Infix to postfix with the shunting-yard method

Why this matters

When you type 3 + 4 * 2 into a calculator, the calculator must know that the multiplication happens first. Spreadsheets, compilers and search filters all have to read expressions like this and work out the order of the operations. A common way to do that is to first rewrite the expression into a form where the order is already fixed. This lesson shows how to do that rewrite with a stack, using a method that Edsger Dijkstra described and that people call the shunting-yard method.

You do not need any C++ to follow the first half. The second half uses C++ with the standard library, and every program in the lesson was compiled with g++ -std=c++20 -Wall -Wextra and run. The output shown is copied from those runs.

Lesson 08 in this module evaluates expressions directly with two stacks. This lesson stops one step earlier: it only changes the order of the symbols.

Words used in this lesson

An expression is a string of numbers, names, operators and brackets that stands for a value, such as 3 + 4 * 2.

A token is one meaningful piece of an expression. The tokens of 3 + 4 * 2 are 3, +, 4, * and 2. Spaces are not tokens.

An operand is a value that an operator works on. In 3 + 4, the operands are 3 and 4. In this lesson an operand can also be a name such as a.

An operator is a symbol that combines operands, such as +, -, * or /.

Infix notation puts each operator between its two operands, like 3 + 4. This is how people normally write maths.

Postfix notation, also called reverse Polish notation, puts each operator after its two operands. 3 4 + means the same as 3 + 4. The postfix form of 3 + 4 * 2 is 3 4 2 * +.

Precedence is the rule that decides which operator binds tighter. In maths, * and / bind tighter than + and -, so 3 + 4 * 2 means 3 + (4 * 2).

Associativity is the rule for a run of operators with the same precedence. Subtraction works left to right: 8 - 3 - 2 means (8 - 3) - 2, which is 3. We say subtraction is left-associative.

A stack is a pile where you can only add or remove items at the top. The last item you put on is the first one you take off. People call this last in, first out. In C++, std::stack from the <stack> header gives you this behaviour with push, pop and top.

Why postfix helps

Infix notation needs rules to be read correctly. A reader has to know that * beats + and that brackets come first. Postfix notation has no such rules. Each operator simply takes the two values that sit directly before it in the list.

Here is a small example. Suppose the postfix string is 3 4 2 * +. Read it from left to right:

1. Put 3 aside.
2. Put 4 aside.
3. Put 2 aside.
4. The * takes the two most recent items, 4 and 2, and gives 8. The list is now 3, 8.
5. The + takes 3 and 8 and gives 11.

Nothing in that process needs a precedence rule. The order of the symbols already says what to do. A computer can therefore evaluate postfix with one stack, and that is what makes postfix useful.

The shunting-yard method is the bridge. It takes infix text, which people write, and produces postfix text, which machines find easy to process.

The idea: wait on a stack until it is safe

Read the infix expression from left to right, one token at a time. Keep two places:

• an output list, where finished tokens go in postfix order
• an operator stack, where operators wait

The key idea is that an operator cannot go to the output yet if a tighter-binding operator is still waiting for its right operand. For example, in 3 + 4 * 2, the + must wait until the * has been written out. The + sits on the stack while 4 and 2 are read.

Each token is handled in one of these ways:

