Infix to Postfix in C++ (Complete Code + Output)

The complete C++ program

Save this as infix_to_postfix.cpp. It uses only the standard library and handles multi-character operands, decimals, all six operators and nested brackets.

infix_to_postfix.cpp

// Convert an infix expression to postfix (Reverse Polish Notation) using a stack.

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

namespace {

const std::unordered_map<char, int> kPrecedence = {
    {'^', 3},
    {'*', 2}, {'/', 2}, {'%', 2},
    {'+', 1}, {'-', 1},
};

const std::unordered_set<char> kRightAssociative = {'^'};

bool IsOperator(char c) { return kPrecedence.count(c) > 0; }

int Precedence(char c) {
    auto it = kPrecedence.find(c);
    return it == kPrecedence.end() ? 0 : it->second;
}

bool IsOperandChar(char c) {
    return std::isalnum(static_cast<unsigned char>(c)) || c == '_' || c == '.';
}

}  // namespace

// Returns the postfix form, tokens separated by single spaces.
std::string InfixToPostfix(const std::string& expression) {
    std::string output;
    std::stack<char> ops;

    for (std::size_t i = 0; i < expression.size();) {
        const char c = expression[i];

        if (std::isspace(static_cast<unsigned char>(c))) {
            ++i;
            continue;
        }

        // Copy a whole operand so "rate" and "12" stay single tokens.
        if (IsOperandChar(c)) {
            const std::size_t start = i;
            while (i < expression.size() && IsOperandChar(expression[i])) ++i;
            output += expression.substr(start, i - start);
            output += ' ';
            continue;
        }

        if (c == '(') {
            ops.push(c);
        } else if (c == ')') {
            while (!ops.empty() && ops.top() != '(') {
                output += ops.top();
                output += ' ';
                ops.pop();
            }
            if (ops.empty()) throw std::invalid_argument("unbalanced brackets: an extra ')'");
            ops.pop();                                  // discard the matching '('
        } else if (IsOperator(c)) {
            while (!ops.empty() && ops.top() != '(' &&
                   (Precedence(ops.top()) > Precedence(c) ||
                    (Precedence(ops.top()) == Precedence(c) &&
                     kRightAssociative.count(c) == 0))) {
                output += ops.top();
                output += ' ';
                ops.pop();
            }
            ops.push(c);
        } else {
            throw std::invalid_argument(std::string("invalid character: '") + c + "'");
        }
        ++i;
    }

    while (!ops.empty()) {
        if (ops.top() == '(') throw std::invalid_argument("unbalanced brackets: a missing ')'");
        output += ops.top();
        output += ' ';
        ops.pop();
    }

    if (!output.empty() && output.back() == ' ') output.pop_back();
    return output;
}

int main() {
    std::string infix;
    std::cout << "Enter an infix expression: ";
    if (!std::getline(std::cin, infix)) return 1;

    try {
        std::cout << "Postfix expression: " << InfixToPostfix(infix) << '\n';
    } catch (const std::invalid_argument& e) {
        std::cout << "Error: " << e.what() << '\n';
    }
    return 0;
}

Compile and run it

g++ -std=c++17 -Wall -Wextra -o infix_to_postfix infix_to_postfix.cpp
./infix_to_postfix

Clang works identically with clang++. On Windows with MSVC use cl /EHsc /std:c++17 infix_to_postfix.cpp. C++17 is not strictly required — the program compiles under C++11 — but it is a sensible default.

Sample output

Enter an infix expression: A+B*C
Postfix expression: A B C * +

Enter an infix expression: (A+B)*C-D
Postfix expression: A B + C * D -

Enter an infix expression: rate * 12 + 250
Postfix expression: rate 12 * 250 +

