Shunting-yard Algorithm and Implementaion in Java

The Shunting Yard algorithm was developed by Edsger Dijkstra as a means to parse an infix mathematical expression into Reverse Polish notation (postfix).

Here is an step-by-step image for A+B*C-D from wiki.


A simplified version of the Shunting-yard algorithm (complete version)
  • For all the input tokens [S1]:
    • Read the next token [S2];
    • If token is an operator (x) [S3]:
      • While there is an operator (y) at the top of the operators stack and either (x) is
        left-associative and its precedence is less or equal to that of (y), or (x) is right-associative
        and its precedence is less than (y) [S4]:

        • Pop (y) from the stack [S5];
        • Add (y) output buffer [S6];
      • Push (x) on the stack [S7];
    • Else If token is left parenthesis, then push it on the stack [S8];
    • Else If token is a right parenthesis [S9]:
      • Until the top token (from the stack) is left parenthesis, pop from the stack to the output buffer [S10];
      • Also pop the left parenthesis but don’t include it in the output buffer [S11];
    • Else add token to output buffer [S12].
  • While there are still operator tokens in the stack, pop them to output [S13]

Note: [SN] Relate with code.

Here is a simple implementaion in Java :