-
Notifications
You must be signed in to change notification settings - Fork 3
Evaluate arithmetic expression
A string containing an arithmetic expression is given. Evaluate its outcome.
For example if an expression is represented by the string
3+6*2
then its value should be15
respectively.
JavaScript
This task generally consist of two subtasks:
- implement parser of an expression into so calles postfix notation aka Reverse Polish Notation (RPN)
- implement a computator of the RPN input;
The first may be implemented as a function that takes an expression as a string and returns it in RPN as an array of operands and operators:
function convertToRPN(str) {
var operatorsStack = [];
var convertedStack = [];
var precedence = {
')': 1,
'(': 2,
'+': 3,
'-': 3,
'*': 4,
'/': 4,
};
var popAndKeep = function(stack) {
return (stack && stack.length)
? stack[stack.length-1]
: null;
};
for (var i = 0, c = str.charAt(i), o = '', n = false; i < str.length; i++, c = str.charAt(i)) {
if (!isNaN(parseInt(c))) {
if (n) {
convertedStack[convertedStack.length-1] *= 10;
convertedStack[convertedStack.length-1] += parseInt(c);
} else {
convertedStack.push(parseInt(c));
}
n = true;
} else if (Object.keys(precedence).indexOf(c) > -1) {
while ( operatorsStack.length
&& ( c !== '(' && popAndKeep(operatorsStack) !== ')' && precedence[c] <= precedence[popAndKeep(operatorsStack)] )
&& ( (o = operatorsStack.pop()) !== '(' )
) {
convertedStack.push(o);
}
if (c !== ')') {
operatorsStack.push(c);
}
n = false;
}
//console.log(convertedStack);
//console.log(operatorsStack);
//console.log('');
}
while(operatorsStack.length){
convertedStack.push(operatorsStack.pop());
}
return convertedStack;
}
The latest should take the result of the abovementioned convertToRPN
function and make computations of an array representing arithmetic expression in RPN:
function evaluateRPN(rpn) {
var opers = '+-*/';
var stack = [];
for (var i = 0; i < rpn.length; i++) {
if (opers.indexOf(rpn[i]) === -1) {
stack.push(rpn[i]);
} else {
var a = stack.pop();
var b = stack.pop();
switch (rpn[i]) {
case '+':
stack.push(a + b);
break;
case '-':
stack.push(b - a);
break;
case '*':
stack.push(a * b);
break;
case '/':
stack.push(b / a);
break;
}
}
}
return stack.pop();
}
And at last just as the proof of concept:
[
'2 + 3 * 4', // 2 3 4 * + // = 14
'3 + 4 * 5 / 6', // 3 4 5 * 6 / + // = 6.(3)
'4 + 8 * 6 - 5 / 3 - 2 * 2 + 2', // 4 8 6 * + 5 3 / - 2 2 * - 2 + // = 48.(3)
'((5 / (7 - (1 + 1))) * 3) - (2 + (1 + 1))', // 5 7 1 1 + - / 3 * 2 1 1 + + - // = -1
'(6 + 10 - 4) / (1 + 1 * 2) + 55', // 6 10 + 4 - 1 1 2 * + / 55 + // = 59
].forEach(function(i) {
var rpn = convertToRPN(i);
console.log(`${i} >>> ${rpn} = ${evaluateRPN(rpn)}`);
});
P.S. please, note that at this point unary sign operators are not supported; i.e. computation of the 2+-1
would give rather some nonsence as the result; likely NaN, but not for sure since this example is not about any sort of the correct handling of errors ;)