Infix to Postfix Converter (Shunting-Yard)

Understanding the Shunting-Yard Algorithm

First invented by computer science pioneer Edsger W. Dijkstra, the Shunting-Yard algorithm takes inspiration from a railroad switching yard: train cars (tokens) either proceed straight down the track (output queue) or are shunted aside onto a siding (operator stack) until tracks are clear.

Operator Precedence & Associativity Table

Operator	Description	Precedence Level	Associativity
^	Exponentiation / Power	4 (Highest)	Right-to-Left
*	Multiplication	3	Left-to-Right
/	Division	3	Left-to-Right
+	Addition	2	Left-to-Right
-	Subtraction	2 (Lowest)	Left-to-Right
(, )	Grouping Parentheses	Special	Non-associative

---

Step-by-Step Worked Example: 3 + 4 * 2 / ( 1 - 5 ) ^ 2

1. 3 $\rightarrow$ Operand $\rightarrow$ Output: 3
2. + $\rightarrow$ Push to stack: [+]
3. 4 $\rightarrow$ Operand $\rightarrow$ Output: 3 4
4. * $\rightarrow$ Higher precedence than + $\rightarrow$ Push to stack: [+, *]
5. 2 $\rightarrow$ Operand $\rightarrow$ Output: 3 4 2
6. / $\rightarrow$ Same precedence as *, left-associative: Pop * to output, push /: Stack [+, /], Output 3 4 2 *
7. ( $\rightarrow$ Push to stack: [+, /, ( ]
8. 1 $\rightarrow$ Output: 3 4 2 * 1
9. - $\rightarrow$ Push to stack: [+, /, (, -]
10. 5 $\rightarrow$ Output: 3 4 2 * 1 5
11. ) $\rightarrow$ Pop until (: Pop - to output, discard (: Stack [+, /], Output 3 4 2 * 1 5 -
12. ^ $\rightarrow$ Higher precedence than / $\rightarrow$ Push: Stack [+, /, ^]
13. 2 $\rightarrow$ Output: 3 4 2 * 1 5 - 2
14. End of expression $\rightarrow$ Pop remaining operators: Pop ^, pop /, pop +.

Final Postfix Output: 3 4 2 * 1 5 - 2 ^ / +