# Algorithms for Processing Arithmetic Expressions

### Postfix evaluation algorithm

input:  a list of tokens representing an expression in postfix form
Output:  a number representing the value of that expression

Create a work stack.  It will be a stack of numbers.
While there are more tokens in the input
Get the next token
If the token is a number, push it onto the stack
If the token is an operator
Pop the stack twice, getting two operands
Apply the operator to the two operands, in the correct order
Push the result onto the stack
Pop the stack to get the value of the expression

### Infix-to-postfix algorithm (without parentheses)

Input:  a list of tokens representing an infix expression
Output:  a list of tokens representing the equivalent postfix expression
Make a new empty list for the tokens in postfix order.
Create a work stack.  It will be used as a stack of operators.
While there are more tokens to read from the infix list
Get the next token
If the token is a number, add it to the postfix list
If the token is an operator,
While the stack is not empty and the top item on the stack has greater or equal priority than the token
Pop an operator from the stack and add it to the postfix list
Push the token onto the stack
While there are more tokens on the stack
Pop them one at a time and add them to the postfix list

### Infix-to-postfix algorithm (with parentheses)

Input:  a list of tokens representing an infix expression
Output:  a list of tokens representing the equivalent postfix expression

Make a new empty list for the tokens in postfix order.
Create a work stack.  It will be used as a stack of operators.
While there are more tokens to read from the infix list
Get the next token
If the token is a number, add it to the postfix list
If the token is a left parenthesis, push it onto the stack
If the token is a right parenthesis,
While the top item on the stack is not a left parenthesis,
Pop an operator from the stack and add it to the postfix list
Pop the left parenthesis from the top of the stack and discard it
If the token is an operator,
While the stack is not empty and the top item on the stack is not a left parenthesis and the top item on the stack has greater or equal priority than the token
Pop an operator from the stack and add it to the postfix list
Push the token onto the stack
While there are more tokens on the stack
Pop them one at a time and add them to the postfix list