Evaluate a postfix expression
A tiny expression engine accepts a calculation already written in postfix — operands first, operator after — and works it out.
- Tokens are either decimal integers or one of + - * /.
- Division is integer division, and every division in the cases is exact.
- There are never too few operands; the tokens always evaluate cleanly.
- An empty token list evaluates to zero.
evaluatePostfix(tokens: list<string>) → int
Java needs a compiler and Drill does not host one yet, so this page is the reference rather than an exercise: the problem, worked examples, and the solution in full. To type it out, the same problem runs in Python.
Where you start
int evaluatePostfix(List<String> tokens) {
}Worked examples
| Call | Result |
|---|---|
evaluatePostfix(Main.<String>ls("3", "4", "+")) | 7 |
evaluatePostfix(Main.<String>ls("10", "3", "-")) | 7 |
evaluatePostfix(Main.<String>ls("2", "3", "*", "4", "+")) | 10 |
evaluatePostfix(Main.<String>ls("12", "4", "/")) | 3 |
Hint
One stack. Push numbers; when an operator arrives, pop two, apply it, push the result back.
Reference solution in Java
int evaluatePostfix(List<String> tokens) {
Deque<Integer> stack = new ArrayDeque<>();
for (String tok : tokens) {
if (tok.length() > 1 || Character.isDigit(tok.charAt(0))) {
stack.push(Integer.parseInt(tok));
} else {
int b = stack.pop();
int a = stack.pop();
if (tok.equals("+")) stack.push(a + b);
else if (tok.equals("-")) stack.push(a - b);
else if (tok.equals("*")) stack.push(a * b);
else stack.push(a / b);
}
}
return stack.isEmpty() ? 0 : stack.pop();
}