Evaluate a postfix expression

Easy

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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();
}