ASAPUtils
The signal
In postfix notation, the operator comes after both inputs: 2 1 + means 2 + 1. Values wait
until an operator consumes them. The newest two values are the next operands, so use a stack.
One-pass approach
For every token:
- Number → push it.
- Operator → pop
right, popleft, computeleft op right, push the result. - The final stack value is the answer.
int evalRPN(vector<string>& tokens) {
vector<long long> st;
for (string token : tokens) {
if (token != "+" && token != "-" && token != "*" && token != "/") {
st.push_back(stoll(token));
continue;
}
long long right = st.back(); st.pop_back();
long long left = st.back(); st.pop_back();
if (token == "+") st.push_back(left + right);
else if (token == "-") st.push_back(left - right);
else if (token == "*") st.push_back(left * right);
else st.push_back(left / right);
}
return st.back();
}
function evalRPN(tokens) {
const stack = [];
for (const token of tokens) {
if (!['+', '-', '*', '/'].includes(token)) {
stack.push(Number(token));
continue;
}
const right = stack.pop();
const left = stack.pop();
const value = token === '+' ? left + right
: token === '-' ? left - right
: token === '*' ? left * right
: Math.trunc(left / right);
stack.push(value);
}
return stack[0];
}
Walkthrough
For 2 1 + 3 *:
| Token | Stack after token | Reason |
|---|---|---|
| 2 | [2] | number |
| 1 | [2, 1] | number |
| + | [3] | 2 + 1 |
| 3 | [3, 3] | number |
| * | [9] | 3 × 3 |
Complexity
O(n) time because every token is handled once. O(n) space because an expression could contain many operands before its operators.
Traps
- Popping into
leftfirst. Name the first popright. - Using
Math.floorfor division in JS; useMath.truncfor negative values. - Treating
"-11"as an operator because it contains-. Compare the full token against the four exact operator strings. - Returning too early. Intermediate results go back on the stack.
Blank re-solve prompt
Evaluate postfix tokens in one pass. Test
4, 13, 5, /, +and one negative division case.