1. Operand (a number or a name). Write it to the output at once. Operands never need to wait.
2. Opening bracket (. Push it onto the operator stack. It acts as a marker that separates what is inside the brackets from what is outside.
3. Closing bracket ). Pop operators from the stack and write them to the output until you pop the matching (. Throw the ( away. It does not appear in the output.
4. Operator. Before you push it, pop and write out every operator on top of the stack that binds at least as tightly. Stop when the top is a ( or when the top binds less tightly. Then push the new operator.
5. End of input. Pop everything left on the stack and write it to the output.

Step 4 has two parts that people often forget. First, "at least as tightly" means equal precedence also counts. That is what makes 8 - 3 - 2 work left to right. Second, the rule stops at (. An operator outside the brackets must not be popped while we are still inside them.

The name of the method comes from how it looks. Operators are shunted, or moved aside, onto a stack and later sent to the output in a new order, like trains moved between tracks on a railway yard.

Worked example 1: a + b * c - d

This example uses names instead of numbers. Names are easier to read in the output because each one appears once. Every row in the table shows the state after one token has been handled.

Look at the - row closely. Two operators were waiting. The * was on top and binds tighter than -, so it goes out. Then the + goes out, because + and - have equal precedence and the earlier operator must finish first. The - then waits on the stack for d.

The result is a b c * + d -. Read it with the rule from earlier. b c * gives b * c. Then a and that product go into +, giving a + b * c. Then d goes into -, giving (a + b * c) - d. That matches the original expression.

Worked example 2: brackets change the order

Now try (a + b) * c. Here the brackets must make the + happen first.

1. ( is pushed. Stack: (.
2. a is written. Output: a.
3. + is pushed. The top is (, so nothing is popped. Stack: +, (.
4. b is written. Output: a b.
5. ) pops until (. The + is written. The ( is removed. Output: a b +. Stack: empty.
6. * is pushed onto the empty stack. Stack: *.
7. c is written. Output: a b + c.
8. End of input pops *. Output: a b + c *.

The + was written before * because the closing bracket forced it out. Without the brackets, the * would have been on the stack first and the output would have been different.

Worked example 3: numbers, brackets and a longer run

The last example uses numbers, which is closer to what a user types. Take 3 + 4 * (2 - 1). The answer should be 3 + 4 * 1 = 7.

Here is the program that does the conversion. It reads the expression, splits it into tokens, and converts it. The trace flag prints the state after each token, so you can compare the output with the table above.

#include <cctype>
#include <iostream>
#include <stack>
#include <stdexcept>
#include <string>
#include <vector>
 
bool is_operator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}
 
int precedence(char op) {
    if (op == '*' || op == '/') return 2;
    if (op == '+' || op == '-') return 1;
    return 0;
}
 
std::vector<std::string> tokenize(const std::string& text) {
    std::vector<std::string> tokens;
    std::size_t i = 0;
    while (i < text.size()) {
        const auto c = static_cast<unsigned char>(text[i]);
        if (std::isspace(c)) {
            ++i;
        } else if (std::isalnum(c)) {
            std::string word;
            while (i < text.size() && std::isalnum(static_cast<unsigned char>(text[i]))) {
                word += text[i];
                ++i;
            }
            tokens.push_back(word);
        } else if (is_operator(text[i]) || text[i] == '(' || text[i] == ')') {
            tokens.push_back(std::string(1, text[i]));
            ++i;
        } else {
            throw std::invalid_argument(std::string("unknown character '") + text[i] + "'");
        }
    }
    return tokens;
}
 
std::string join(const std::vector<std::string>& parts) {
    std::string result;
    for (std::size_t i = 0; i < parts.size(); ++i) {
        if (i > 0) result += ' ';
        result += parts[i];
    }
    return result;
}
 
void print_step(const std::string& token, const std::vector<std::string>& output,
                std::stack<char> ops) {
    std::string stack_text;
    while (!ops.empty()) {
        stack_text += ops.top();
        ops.pop();
    }
    std::cout << "  token " << token << "  output: [" << join(output) << "]"
              << "  stack (top first): [" << stack_text << "]\n";
}
 
std::vector<std::string> to_postfix(const std::vector<std::string>& tokens, bool trace) {
    std::vector<std::string> output;
    std::stack<char> ops;
 
    for (const std::string& tok : tokens) {
        if (tok == "(") {
            ops.push('(');
        } else if (tok == ")") {
            while (!ops.empty() && ops.top() != '(') {
                output.push_back(std::string(1, ops.top()));
                ops.pop();
            }
            if (ops.empty()) {
                throw std::invalid_argument("unmatched ')'");
            }
            ops.pop();  // throw away the "("
        } else if (tok.size() == 1 && is_operator(tok[0])) {
            const char op = tok[0];
            while (!ops.empty() && ops.top() != '(' &&
                   precedence(ops.top()) >= precedence(op)) {
                output.push_back(std::string(1, ops.top()));
                ops.pop();
            }
            ops.push(op);
        } else {
            output.push_back(tok);  // an operand goes straight to the output
        }
 
        if (trace) {
            print_step(tok, output, ops);
        }
    }
 
    while (!ops.empty()) {
        if (ops.top() == '(') {
            throw std::invalid_argument("unmatched '('");
        }
        output.push_back(std::string(1, ops.top()));
        ops.pop();
    }
    return output;
}
 
int main() {
    const std::vector<std::string> examples = {
        "a + b * c - d",
        "(a + b) * c",
        "a - b - c",
        "3 + 4 * (2 - 1)",
        "a + b)",
        "(a + b",
        "a + $ b",
    };
 
    for (const std::string& text : examples) {
        std::cout << "infix:   " << text << "\n";
        try {
            const bool trace = (text == examples[0]);
            if (trace) {
                std::cout << "trace:\n";
            }
            const auto postfix = to_postfix(tokenize(text), trace);
            std::cout << "postfix: " << join(postfix) << "\n\n";
        } catch (const std::invalid_argument& e) {
            std::cout << "error:   " << e.what() << "\n\n";
        }
    }
    return 0;
}

Compile and run it:

g++ -std=c++20 -Wall -Wextra -o shunting shunting.cpp && ./shunting

The output is:

infix:   a + b * c - d
trace:
  token a  output: [a]  stack (top first): []
  token +  output: [a]  stack (top first): [+]
  token b  output: [a b]  stack (top first): [+]
  token *  output: [a b]  stack (top first): [*+]
  token c  output: [a b c]  stack (top first): [*+]
  token -  output: [a b c * +]  stack (top first): [-]
  token d  output: [a b c * + d]  stack (top first): [-]
postfix: a b c * + d -
 
infix:   (a + b) * c
postfix: a b + c *
 
infix:   a - b - c
postfix: a b - c -
 
infix:   3 + 4 * (2 - 1)
postfix: 3 4 2 1 - * +
 
infix:   a + b)
error:   unmatched ')'
 
infix:   (a + b
error:   unmatched '('
 
infix:   a + $ b
error:   unknown character '$'

The trace matches the table in worked example 1. Each line shows the output list and the operator stack after one token. The stack (top first) label means the first character printed is the one that will be popped next.

Check the last postfix string by hand. 2 1 - comes first and gives 1, so the list is now 3, 4, 1. Then * takes 4 and 1 to give 4, and + takes 3 and 4 to give 7. The brackets are gone because the postfix order already says that 2 - 1 happens before the multiplication.

The a - b - c line shows the associativity rule. The second - pops the first one before it is pushed, so the output is a b - c -, which means (a - b) - c.

Worked example 4: a longer expression

Take a * b - c / (d + e) * f. It uses every rule in one line. The table lists the operator stack with its top first, as in worked example 1.

Two rows need a closer look. On the ) row, the + inside the brackets is written first, and the ( is removed. The / below the bracket stays on the stack, because the loop stopped at the (. On the * row, the / goes out before the * is pushed. The two operators have equal precedence, and the / came first, so it must finish first. The - underneath stays, because it binds less tightly than *.

The program prints the same postfix string for this input.

Checking a postfix string

A binary operator takes two operands, and every operator in this lesson is binary. A complete postfix expression of binary operators always has one more operand than operators. That gives a quick test. The string a b + c * has three operands and two operators, so it passes. The string a b + c from the missing-final-pop mistake below has three operands and one operator, so it fails. It is missing an operator.

The count does not check the order. The string a c b + * also passes, but it means a * (c + b), which is different from (a + b) * c. Use the count to catch missing symbols, and use a trace like the tables above to check the order.

Common mistakes

Using > where >= is needed. The rule is "pop while the top binds at least as tightly". If you write a strict comparison, equal operators stay on the stack, and subtraction and division come out in the wrong order. Here is the output of the same program with > in the comparison, for the input a - b - c:

infix:   a - b - c
postfix: a b c - -

The output a b c - - means a - (b - c). That is a different value from (a - b) - c. To check a rule like this, try a case where the two operators are equal, such as 8 - 3 - 2.

Forgetting the final pop. When the input ends, operators can still be waiting on the stack. If the loop that writes them out is missing, the operators disappear. Here is the output of a version of the program with the final loop turned off:

infix:   (a + b) * c
postfix: a b + c

The * is lost, and no error is printed, so the wrong answer looks like a normal result. Write the final loop as a separate step that always runs, and test an expression that ends with an operator on the stack.

Popping through a (. The loop in step 4 must stop at (. The program checks for it explicitly, and it also gives ( the precedence 0, lower than any operator. Without that stop, an operator outside the brackets could be written before the expression inside them is finished.

Writing the bracket into the output. Brackets only control the order. They do not produce a postfix token. If ( or ) shows up in the output, the postfix string contains symbols that no evaluator knows how to read.

Mismatched brackets. Two real messages come from the program when the brackets do not match:

error:   unmatched ')'
error:   unmatched '('

The first comes from a + b), where a ) finds no ( on the stack. The second comes from (a + b, where the input ends while a ( is still waiting. Read the message to find which bracket is missing, then look at the input for the matching one.

Forgetting to include the header. std::stack lives in <stack>. Here is the start of the real compiler message from a small program that uses std::stack without that include. The compiler prints more lines after these:

nostack.cpp: In function ‘int main()’:
nostack.cpp:4:10: error: ‘stack’ is not a member of ‘std’
    4 |     std::stack<int> s;
      |          ^~~~~
nostack.cpp:2:1: note: ‘std::stack’ is defined in header ‘<stack>’; this is probably fixable by adding ‘#include <stack>’

The note gives the fix. Add #include <stack> at the top of the file.

Practice

Exercise 1. Convert a * b + c to postfix by hand. Write the stack after each token.

Show the answer

The output is a b * c +. The * is pushed first. When the + arrives, the * binds tighter, so it is popped and written before the + is pushed. The + then waits for c, and it is popped at the end.

Exercise 2. Convert a * (b + c) to postfix by hand.

Show the answer

The output is a b c + *. The * is pushed first. The ( goes on top of it, so the + does not pop the *. The ) pops the + and removes the (. At the end the * is popped.

Exercise 3. Convert 10 - 4 - 3 to postfix. Then check whether your answer matches the value 3 by reading the postfix from left to right.

Show the answer

The output is 10 4 - 3 -. The second - pops the first - before it is pushed, because the two operators have equal precedence. Read it left to right: 10 4 - gives 6, then 6 3 - gives 3, which is the same as (10 - 4) - 3.

Exercise 4. Explain why the program prints unmatched '(' for the input a + (b * c, and say what changes in the output if you remove the final loop from to_postfix in the program.

Show the answer

The input ends while the ( is still on the stack. The final loop finds a ( and stops with that message. The program only reaches that check inside the final loop, so removing the loop removes the message too. The input would then return a result with the operators missing, and no error.

Exercise 5. Write the postfix string for 12 + (3 * 45), then list the tokens that tokenize returns for the same input.

Show the answer

The postfix string is 12 3 45 * +. The tokens are 12, +, (, 3, *, 45, ). The number 12 is one token, not two, because tokenize keeps reading letters and digits until it finds something else.

Summary

• Postfix puts each operator after its operands, so it needs no precedence rules to read.
• The shunting-yard method writes operands to the output at once and holds operators on a stack until they are safe to write.
• An operator pops every operator on top of the stack that binds at least as tightly, and stops at (.
• Brackets control the order and never appear in the output.
• Equal precedence pops on the left, which keeps subtraction and division left to right.