Shuntingyard

Shunting-yard algorithm, often called the shunting-yard, is a method for parsing mathematical expressions written in infix notation. It converts such expressions into postfix notation (Reverse Polish) or into an abstract syntax tree. The algorithm was developed by computer scientist Edsger W. Dijkstra in 1961 as part of his work on expression parsing. It is widely used in calculators and compiler front ends to transform human-friendly expressions into a form that can be efficiently evaluated.

The algorithm uses two data structures: a stack for operators and an output list for the resulting sequence. It reads tokens from left to right. If a token is an operand, it is appended to the output. If it is a function, it is pushed on the stack. If it is an operator, the algorithm pops operators from the stack to the output while they have higher precedence or equal precedence with left associativity, then pushes the current operator. If a left parenthesis is encountered, it is pushed onto the stack; if a right parenthesis is encountered, operators are popped to the output until the matching left parenthesis is removed. After processing all tokens, any remaining operators on the stack are moved to the output. The resulting postfix expression can be evaluated by a simple stack-based evaluator.

Extensions of the basic algorithm handle unary operators, functions with arguments, and varying operator precedence. Some variants construct an abstract syntax tree directly instead of producing postfix notation. The method operates in linear time with respect to the length of the input and uses linear extra space.

Example: transforming the infix expression 3 + 4 * 2 / (1 – 5) ^ 2 ^ 3 yields the postfix form 3 4 2 * 1 5 - 2 3 ^ ^ / +, assuming ^ is right-associative.