Evaluate an infix arithmetic expression

Medium

Problem

Evaluate a normal (infix) expression string with non-negative integers, + − * /, parentheses and spaces, respecting operator precedence. Integer division truncates.

Example 1

Input:  "3 + 2 * 2"
Output: 7

Example 2

Input:  "(1 + (4 + 5 + 2) - 3) + (6 + 8)"
Output: 23

Also asked as: Arithmetic Expression evaluation

Test cases

Case 1

Input:    "3+2*2"
Expected: 7

Case 2

Input:    " 3/2 "
Expected: 1

Case 3

Input:    "(1+(4+5+2)-3)+(6+8)"
Expected: 23

Case 4

Input:    "2*(5+5*2)/3+(6/2+8)"
Expected: 21

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Two stacks (values + operators) with precedence

Time O(n)Space O(n)

Scan tokens; push numbers; on an operator, first resolve any stacked operator of higher/equal precedence; handle parentheses by resolving until "(".

function evalInfix(expr) {
const nums = [], ops = [];
const prec = (o) => (o === '+' || o === '-' ? 1 : o === '*' || o === '/' ? 2 : 0);
const apply = () => {
const b = nums.pop(), a = nums.pop(), o = ops.pop();
nums.push(o === '+' ? a + b : o === '-' ? a - b : o === '*' ? a * b : Math.trunc(a / b));
};
const tokens = expr.match(/\d+|[()+\-*/]/g) || [];
for (const t of tokens) {
if (/\d/.test(t)) nums.push(Number(t));
else if (t === '(') ops.push(t);
else if (t === ')') { while (ops[ops.length - 1] !== '(') apply(); ops.pop(); }
else { while (ops.length && prec(ops[ops.length - 1]) >= prec(t)) apply(); ops.push(t); }
}
while (ops.length) apply();
return nums[0];
}