The challenge
Evaluate a valid postfix expression containing integer operands and +, -, *, /.
Tokens are space-separated. Division truncates toward zero. No division by zero; intermediates fit signed 32-bit integers.
Example
2 1 + 3 * → 9.
Use the walkthrough below to inspect the input and each state change.
See Evaluate Reverse Polish Notation, step by step
Inspect each push, pop, and recorded answer. Entries such as 2: 5 mean index: value.
Zero-based input · top labeled explicitlyLIFO
- Current input index
- —
- Main stack size
- 0
Step 01 / 7
Start with an empty stack
Read the input in order. The stack keeps only the state needed to resolve the next item.
Answer so far
Not recorded yet
- Main stack · bottom → top
- Empty
- Auxiliary stack · bottom → top
- Empty
View exact input and state
Input: ["2","1","+","3","*"]
Main stack: []. Auxiliary stack · bottom → top: [].
Put it into code
Operands wait on the stack until an operator consumes the top two.
Indices are zero-based. C++ uses C++17 or later.
def solve(tokens):
stack = []
for token in tokens:
if token not in ('+', '-', '*', '/'):
stack.append(int(token))
continue
right, left = stack.pop(), stack.pop()
if token == '+': value = left + right
elif token == '-': value = left - right
elif token == '*': value = left * right
else:
value = abs(left) // abs(right)
if (left < 0) != (right < 0): value = -value
stack.append(value)
return stack[0]
#include <algorithm>
#include <optional>
#include <utility>
#include <string>
#include <vector>
using namespace std;
int solve(const vector<string>& tokens) {
vector<long long> stack;
for (const auto& token : tokens) {
if (token != "+" && token != "-" && token != "*" && token != "/") {
stack.push_back(stoll(token));
continue;
}
long long right = stack.back(); stack.pop_back();
long long left = stack.back(); stack.pop_back();
long long value = token == "+" ? left + right : token == "-" ? left - right
: token == "*" ? left * right : left / right;
stack.push_back(value); // Integer division truncates toward zero.
}
return static_cast<int>(stack.back());
}