Evaluate a postfix expression
Problem
Evaluate an expression in postfix (Reverse Polish) notation, where every operator comes after its two operands. Integer division truncates toward zero.
Example 1
Input: ["2", "1", "+", "3", "*"] Output: 9
(2 + 1) × 3.
Example 2
Input: ["4", "13", "5", "/", "+"] Output: 6
4 + (13 / 5) = 4 + 2.
Also asked as: Evaluation of Postfix expression
Test cases
Case 1
Input: ["2","1","+","3","*"] Expected: 9
Case 2
Input: ["4","13","5","/","+"] Expected: 6
Case 3
Input: ["10","6","9","3","+","-11","*","/","*","17","+","5","+"] Expected: 22
View solutionHide solution1 approach
1. Operand stack
Time O(n)Space O(n)
Push numbers; on an operator, pop two, apply, push the result.
function evalPostfix(tokens) { const st = []; const ops = { '+': (a, b) => a + b, '-': (a, b) => a - b, '*': (a, b) => a * b, '/': (a, b) => Math.trunc(a / b) }; for (const t of tokens) { if (t in ops) { const b = st.pop(), a = st.pop(); st.push(ops[t](a, b)); } else st.push(Number(t)); } return st.pop();}