Evaluate an infix arithmetic expression
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
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];}