PROBLEM LINK:
link:Contest
Author: verma888
DIFFICULTY: simple
PREREQUISITES: Data Structure
PROBLEM:
Convert the Infix expression with brackets into Postfix form (Reverse Polish Notation). Two-argument operators: +, -, *, /, ^ (priority from the lowest to the highest), brackets ( ). Operands: only letters: A,B,…,Z. Assume that there is only one Infix form.
EXPLANATION:
There is an algorithm to convert an infix expression into a postfix expression. It uses a stack; but in this case, the stack is used to hold operators rather than numbers. The purpose of the stack is to reverse the order of the operators in the expression. It also serves as a storage structure, since no operator can be printed until both of its operands have appeared.
In this algorithm, all operands are printed (or sent to output) when they are read. There are more complicated rules to handle operators and parentheses.Rules are
- Print operands as they arrive.
- If the stack is empty or contains a left parenthesis on top, push the incoming operator onto the stack.
- If the incoming symbol is a left parenthesis, push it on the stack.
- If the incoming symbol is a right parenthesis, pop the stack and print the operators until you see a left parenthesis. Discard the pair of parentheses.
- If the incoming symbol has higher precedence than the top of the stack, push it on the stack.
- If the incoming symbol has equal precedence with the top of the stack, use association. If the association is left to right, pop and print the top of the stack and then push the incoming operator. If the association is right to left, push the incoming operator.
- If the incoming symbol has lower precedence than the symbol on the top of the stack, pop the stack and print the top operator. Then test the incoming operator against the new top of stack.
- At the end of the expression, pop and print all operators on the stack. (No parentheses should remain.)
More details can be found here
AUTHOR’S AND TESTER’S SOLUTIONS:
link:Author’s Solution.