Skip to content

Latest commit

 

History

History
71 lines (60 loc) · 5.01 KB

README.md

File metadata and controls

71 lines (60 loc) · 5.01 KB

Infix to Postfix

This converts the input expression from infix to postfix notation

The following Piet program resembles the Shunting Yard Algorithm

Program Map

Use this to follow the explanation below

Explanation

Note: Unfortunately Github markdown does not support HTML text coloring...

Input Reading / Initial Logic (Blue)

  1. Push 0 onto stack
  2. The start of the programs main while loop
    • First reads in a character (from now on reffered to as token), if no input left break out of loop and go to green 1, else go to blue 3
    • 2a - Ensures CC is set to left
  3. Push 48 (0) to stack to check if token is a digit or operator
  4. If token is an operator (or parenthesis) go to red
  5. Else token is a digit, so output the number and loop back to blue 2

Parenthesis Check (Red)

  1. Push 40 ('(') onto the stack, if token is left paren go to red 1a
    • 1a - Push left paren onto operator stack (which I define as everything below the 0 on stack) and continue to blue 2
    • Else, continue to red 2
  2. Push 41 (')') onto the stack, if token is right paren go to red 3
    • If token is not right paren, then token is an operator, go to red 4
  3. Pop value 'operator' from operator stack, if 'operator' is not left paren, output 'operator' and loop back to 3 by following 3a,b
    • If 'operator' is a left paren, break out of the 3 loop and go to red 5
  4. Line break to go to purple
  5. Go back to blue 2

Operator Stack Check (Purple)

  1. Roll stack to get the top element op1 from the operator stack (that we've maintained by keeping under the initial pushed 0), go to purple 2
    • 1a - Ensures CC is set to left
  2. Check if operator stack is empty, if empty go to purple 2a
    • 2a - Push token to the operator stack and continue back to blue 2
  3. Push 40 ('(') onto the stack, if op1 is left paren go to purple 3a
    • 3a - Push 'token' to the operator stack and continue back to blue 2
    • Else op1 is not left paren, so continue to orange

Operator Logic (Orange)

  1. Roll stack to place token on the top
  2. Push 42 ('*') onto the stack, if token is *, go to orange 4
  3. Else Push 47 ('/') onto the stack, if token is /, go to orange 4
    • Else token precedence is <= to that of op1, thus go to orange 7
  4. Roll stack to place op1 on the top
  5. Push 43 ('+') onto the stack, if op1 is +, go to orange 5a
    • Else, op1 is not +, go to orange 6
    • 5a - Roll stack to place token on the top, then Push token to the operator stack and continue back to blue 2
  6. Push 45 ('-') onto the stack, if op1 is -, go to orange 6a
    • 6a - Continue to orange 5a
  7. Roll stack to place op1 on the top, go to orange 8
  8. Output operator, continue to purple 1a

Post Input Processing (Green)

  1. Proceed down to green 2
  2. Roll stack to get the top element op1 from the operator stack. If op1 > 1 (meaning op1 exists and is not the initial pushed 0) go to green 2a
    • Else go to green 3
    • 2a - Stack is empty, program end
  3. Push 40 ('('), if op1 - 40 > 1 (meaning op1 is not left or right paren), go to green 4
    • Else op1 is a parenthesis, go to green 3a
    • 3a - Parenthesis should have been handled by red loop, so unmatched parens, input is not valid, output '?' and end program (green 3b)
  4. Output operator, continue to green 4a
    • 4a - Correct CC and go back to green 2

Limitations

Does not handle multi-digit numbers, negative numbers, or exponents in input.