Evaluate Reverse Polish Notation
Problem
Evaluate an arithmetic expression in postfix (reverse Polish) form. Tokens are integers or one of + − × ÷. Division truncates toward zero.
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.
Input
tokens = ["6", "3", "−", "4", "*", "8", "+"]Output
20((6 − 3) × 4) + 8 = 20.
def 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();
}