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
C# 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
public int EvaluatePostfix(List<string> tokens) {
}Worked examples
| Call | Result |
|---|---|
EvaluatePostfix(new List<string> { "3", "4", "+" }) | 7 |
EvaluatePostfix(new List<string> { "10", "3", "-" }) | 7 |
EvaluatePostfix(new List<string> { "2", "3", "*", "4", "+" }) | 10 |
EvaluatePostfix(new List<string> { "12", "4", "/" }) | 3 |
Hint
One stack. Push numbers; when an operator arrives, pop two, apply it, push the result back.
Reference solution in C#
public int EvaluatePostfix(List<string> tokens) {
var stack = new Stack<int>();
foreach (string tok in tokens) {
if (tok.Length > 1 || char.IsDigit(tok[0])) {
stack.Push(int.Parse(tok));
} else {
int b = stack.Pop();
int a = stack.Pop();
if (tok == "+") stack.Push(a + b);
else if (tok == "-") stack.Push(a - b);
else if (tok == "*") stack.Push(a * b);
else stack.Push(a / b);
}
}
return stack.Count == 0 ? 0 : stack.Pop();
}