4. Transform the Expression

Transform the algebraic expression with brackets into RPN 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 RPN form (no expressions like a*b*c).

Input

t [the number of expressions <= 100]
expression [length <= 400]
[other expressions]

Text grouped in [ ] does not appear in the input file.

Output

The expressions in RPN form, one per line.

Example

Input:
3
(a+(b*c))
((a+b)*(z+x))
((a+t)*((b+(a+c))^(c+d)))

Output:
abc*+
ab+zx+*
at+bac++cd+^*

Basic Algorithm:

the algorithm is pretty simple Every operation has a binding weight, with + and - being the lowest. There are two rules:

• print out numbers immediately
• never put a lighter item on a heavier item
• left parentheses go on the stack
• right parentheses pop off the stack until you hit a left parentheses, and then remove the left parentheses

Code based on that:

A

PS: i have solved it for any given expression as per sun you need to take input and iterate it as per the user want it to and then get the output 

import java.util.Stack;

public class reversePolishExp

{

public static String Infix2(String input)

{

char[] in = input.toCharArray();

Stack<Character> stack = new Stack<Character>();

StringBuilder out = new StringBuilder();

for (int i = 0; i < in.length; i++)

switch (in[i]) {

case '+':

case '-':

while (!stack.empty() && (stack.peek() == '*' || stack.peek() == '/')) {

out.append(' ');

out.append(stack.pop());

}

out.append(' ');

stack.push(in[i]);

break;

case '*':

case '/':

out.append(' ');

stack.push(in[i]);

break;

case '(':

stack.push(in[i]);

break;

case ')':

while (!stack.empty() && stack.peek() != '(') {

out.append(' ');

out.append(stack.pop());

}

stack.pop();

break;

default:

out.append(in[i]);

break;

}

while (!stack.isEmpty())

out.append(' ').append(stack.pop());

return out.toString();

}

public static void main (String args[])

{

// reversePolishExp exp = new reversePolishExp();

String man=reversePolishExp.Infix2("(a+b)*(c+d)");

System.out.print(man);

}

}