Convert infixed expression to postfix
Given that an arithmetic expression is properly form with respect to parentheses, do the following:
• Create an empty stack to hold any arithmetic operators and left parenthesis, ONLY.
• A string to contain the postfix expression - the output from this conversion.
• Scan the arithmetic expression from left to right.
• While the are more symbols in the arithmetic expression,
{
After a symbol is scanned, there are four (4) basic rules to observed and apply accordingly:
1. If the symbol is an operand (a number), write it to the output string.
2. If the symbol is an operator and if the stack is empty, push the symbol on the stack.
Otherwise, if the symbol is either '(' or ')', check for the following conditions:
If the symbol is '(', push on to the stack,
Otherwise
If the symbol is ')'
{
Pop everything from the operator stack down to the first '('. Write each item
popped from the stack to the output string. Do not write the item ')'. Discard it.
}
3. If the symbol scanned is an arithmetic operator, check for the following and apply accordingly:
If the operator on the top of the stack has higher or equal precedence, that operator is popped from off the stack, and is written to the to the output string. This process is continues until one of two things happen:
(a) Either the first '(' is encountered. When this occurs, the '(' is removed from the stack and is discarded, and the recently scanned symbol is placed on the stack
OR
(b) The operator on the stack has lower precedence than the one just scanned. When this situation arises, the recently scanned symbol is pushed onto the stack.
}
4. After the arithmetic expression is exhausted, any operator is remaining on the stack must be popped from off and is written to the output string.