|Hide textShow text Hide pseudo-codeShow pseudo-code|
Infix expressions are often translated into postfix form in which the operators appear after their operands. The advantage of the postfix notation is that it eliminates the parenthesis of the infix notation without violating the original semantics.
Transform the Infix expression into a Postfix expression using the stack as an auxiliary structure. Use the algorithm below.
Some addditional problems.
1. Scan the Infix Expression from left to right.
2. If the scannned character is an operand, copy it to the Postfix Expression.
3. If the scanned character is left parentheses, push it onto the stack.
4. If the scanned character is right parenthesis, the symbol at the top of the stack is popped off the stack and copied to the Postfix Expression. Repeat until the symbol at the top of the stack is a left parenthesis (both parentheses are discarded in this process).
5. If the scanned character is an operator and has a higher precedence than the symbol at the top of the stack, push it onto the stack.
6. If the scanned character is an operator and the precedence is lower than or equal to the precedence of the operator at the top of the stack, one element of the stack is popped to the Postfix Expression; repeat this step with the new top element on the stack. Finally, push the scanned character onto the stack.
7. After all characters are scanned, the stack is popped to the Postfix Expression until the stack is empty.