Shunting yard

the shunting yard algorithm

Invented by Edsger Dijkstra

This is a way to parse infix (1 + 1) notation and convert it to postfix/RPN (1 1 +) which is easier to interpret cuz no order of operations.

All of this info is from the wikpedia article but it wasnt really clear to me so im rewriting it. I'm skipping over functions and right associating operators cuz idrk what it is and i dont need it :)

Ok so for the algorithm there are 2 stacks, the output stack and operator stack

• You go token by token.
• if the token is a number, push it to the output
• if its an operator:
• • remove the operators at the top of the stack if they have the same or higher precedence and add them to the output
• • add the operator to the opstack (AFTER step 1)
• if its an open paren push it to the operator stack
• if its a close paren, add all the operators to the output until it reaches the open paren, remove the open paren
• at the end add all the operators to the output (FILO i think since its a stack)

pretty simple and neat!