RPN and the Shunting Yard Algorithm - Swift Calculator Part 2

In Part 1, I shared my journey building a calculator in Swift. I explored NSExpression, hand-written recursive parsers, and ultimately landed on a more powerful and elegant solution: Reverse Polish Notation (RPN) with the Shunting Yard algorithm.

This post explains what these concepts are, why they work so well — and how to implement them in Swift.

Why Not Infix?

The way we usually write math is in infix notation:

3 + 4 * 2 / (1 - 5)

But this requires rules about:

• Operator precedence (multiplication before addition)
• Associativity (left-to-right or right-to-left)
• Parentheses

To evaluate it, a computer must constantly check what’s higher priority. This is where RPN shines.

What is Reverse Polish Notation (RPN)?

RPN writes operators after their operands. No parentheses. No ambiguity.

Infix:      3 + 4 * 2
RPN:        3 4 2 * +
Evaluates:  3 + (4 * 2) = 11

How does it work? You process the RPN tokens left to right with a stack:

1. Push numbers on the stack
2. When you see an operator, pop the last two numbers, apply the operator, and push the result

Example:

RPN: 3 4 + 2 *       (i.e., (3 + 4) * 2)
Stack steps:
- Push 3 → [3]
- Push 4 → [3, 4]
- '+' → pop 4 & 3 → push 7 → [7]
- Push 2 → [7, 2]
- '*' → pop 2 & 7 → push 14 → [14]
Result = 14

Enter: The Shunting Yard Algorithm

Invented by Edsger Dijkstra, the Shunting Yard algorithm converts infix → RPN.

Core idea:

We use:

• An output queue for the final RPN
• An operator stack to manage precedence and grouping

Precedence Rules:

Higher precedence:
    * /
Lower precedence:
    + -

Algorithm Flow (simplified):

1. Read tokens from the infix string:

   • If number → add to output queue
   • If operator → pop higher/equal-precedence ops to output, then push this operator
   • If ‘(’ → push to stack
   • If ‘)’ → pop from stack to output until ‘(’ is found

2. After reading all tokens, pop remaining operators from the stack to the output.

Example: (3 + 4) * 5

Step-by-step with stacks:

Final RPN: 3 4 + 5 * → Result: 35

Swift Implementation Summary

Here’s the key conversion logic in Swift:

func infixToRPN(_ infix: String) -> [String]? {
    var output: [String] = []
    var operatorStack: [Character] = []

    for (i, char) in infix.enumerated() {
        // Parse digits
        // Handle '(' and ')'
        // Handle operators with precedence checks
    }

    // Pop remaining operators
    return output
}

And for evaluation:

func evaluateRPN(_ rpn: [String]) -> Decimal? {
    var stack: [Decimal] = []

    for token in rpn {
        if let num = Decimal(string: token) {
            stack.append(num)
        } else if "+-*/".contains(token) {
            // Pop last 2 values, apply operator, push result
        }
    }

    return stack.first
}

Bonus Test Case

Try it yourself:

let expr = "(2 + 3) * (4 - 1)"

• RPN: 2 3 + 4 1 - *
• Result: 5 * 3 = 15

RPN is Awesome Because:

• It’s deterministic — no ambiguity
• No parentheses needed
• Easy to evaluate with a simple stack
• Ideal for calculator logic and compilers
• Surprisingly elegant once you get it

Conclusion

RPN may look weird at first, but it’s beautiful in its simplicity. And once you pair it with the Shunting Yard algorithm, you’ve got a rock-solid foundation for any math parser or calculator.

In my own Swift calculator app, this has made expression evaluation much more reliable, testable, and scalable.

Happy coding ✌️