Evaluate Reverse Polish Notation
Problem
Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, and /. Each operand may be an integer or another expression.
Walk the tokens. If a token is a number, push it. If it's an operator, pop the top two values (the second pop is the left operand), apply the operator, and push the result. The final stack value is the answer.
tokens = ["6", "3", "−", "4", "*", "8", "+"]20def eval_rpn(tokens):
stack = []
for t in tokens:
if t.lstrip("-").isdigit():
stack.append(int(t))
continue
b = stack.pop()
a = stack.pop()
if t == "+": stack.append(a + b)
elif t == "-": stack.append(a - b)
elif t == "*": stack.append(a * b)
else: stack.append(int(a / b))
return stack[0]function evalRPN(tokens) {
const stack = [];
for (const t of tokens) {
if (/^-?\d+$/.test(t)) { stack.push(Number(t)); continue; }
const b = stack.pop(), a = stack.pop();
if (t === "+") stack.push(a + b);
else if (t === "-") stack.push(a - b);
else if (t === "*") stack.push(a * b);
else stack.push(Math.trunc(a / b));
}
return stack[0];
}class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> st = new ArrayDeque<>();
for (String t : tokens) {
if (t.length() > 1 || Character.isDigit(t.charAt(0))) {
st.push(Integer.parseInt(t));
continue;
}
int b = st.pop(), a = st.pop();
switch (t) {
case "+": st.push(a + b); break;
case "-": st.push(a - b); break;
case "*": st.push(a * b); break;
default: st.push(a / b);
}
}
return st.peek();
}
}int evalRPN(vector<string>& tokens) {
stack<int> st;
for (auto& t : tokens) {
if (t.size() > 1 || isdigit(t[0])) { st.push(stoi(t)); continue; }
int b = st.top(); st.pop();
int a = st.top(); st.pop();
if (t == "+") st.push(a + b);
else if (t == "-") st.push(a - b);
else if (t == "*") st.push(a * b);
else st.push(a / b);
}
return st.top();
}Explanation
Reverse Polish (postfix) notation writes the operator after its operands, which is exactly what a stack loves: numbers wait on the stack until an operator arrives to consume them.
We walk the tokens. If a token is a number we push it. If it is an operator, we pop the top two values, apply the operator, and push the result back. The careful detail is order: the first pop is the right operand b and the second pop is the left operand a, so we compute a op b.
This naturally respects the intended grouping without any parentheses, because the postfix order already encodes it. When every token is processed, the single value left on the stack is the answer.
Example: ["6","3","-","4","*","8","+"]. Push 6, 3. - → 6-3=3. Push 4. * → 3*4=12. Push 8. + → 12+8=20. Result is 20.
Each token is handled in constant time, so the evaluation is a single linear pass.