Infix to Postfix Conversion and Postfix Evaluation with a Stack (C++)

Why a stack, and where this actually shows up

Read A+B*C left to right. When you reach the +, you cannot emit it yet — a higher-precedence * might be lurking ahead, and it is. So the + has to wait. When you reach *, it also has to wait for C. Now the crucial observation: * started waiting later than +, and it finishes waiting earlier. Nested lifetimes with last-in-first-out completion — that is the definition of a stack, and it is why the stack is not merely a solution here but the natural one.

Parentheses reinforce it. ( opens a scope that must be closed by the nearest unmatched ). Nesting again, so again a stack.

Where this matters outside a textbook:

• Calculators and spreadsheet formula engines parse infix and evaluate a postfix or tree form.
• Stack virtual machines — JVM bytecode, WebAssembly, CPython's older evaluation loop — are literally postfix machines. iadd pops two, pushes one.
• HP RPN calculators ask the user to type postfix directly, precisely because it needs no parentheses and no precedence.
• Compiler front ends use the same shunting-yard shape to build expression trees.

One more property worth naming: postfix is unambiguous without precedence rules. ABC*+ and AB+C* are different strings with different meanings, and neither needs a convention about whether * binds tighter than +. All that knowledge got baked in during conversion, once.

The conversion rules, stated precisely

Scan the infix string one character at a time. Maintain an operator stack and an output string. Exactly five cases:

