/Shunting-Yard-Algorithm--CSharp

Primary LanguageC#

Shunting Yard Algorithm - C#

The Shunting Yard Algorithm is a method for parsing arithmetical or logical expressions, or a combination of both, specified in infix notation. It can produce a postfix notation string, also known as Reverse Polish notation.

What are the rules?

  • Expressions are parsed left to right.
  • Each time a number or operand is read, we push it to the stack.
  • Each time an operator comes up, we pop the required operands from the stack, perform the operations, and push the result back to the stack.
  • We are finished when there are no tokens (numbers, operators, or any other mathematical symbol) to read. The final number on the stack is the result.
Operator Precedence Associativity
^ 4 Right
× 3 Left
÷ 3 Left
+ 2 Left
− 2 Left

What is the logic of the algorithm?

  While there are tokens to be read:
       Read a token
        ->If it's a number add it to queue
        ->If it's an operator
               While there's an operator on the top of the stack with greater precedence:
                       Pop operators from the stack onto the output queue
               Push the current operator onto the stack
        ->If it's a left bracket push it onto the stack
        ->If it's a right bracket 
            While there's not a left bracket at the top of the stack:
                     Pop operators from the stack onto the output queue.
             Pop the left bracket from the stack and discard it
 While there are operators on the stack, pop them to the queue

Example

Input: 3 + 4 × 2 ÷ ( 1 − 5 ) ^ 2 ^ 3

Token Action Output
(in RPN) 		Operator
stack 		Notes
3 Add token to output 3
+ Push token to stack 3 +
4 Add token to output 3 4 +
× Push token to stack 3 4 × + × has higher precedence than +
2 Add token to output 3 4 2 × +
÷ Pop stack to output 3 4 2 × + ÷ and × have same precedence
Push token to stack 3 4 2 × ÷ + ÷ has higher precedence than +
( Push token to stack 3 4 2 × ( ÷ +
1 Add token to output 3 4 2 × 1 ( ÷ +
− Push token to stack 3 4 2 × 1 − ( ÷ +
5 Add token to output 3 4 2 × 1 5 − ( ÷ +
) Pop stack to output 3 4 2 × 1 5 − ( ÷ + Repeated until "(" found
Pop stack 3 4 2 × 1 5 − ÷ + Discard matching parenthesis
^ Push token to stack 3 4 2 × 1 5 − ^ ÷ + ^ has higher precedence than ÷
2 Add token to output 3 4 2 × 1 5 − 2 ^ ÷ +
^ Push token to stack 3 4 2 × 1 5 − 2 ^ ^ ÷ + ^ is evaluated right-to-left
3 Add token to output 3 4 2 × 1 5 − 2 3 ^ ^ ÷ +
end Pop entire stack to output 3 4 2 × 1 5 − 2 3 ^ ^ ÷ +

Output: 3 4 2 × 1 5 − 2 3 ^ ^ ÷ +