Enter an infix expression: (A+B
Error: unbalanced brackets: a missing ')'

Those are the real outputs of the listing above. Run the same expressions through the converter on the homepage to compare against the full stack trace.

How it works

The program is a precedence map, an associativity set, and one function that scans the string once.

What each part of the C++ program does
Part	Purpose
kPrecedence	Maps each operator to a number; `count()` doubles as the "is this an operator?" test
kRightAssociative	A set holding only `^`
std::stack<char>	Holds operators and bracket markers
ops.top()	Peek — reads the top without removing it
ops.pop()	Removes the top and returns nothing
anonymous namespace	Keeps the helpers internal to this translation unit
std::isspace / isalnum	Cast to `unsigned char` first — passing a negative `char` is undefined behaviour

Why std::stack, and the top/pop split

Use std::stack. It is a container adaptor over std::deque with O(1) push, pop and top. Writing your own array stack is worth doing once as an exercise, and otherwise a liability.

pop() does not return the value

This surprises people coming from Python or Java. std::stack::pop() returns void, because returning by value could throw after the element was removed, losing it. So every pop here is two calls: ops.top() to read it, then ops.pop() to remove it. Writing output += ops.pop(); will not compile.

The two rules that decide correctness

the condition that matters

while (!ops.empty() && ops.top() != '(' &&
       (Precedence(ops.top()) > Precedence(c) ||
        (Precedence(ops.top()) == Precedence(c) &&
         kRightAssociative.count(c) == 0))) {
    output += ops.top();
    output += ' ';
    ops.pop();
}
ops.push(c);

The == branch. Equal precedence must also pop, for left-associative operators. Remove it and A - B - C becomes A B C - -, meaning A - (B - C).
The count(c) == 0 guard. Without it, a ^ b ^ c becomes a b ^ c ^ instead of a b c ^ ^.
The ops.top() != '(' guard. An opening bracket is a floor; popping must never run past it.

Evaluating the postfix result

A second stack, holding double this time. Push operands; on an operator pop two values, apply it, push the result.

postfix_evaluator.cpp

// Evaluate a postfix expression with a stack of values.

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

double Apply(char op, double left, double right) {
    switch (op) {
        case '+': return left + right;
        case '-': return left - right;
        case '*': return left * right;
        case '/':
            if (right == 0) throw std::domain_error("division by zero");
            return left / right;
        case '%':
            if (right == 0) throw std::domain_error("modulo by zero");
            return std::fmod(left, right);
        case '^': return std::pow(left, right);
        default:  throw std::invalid_argument("unknown operator");
    }
}

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

    while (in >> token) {
        if (token.size() == 1 && std::string("+-*/%^").find(token[0]) != std::string::npos) {
            if (values.size() < 2) throw std::invalid_argument("not enough operands for " + token);
            const double right = values.top(); values.pop();   // popped first
            const double left  = values.top(); values.pop();   // popped second
            values.push(Apply(token[0], left, right));
        } else {
            values.push(std::stod(token));
        }
    }

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

std::string InfixToPostfix(const std::string&);   // from infix_to_postfix.cpp

int main() {
    const std::string samples[] = {
        "2 + 3 * 4", "(2 + 3) * 4", "2 ^ 3 ^ 2",
        "100 / 5 / 2", "3 + 4 * 2 / (1 - 5) ^ 2", "6*4+2^5-3",
    };
    for (const auto& infix : samples) {
        const std::string postfix = InfixToPostfix(infix);
        std::cout << infix;
        for (std::size_t i = infix.size(); i < 26; ++i) std::cout << ' ';
        std::cout << "-> " << postfix;
        for (std::size_t i = postfix.size(); i < 26; ++i) std::cout << ' ';
        std::cout << "= " << EvaluatePostfix(postfix) << '\n';
    }
    return 0;
}

2 + 3 * 4                 -> 2 3 4 * +                 = 14
(2 + 3) * 4               -> 2 3 + 4 *                 = 20
2 ^ 3 ^ 2                 -> 2 3 2 ^ ^                 = 512
100 / 5 / 2               -> 100 5 / 2 /               = 10
3 + 4 * 2 / (1 - 5) ^ 2   -> 3 4 2 * 1 5 - 2 ^ / +     = 3.5
6*4+2^5-3                 -> 6 4 * 2 5 ^ + 3 -         = 53

Note the operand order

right is popped before left. The second value popped is the left operand, because it was pushed first. Swap the two lines and addition still works while subtraction, division and exponentiation silently invert — 2 3 2 ^ ^ would give 81 instead of 512.

Errors you are likely to hit

Common problems in an infix to postfix C++ program
Symptom	Cause	Fix
Will not compile: `output += ops.pop();`	`pop()` returns `void`	Read `ops.top()` first, then `ops.pop()`
Crash or garbage on non-ASCII input	`isalnum(char)` with a negative value	Cast to `unsigned char` first
`A-B-C` gives `A B C - -`	Equal precedence pushes instead of popping	Add the `==` branch
`a^b^c` gives `a b ^ c ^`	`^` treated as left associative	Add the right-associativity guard
`12+3` gives `1 2 3 +`	Reading one character per operand	Consume the whole alphanumeric run
Only the first word is read	`std::cin >> s` stops at whitespace	Use `std::getline(std::cin, s)`
`%` will not compile on doubles	`%` is integer-only in C++	Use `std::fmod` from `<cmath>`

Frequently asked questions

How do you convert infix to postfix in C++?

Use std::stack<char> for the operators. Scan the expression left to right: append operands to the output, push an opening bracket, and on a closing bracket pop to the output until the matching opening bracket. For an operator, pop while the stack top has higher precedence — or equal precedence and the incoming operator is left associative — then push it. Pop whatever remains when the scan ends.

Should I use std::stack or write my own?

Use std::stack. It is a container adaptor over std::deque with O(1) push, pop and top, it is in the standard library, and there is nothing to get wrong. Writing an array stack is only worth it as an exercise, or when you must avoid dynamic allocation entirely.

Why does std::stack::pop() not return the value?

Because returning by value could throw after the element was already removed, which would lose it. The standard library splits the operation: top() reads the element, pop() removes it. Every pop in this program is therefore two calls — read the top, then pop.

How do I handle multi-digit numbers in C++?

Consume the whole run of alphanumeric characters, underscores and dots as one token rather than reading a single char. The inner while loop in this program does that with substr, so rate * 12 + 250 produces rate 12 * 250 + instead of splitting the digits.

What is the time complexity?

O(n) time and O(n) space for n characters. Each character is read once and each operator is pushed and popped at most once. Appending to std::string is amortised O(1), so building the output stays linear.

Why use fmod instead of % for the modulo operator?

The % operator in C++ only works on integers. Since this evaluator holds doubles, std::fmod from <cmath> is the floating-point equivalent. Using % on a double will not compile.