1. Operand (letter or digit) — append to output immediately. Operands never wait; their position in postfix is the same as in infix.
2. ( — push it. It is a fence, not an operator.
3. ) — pop and emit until you see ( on top, then pop the ( and throw it away. Parentheses never appear in postfix output.
4. Operator — while the stack is non-empty and the top is not ( and the top has higher precedence than the incoming operator, or equal precedence and the incoming operator is left-associative: pop and emit. Then push the incoming operator.
5. End of input — pop and emit everything left. If you meet a ( here, the input had unbalanced parentheses.

Precedence used here: + - → 1; * / % → 2; ^ → 3.

Two details in rule 4 do all the work, and both are easy to get wrong.

The top != '(' guard. A ( is pushed but is never popped by a precedence comparison — only rule 3 removes it. Give ( precedence 0 and add the explicit guard; relying on precedence alone is fragile. Concretely, in A*(B+C), when the + arrives the stack is * (. The * outranks +, but it must not be popped: it belongs outside the parentheses. The ( on top blocks the comparison from ever reaching it.

Equal precedence and associativity. A-B-C means (A-B)-C because - is left-associative. So when the second - arrives with - already on top at equal precedence, you do pop — giving AB-C-. If you refuse to pop on ties, you get ABC--, which evaluates as A-(B-C): a different number. The one common right-associative operator is ^: A^B^C means A^(B^C), so on a tie you must not pop, giving ABC^^. That is the sole reason the code below carries a rightAssociative() helper.

int precedence(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/' || op == '%') return 2;
    if (op == '^') return 3;      // right-associative
    return 0;                     // '(' and anything else
}

bool rightAssociative(char op) { return op == '^'; }

// the decision in rule 4, spelled out:
//   pop while  top != '('  &&  ( prec(top) > prec(ch)
//                            || (prec(top) == prec(ch) && !rightAssociative(ch)) )

Worked conversion: 7*(2+3)-8/4

Stack is written bottom-to-top, so the rightmost character is the top.

Read the two interesting rows again. At ), the * sitting below the ( was never examined — correct, since it is outside the parentheses. At -, the * finally came out, and only then did - get pushed; that ordering is what encodes "multiply first, subtract after".

Sanity check the result by reading it back: 723+*84/- → 7 (2 3 +) * = 7×5 = 35, then 8 4 / = 2, then 35 2 - = 33. And 7*(2+3)-8/4 = 35 − 2 = 33. They agree.

The C++ implementation

This is the complete program — compiled with g++ -std=c++17 -Wall -Wextra -pedantic and run; the outputs in main()'s comments are the real ones.

A few deliberate choices. std::isalnum treats any letter or digit as an operand, so the same function converts symbolic expressions (A+B*C) and single-digit numeric ones (7*(2+3)). Whitespace is skipped rather than rejected. The static_cast<unsigned char> on every <cctype> call is not decoration: passing a negative char to isalnum/isdigit is undefined behaviour, and it bites on inputs with non-ASCII bytes. Errors are thrown rather than returned as sentinel strings, so a malformed expression cannot be silently mistaken for a valid answer.

#include <iostream>
#include <stack>
#include <string>
#include <cctype>
#include <stdexcept>

int precedence(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/' || op == '%') return 2;
    if (op == '^') return 3;
    return 0;
}

bool rightAssociative(char op) { return op == '^'; }

// ---- infix -> postfix -------------------------------------------------
std::string toPostfix(const std::string& infix) {
    std::stack<char> ops;
    std::string out;

    for (char ch : infix) {
        if (std::isspace(static_cast<unsigned char>(ch)))
            continue;

        if (std::isalnum(static_cast<unsigned char>(ch))) {
            out += ch;                                  // operand: emit now
        }
        else if (ch == '(') {
            ops.push(ch);                               // fence; never popped on precedence
        }
        else if (ch == ')') {
            while (!ops.empty() && ops.top() != '(') {
                out += ops.top();
                ops.pop();
            }
            if (ops.empty())
                throw std::runtime_error("unbalanced ')'");
            ops.pop();                                  // discard the '('
        }
        else {                                          // an operator
            while (!ops.empty() && ops.top() != '(' &&
                   (precedence(ops.top()) > precedence(ch) ||
                    (precedence(ops.top()) == precedence(ch) && !rightAssociative(ch)))) {
                out += ops.top();
                ops.pop();
            }
            ops.push(ch);
        }
    }

    while (!ops.empty()) {                              // flush what is still waiting
        if (ops.top() == '(')
            throw std::runtime_error("unbalanced '('");
        out += ops.top();
        ops.pop();
    }
    return out;
}

// ---- postfix evaluation (single-digit operands) -----------------------
int evaluatePostfix(const std::string& postfix) {
    std::stack<int> values;

    for (char ch : postfix) {
        if (std::isspace(static_cast<unsigned char>(ch)))
            continue;

        if (std::isdigit(static_cast<unsigned char>(ch))) {
            values.push(ch - '0');                 // char digit -> int value
            continue;
        }

        if (values.size() < 2)
            throw std::runtime_error("malformed postfix: not enough operands");

        int right = values.top(); values.pop();    // FIRST pop  = RIGHT operand
        int left  = values.top(); values.pop();    // SECOND pop = LEFT  operand

        int result;
        switch (ch) {
            case '+': result = left + right; break;
            case '-': result = left - right; break;
            case '*': result = left * right; break;
            case '/':
                if (right == 0) throw std::runtime_error("division by zero");
                result = left / right;
                break;
            case '%':
                if (right == 0) throw std::runtime_error("modulo by zero");
                result = left % right;
                break;
            case '^': {
                result = 1;
                for (int i = 0; i < right; ++i) result *= left;
                break;
            }
            default:
                throw std::runtime_error(std::string("unknown operator '") + ch + "'");
        }
        values.push(result);
    }

    if (values.size() != 1)
        throw std::runtime_error("malformed postfix: operands left over");
    return values.top();
}

int main() {
    std::string infix = "7*(2+3)-8/4";
    std::string postfix = toPostfix(infix);
    std::cout << infix << "  ->  " << postfix << '\n';            // 723+*84/-
    std::cout << "value = " << evaluatePostfix(postfix) << '\n';  // value = 33

    std::cout << toPostfix("A+B*(C-D)/E") << '\n';                // ABCD-*E/+
    std::cout << toPostfix("a^b^c-d")     << '\n';                // abc^^d-
    return 0;
}

Evaluating postfix, and the operand-order rule

Evaluation is the shorter algorithm and the one with the nastier bug.

Scan left to right. Operand → push. Operator → pop two values, apply, push the single result. At the end the stack holds exactly one number: the answer.

ch - '0'. The C++ standard guarantees that the character codes for '0' through '9' are consecutive and increasing. So '7' - '0' is 55 - 48 = 7 — a plain int subtraction that converts a digit character into the digit value. Writing values.push(ch) instead pushes 55, and the whole computation quietly runs on ASCII codes. This trick only works for one digit; see the extension below.

Now the rule that everything depends on. In postfix a b -, a is pushed first and b second. A stack returns the most recent item, so:

The first value you pop is the RIGHT operand. The second value you pop is the LEFT operand.

Write it as right then left, in that order, and name the variables — do not try to remember which of two anonymous int a, b is which.

Why this bug survives testing: + and * are commutative, so a reversed pop gives the correct answer for them. An evaluator tested only on 234*+ looks perfect. The failure appears only on -, /, % and ^, and even then it does not crash — it returns a small, plausible integer. "82/" should be 4; reversed it computes 2/8, and C++ integer division truncates that to 0. Zero is not an obviously wrong-looking answer, which is exactly what makes this the most expensive mistake in the topic.

Trace of 723+*84/-:

One value left on the stack — 33. Had the pops been reversed, the / would give 4/8 = 0 and the - would give 0 - 35 = -35. Still one value, still an integer, still wrong.

Complexity, and why it is what it is

Let n be the length of the input string.

The interesting claim is that conversion is O(n) despite containing a while loop inside a for loop. That nesting looks like O(n²), and reasoning "loop inside a loop, therefore quadratic" is the standard wrong answer here.

The correct argument is amortised, and it is one sentence: every operator character is pushed onto the stack exactly once and popped at most once, so across the entire scan the inner while can execute at most n pop operations in total. One character might trigger many pops — in A*B*C*D+E, the + unwinds three *s at once — but those three pops are paid for by the three pushes that already happened. The total work is bounded by (pushes + pops) ≤ 2n, hence O(n) overall, and O(1) amortised per character even though a single character is not O(1) worst case. Evaluation has no nested loop at all: each symbol does a constant amount of work.

Space is the maximum stack depth. For conversion, the worst case is a fully nested expression like ((((((a)))))) or a long right-associative chain a^b^c^d^…, where nothing can be popped until the end: depth Θ(n). For evaluation, the worst case is a run of operands before any operator, e.g. 9 9 9 9 + + +, again Θ(n). Both are O(1) extra space beyond the stack only in the trivial case of an already-flat expression — do not claim O(1) space overall.

Also worth stating: this is a single pass, no backtracking, no lookahead beyond the current character. That is why the same algorithm works on a stream you can only read once.

Mistakes people actually make

In rough order of how often they cost real marks and real debugging time.

1. Reversed operand order. Covered above. First pop is the right operand. Commutative operators hide it; - and / expose it as a plausible wrong number rather than a crash.
2. Popping the ( on a precedence comparison. Without the ops.top() != '(' guard, A*(B+C) pops the * out from under the parenthesis and produces garbage. Give ( precedence 0 and keep the explicit guard.
3. Getting associativity backwards at equal precedence. For left-associative operators you must pop on a tie: A-B-C → AB-C-. Not popping gives ABC-- = A-(B-C). For ^ (right-associative) the rule inverts. Using >= blindly breaks ^; using > blindly breaks - and /.
4. Forgetting the final flush loop. The scan ends with operators still waiting. Omitting the drain silently truncates the output — A+B*C comes out as ABC with no operators at all.
5. Forgetting to discard the matching (. After popping to the ( in rule 3, you must pop() it and not append it. A stray ( in the output string will make the evaluator throw "unknown operator".
6. Calling top() on an empty stack. std::stack::top() on an empty container is undefined behaviour, not an exception — no bounds check, no std::out_of_range. Malformed input like "5+" or "+" will read garbage memory. Always if (values.size() < 2) throw … before the two pops, and !ops.empty() before every top().
7. ch - '0' on multi-digit input. "12+3" is read as operands 1, 2, then +, then 3 — a completely different expression that still evaluates without error. The single-char trick is a deliberate simplification, not a general parser. See the next section.
8. Pushing the character instead of its value. values.push(ch) pushes 55 for '7'. The whole answer becomes ASCII arithmetic.
9. Unbalanced parentheses accepted silently. (A+B with no error check just drops the ( (or emits it). Check for ( during the final flush, and for an empty stack when handling ).
10. Integer-division surprises. left / right truncates toward zero, so 7/2 is 3 and -7/2 is −3. And a zero divisor is UB in C++, not an exception — guard it explicitly. If you want real arithmetic, template the evaluator on double; then also drop %.
11. Reading your own trace table inconsistently. Pick one convention — bottom-to-top or top-to-bottom — write it in the header, and never switch. Half of all hand-traced errors are the tracer mis-reading their own stack column.
12. Assuming the output string is a stack. The output is append-only, in order. Only operators are stacked. Mixing the two mental models produces reversed operand sequences in the answer.

Extension: multi-digit and negative operands

The single-character version is the right thing to learn first, but the moment your input contains 120 the ch - '0' approach breaks. The fix is to tokenise: split on whitespace and parse each token as a whole number, so the caller writes "120 5 / 3 -" instead of jamming digits together. This is also why real RPN calculators require spaces — 12 3 + and 1 23 + are genuinely different expressions and no amount of cleverness can separate them from 123+.

The structure of the algorithm does not change at all; only the "is this an operand, and what is its value" test does. That is a good sign: the stack discipline was the essential part, and digit parsing was incidental. The code below was also compiled and run.

#include <iostream>
#include <sstream>
#include <stack>
#include <string>
#include <cctype>
#include <stdexcept>

long long evaluatePostfixTokens(const std::string& postfix) {
    std::istringstream in(postfix);
    std::stack<long long> values;
    std::string token;

    while (in >> token) {
        bool numeric = !token.empty() &&
                       (std::isdigit(static_cast<unsigned char>(token[0])) ||
                        (token.size() > 1 && token[0] == '-'));   // "-4" is a number, "-" is not
        if (numeric) {
            values.push(std::stoll(token));
            continue;
        }

        if (values.size() < 2)
            throw std::runtime_error("not enough operands");

        long long right = values.top(); values.pop();
        long long left  = values.top(); values.pop();

        switch (token[0]) {
            case '+': values.push(left + right); break;
            case '-': values.push(left - right); break;
            case '*': values.push(left * right); break;
            case '/':
                if (right == 0) throw std::runtime_error("division by zero");
                values.push(left / right);
                break;
            default: throw std::runtime_error("unknown operator");
        }
    }

    if (values.size() != 1)
        throw std::runtime_error("malformed postfix");
    return values.top();
}

int main() {
    std::cout << evaluatePostfixTokens("120 5 / 3 -") << '\n';   // 21
    std::cout << evaluatePostfixTokens("-4 10 *")     << '\n';   // -40
}

Checking your own answers

Two cheap self-checks that catch most errors before you commit to a result.

Count the symbols. A well-formed postfix expression over binary operators always has exactly one more operand than operators. 723+*84/- has 5 operands and 4 operators — consistent. If your conversion produced 5 operands and 3 operators, you dropped an operator (usually by forgetting the flush loop).

Read the postfix back into infix. Run the evaluation algorithm but push strings instead of numbers: on each operator, pop right, pop left, and push "(" + left + op + right + ")". At the end you have a fully parenthesised infix expression. Compare it to your original. For ABC*+ this reconstructs (A+(B*C)), which matches A+B*C; for AB+C* it gives ((A+B)*C), which does not. This is the same algorithm you already wrote, with int swapped for std::string, so it is about six lines of change — and it is the single most effective way to verify a conversion by hand.

Reference results (all produced by the code on this page, so you can use them as test cases):

Exercises with solutions

Work through each question before opening the solution below it.

int evaluate(const std::string& p) {
    std::stack<int> st;
    for (char ch : p) {
        if (std::isdigit(static_cast<unsigned char>(ch))) { st.push(ch - '0'); continue; }
        int left  = st.top(); st.pop();
        int right = st.top(); st.pop();
        switch (ch) {
            case '+': st.push(left + right); break;
            case '-': st.push(left - right); break;
            case '*': st.push(left * right); break;
            case '/': st.push(left / right); break;
        }
    }
    return st.top();
}

if (st.size() < 2) throw std::runtime_error("malformed postfix");
int right = st.top(); st.pop();   // last pushed = right operand
int left  = st.top(); st.pop();

Related pages