Shunting Yard Algorithm

The shunting yard algorithm is a method for parsing arithmetical or logical expressions written in infix notation, producing either a postfix reverse Polish notation string or an abstract syntax tree. It was invented by Edsger Dijkstra, first published in November 1961 and named for its resemblance to the operation of a railroad shunting yard; it is stack-based, reads each input symbol in order, correctly parses all valid infix expressions though it does not reject every invalid one, and was later generalized into operator-precedence parsing.