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
Go 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
func evaluatePostfix(tokens []string) int {
}Worked examples
| Call | Result |
|---|---|
evaluatePostfix([]string{"3", "4", "+"}) | 7 |
evaluatePostfix([]string{"10", "3", "-"}) | 7 |
evaluatePostfix([]string{"2", "3", "*", "4", "+"}) | 10 |
evaluatePostfix([]string{"12", "4", "/"}) | 3 |
Hint
One stack. Push numbers; when an operator arrives, pop two, apply it, push the result back.
Reference solution in Go
func evaluatePostfix(tokens []string) int {
stack := []int{}
for _, tok := range tokens {
if len(tok) > 1 || (tok[0] >= '0' && tok[0] <= '9') {
n, _ := strconv.Atoi(tok)
stack = append(stack, n)
} else {
b := stack[len(stack)-1]
a := stack[len(stack)-2]
stack = stack[:len(stack)-2]
switch tok {
case "+":
stack = append(stack, a+b)
case "-":
stack = append(stack, a-b)
case "*":
stack = append(stack, a*b)
default:
stack = append(stack, a/b)
}
}
}
if len(stack) == 0 {
return 0
}
return stack[len(stack)-1]
}