Shunting-Yard
How to write a formula parser
Shunting Yard is a place where people reassemble and reorder the cargos of trains and the shunting-yard algorithm describes a similar process when dealing with liner text (usually mathematical input) which contains operators, arguments, and brackets. It is the fundamental algorithm of calculators, and it can be further generalized to operator precedence parsing.
Reversed Polish notation (RPN) and abstract syntax tree (AST)
Our traditional math input is called infix notation, which put binary operators like $+-*/$ in between the two arguments.
It is convention of infix notation that makes brackets necessary (manually specify the order beca. For example the equivalent postfix form of
can be writen in postfix forn (or RPN)
There is no ambiguity, each operator from right hand will take previous two numbers as arguments. If any of the token is not number, it will take the output of the operator as input
can be written as
How to evaluate the RPN?
- Read from left to right
- If encounter a binary-operator of which the previous two tokens are numbers, evaluate the result and replace the three tokens with the result.
- Continue to read to right until the string is totally evaluated