Stack — Evaluate Postfix (Reverse Polish Notation)

What does it solve?

Evaluate an arithmetic expression written in postfix (Reverse Polish Notation), where operators come after their operands: 3 4 + means 3 + 4. No parentheses, no precedence rules to juggle: the order is baked into the token sequence.

Key insight: a single stack does it. Scan tokens left to right. A number → push it. An operator → pop the top two (the second popped is the left operand), apply the operator, push the result back. When the tokens run out, the one value left on the stack is the answer. Watch operand order for − and /: it's left OP right, not the reverse.

The core idea

// one stack, one pass
for token in tokens:
  if number: push(token)
  else:
    b = pop(); a = pop()
    push(a OP b)
return stack.top()

Complexity

Time complexity

O(N)

One pass over N tokens. Each token triggers a constant amount of work: one push, or two pops and a push.

Space complexity

O(N)

The stack holds pending operands. In the worst case (all numbers first) it grows to about N/2 before any operator collapses it.

Expressions & edge cases

Live animation — tokens feed a single evaluation stack

tokens consumed tokens remaining

current token operator result pushed stack value

Postfix tokens

Evaluation stack (left → right = bottom → top)

Current step detail

token = — stack = — operations = — result = —

Step — of —

token

—

being read

stack top

—

latest value

operations

—

applied

stack size

—

values held

Select an expression and press Play to start.

✓ Done

Speed Medium

Step-by-step table

Step	Token	Type	Action	Stack (after)

C++ implementation

evaluate_rpn.cpp

#include <bits/stdc++.h>
using namespace std;

// Evaluate a postfix (Reverse Polish Notation) expression with one stack.
int evalRPN(vector<string>& tokens) {
    stack<long> st;
    for (auto& tk : tokens) {
        if (tk == "+" || tk == "-" || tk == "*" || tk == "/") {
            long b = st.top(); st.pop();   // right operand
            long a = st.top(); st.pop();   // left operand
            if (tk == "+") st.push(a + b);
            else if (tk == "-") st.push(a - b);
            else if (tk == "*") st.push(a * b);
            else              st.push(a / b);  // a / b, order matters
        } else {
            st.push(stol(tk));           // operand: push its value
        }
    }
    return st.top();                  // last value = answer
}

int main() {
    vector<string> t = {"3","4","+","2","*"};
    cout << evalRPN(t) << "\n"; // (3+4)*2 = 14
    return 0;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars