The Shunting-Yard Algorithm (2011)

A few months ago I wanted to add arithmetic parsing to my game's debug console, and went with this approach.

While researching the area, I came across this exact blog post, and thought it was perfect. It explains things clearly and concisely (without even needing code/pseudocode). Granted, it's a simple algorithm, but this post was just so much nicer than any of the (higher ranked) results that Google gave me. And it has no ads!

It made me sad. Years ago, it seemed like Google helped me find lots of nice little pages like this one. It's much harder to find web articles of this quality anymore.

Back to this article specifically, I particularly appreciated the "Advanced Usage" section, where it briefly (and clearly!) goes over some useful extensions to the algorithm. These were very much on my mind (since I wanted parentheses and function calls). They are simple extensions to a simple algorithm, but it's nice to have them summarized for you before you dive in.

It was a breezy joy to implement (did it even take an hour?). And I can think of other easy ways to extend its capabilities further. This style of arithmetic parsing would be a wonderful thing for beginner programmers to cut their teeth on. It exposes them to a number of important computer/programming ideas, yet is simple to implement while also being directly useful.

Some limitations of this particular article:

* it doesn't mention that operator-precedence (usually: Pratt) parsing is another alternative

* it doesn't mention that you don't have to evaluate the expression directly; it's perfectly possible to output an AST, RPN, or some kind of minimal bytecode.

* unless you do a bit of optimization, you can't reduce the number of "registers" needed à la Schneider. While generally less relevant for interpreters unless you do some careful platform-dependent design, interpreters can easily benefit from the one-register case.

* you're allowed to use an ahead-of-time LR machine generator, you don't have to encode its tables by hand (but for simple grammars it's not actually that hard to work out with comments).

* it doesn't sufficiently mention that you really want to work with IDs in a lot of cases; among other things this avoids further unary/binary problems (though I suppose synthesizing an extra argument also works).

I've used that algorithm and extended it to handle distfix expressions[1]. For instance it can parse the expression

    1 + if true then 1 else a b + c

as (represented as an s-expr using some weird angle brackets):

    ⟨+ 1 ⟨if␣then␣else␣ true 1 ⟨+ ⟨a b⟩ c⟩⟩⟩

I thought it was cool and could be useful to a lot of simple use cases.

[1]: https://github.com/noteed/syntactical

I remember covering that at university, I don't think in too much depth, just enough that a few years later at my job I needed to do some parsing of equations and immediately knew the name of what I needed to use.

I then proceeded to extend it a little for my purposes (supporting functions iwth variable numbers of arguments) which was fun, and got a surprising amount of people showing up in the blog post comments: https://blog.kallisti.net.nz/2008/02/extension-to-the-shunti...

Back in the early 90s, I learned C from a book called "Illustrated C" (I forget the author) that taught C programming & internals pictorially, which strongly appealed to my brain.

One of the sections was an implementation of this algorithm, and it made me fall in love with programming and the power of well-designed algorithms.

A more succint presentation here: https://www.andreinc.net/2010/10/05/converting-infix-to-rpn-...

Besides being a relatively easy to understand parsing algorithm, it's also pretty efficient. We're using the Shunting-Yard for Sonic, our in-house .NET expression evaluation engine used in all of our simulation products.

Since performance is a major concern, we compared a lot of algorithms and frameworks and Shunting Yard really hits the spot being both fast and easy to grasp, producing maintainable code.

For anyone interested in seeing code, we recently open sourced Sonic: https://github.com/adletec/sonic

Interestingly, I've heard of this algorithm before as "Dijkstra's two-stack parsing algorithm," but not as the seemingly more common name of the "Shunting-yard algorithm."

An amusing factoid, you can evaluate the derivative of a postfix expression using a second stack and all of the freshman calculus rules including the chain rule and l'hopital's rule.

I implemented this algorithm for a hobby project around five years ago.

https://github.com/LoganDark/cpp-calculator/blob/315c3e9814e...

It was sort of butchered to try to handle function calls as well, but it's still kind of shunting-yard. It also doesn't handle unary operators well. But it worked for its original purpose, I suppose.

I implemented a variation long ago to parse regular expressions (regex) [0]. Albeit I did some pre parsing for things like character classes and lookarounds.

[0]: https://github.com/nitely/nim-regex/blob/5e447c329ce826deb61...

edit: added permalink

I've done recursive decent expression parsing a couple times in the past for simple expression. In the past year I had to implement a parser for Verilog. The operator precedence table has 18 levels of precedence!

Not only would writing 18 routines be a PITA, it would mean super deep and slow call stacks during expression evaluation. So I used the shunting yard algorithm.

Updated for 2023: if you attempt to implement this algorithm in a language or service area not approved by Dijkstra, it will return a scary copyright notice and refuse to work.

[edit] I've been told that this is only true in Poland, where reverse Polish notation is interpreted literally.

I implemented this algorithm when creating a language interpreter. It felt like magic when it worked!

In my case, I used it to build an AST, rather than evaluate the calculation.

I wrote my first calculator app 11 years ago using shunting yard algorithm. It’s a wonderful algorithm, hats off to Dijsktra for coming up with a simple and elegant algorithm.

I was hoping this might have some reference to the movie Society, but in the end I learned why they called it "shunting". I'll call that a net positive.

as always I wonder about (re?) posts of such old content, but given the algorithm in question itself is such a relic, maybe it’s fine

Adding my two cents, this is a really great little algo that I personally have implemented for the fun of it many times as a means of comparing languages to one another, really just for my own benefit. the kotlin instantiation was my fave thus far but I am overdue to revisit this in things like mojo and zig, so big +1

Making a calculator is one of the things I do when I learn a new language, and I always end up using this algorithm because it's the only one I know!

This post was an interesting one. I often get this problem in interviews, but never knew about this algorithm, so I implemented it and I love it!

I also found that it's super-easy to extend to support parentheses.

Some Ruby code to share if anyone would like to see it.

    PRECEDENCES = [
      ['+', '-'],
      ['*', '/']
    ]

    def precedence_of(operator)
      PRECEDENCES.find_index do |level_ops|
        level_ops.include?(operator)
      end
    end

    def lower_precedence(token, than:)
      precedence_of(token) < precedence_of(than)
    end

    def apply(operator, l, r)
      case operator
      when '+'
        l + r
      when '-'
        l - r
      when '*'
        l \* r
      when '/'
        l / r
      else
        raise Exception.new("Unknown operator #{operator}")
      end
    end

    def collapse(operators, operands, next_operator: nil)
      while !operators.empty? &&
          (next_operator.nil? ||
          lower_precedence(next_operator, than: operators.last))

        r = operands.pop()
        op = operators.pop()
        l = operands.pop()

        operands.push(apply(op, l, r))
      end
    end

    def expect_operator(token)
      if precedence_of(token).nil?
        raise Exception.new("Expected operator, got #{token.inspect}")
      end

      return token
    end

    def expect_operand(token)
      if token[/^\d+$/]
        return token.to_i
      end

      raise Exception.new(
        "Expected value or nested expression beginning with '(', instead got #{token.inspect}"
      )
    end

    def should_cons(str, char)
      return !str.nil? && str[/^\d+$/] && char[/^\d+$/]
    end

    loop do
      input = gets

      tokens = []

      input.chars.each do |char|
        if should_cons(tokens.last, char)
          tokens.push(tokens.pop() + char)
        else
          if char.strip.size > 0
            tokens.push(char)
          end
        end
      end
      
      puts tokens.inspect

      expect_value = true

      operators = []
      operands = []

      parentheses_stack = []

      tokens.each do |token|
        if expect_value
          if token == '('
            puts "PUSHING #{operators.inspect} #{operands.inspect}"
            parentheses_stack << [operators, operands]
            operators = []
            operands = []

            next
          else
            operand = expect_operand(token)
            operands << operand
          end
        else
          if token == ')'
            puts "COLLAPSING #{operators.inspect} #{operands.inspect}"
            collapse(operators, operands)
            result = operands.last
            puts "RESULT #{result.inspect}"

            operators, operands = parentheses_stack.pop()
            operands.push(result)
            puts "POPPING(+ pushing) #{operators.inspect} #{operands.inspect}"

            next
          else
            operator = expect_operator(token)

            puts "COLLAPSING #{operators.inspect} #{operands.inspect}"
            collapse(operators, operands, next_operator: operator)
            operators.push(operator)
          end
        end

        expect_value = !expect_value
      end

      collapse(operators, operands)

      puts operands.last
    end