Part 12 of 17 in Stacks & Queues  

Infix to Postfix Conversion by phantom11

Problem statement

As the problem title says, you are given a string S in infix form which you need to convert to postfix form. The expression contains operands from the set of uppercase English alphabets, operators from the set {+,-*,/}. Also there may be rounded parentheses '()' in the expression. There will be no other character in the string. The operators have the following properties:

  • Expressions within brackets are always evaluated first.
  • Multiplication(*) and Division(/) have the same precedence. Similarly, Addition(+) and Subtraction(-) have same precedence. But, + and / have higher precedence than + and -.
  • All operators have left to right associativity.

Input & Output

The first line contains the number of test cases T (≤ 50). Each of the next T lines contains a string S (|S| ≤ 100), which is in infix form and contains characters as described above. The given expression will always be a valid infix expression.

For each test case output one line which is the postfix form for the given expression. Note that parentheses are not printed in the postfix form.

Sample Input
2
A*(B+C)
(X*Y+Z)
Sample Output
ABC+*
XY*Z+


To try out your code



Sign in

Sign up