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
int evaluatePostfix(std::vector<std::string> tokens) {
}Worked examples
| Call | Result |
|---|---|
evaluatePostfix(std::vector<std::string>{std::string("3"), std::string("4"), std::string("+")}) | 7 |
evaluatePostfix(std::vector<std::string>{std::string("10"), std::string("3"), std::string("-")}) | 7 |
evaluatePostfix(std::vector<std::string>{std::string("2"), std::string("3"), std::string("*"), std::string("4"), std::string("+")}) | 10 |
evaluatePostfix(std::vector<std::string>{std::string("12"), std::string("4"), std::string("/")}) | 3 |
Hint
One stack. Push numbers; when an operator arrives, pop two, apply it, push the result back.
Reference solution in C++
int evaluatePostfix(std::vector<std::string> tokens) {
std::vector<int> stack;
for (const string& tok : tokens) {
if (tok.size() > 1 || (tok[0] >= '0' && tok[0] <= '9')) {
stack.push_back(std::stoi(tok));
} else {
int b = stack.back();
stack.pop_back();
int a = stack.back();
stack.pop_back();
if (tok == "+") stack.push_back(a + b);
else if (tok == "-") stack.push_back(a - b);
else if (tok == "*") stack.push_back(a * b);
else stack.push_back(a / b);
}
}
return stack.empty() ? 0 : stack.back();
}