He’s an interesting albeit relatively easy problem from CodeChef.com:

———-

Reverse Polish Notation (RPN) is a mathematical notation where every operator follows all of its operands. For instance, to add three and four, one would write “3 4 +” rather than “3 + 4”. If there are multiple operations, the operator is given immediately after its second operand; so the expression written “3 − 4 + 5” would be written “3 4 − 5 +” first subtract 4 from 3, then add 5 to that.

Transform the algebraic expression with brackets into RPN form.

You can assume that for the test cases below only single letters will be used, brackets [] will not be used and each expression has only one RPN form (no expressions like a*b*c)

Input

The first line contains t, the number of test cases (less then 100).
Followed by t lines, containing an expression to be translated to RPN form, where the length of the expression is less then 400.

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+^*

———

My Solution

Most computer science students see this example in class while studying data structures, as you can solve this problem quite easily using a simple stack. You basically need to go through the original string, outputing letters as they come (since their order won’t change) and pushing operators into the stack. Then whenever you find a closing parentheses ‘)’ you pop and output everything on the stack until you find the matching opening parenthesis ‘(‘. I used Java because it already has a stack structure implemented (though implementing one is always fun and useful to polish your pointer skills).

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main{

  public static void main(String[] args){
    int i,j;
    j = 0;
    String x = "";

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    try{
      j = Integer.parseInt(br.readLine());
    }
    catch(IOException e){
      e.printStackTrace();
    }
    for(i=0;i<j;i++){
      try{
        x = br.readLine();
      }
      catch(IOException e){
        e.printStackTrace();
      }
      System.out.println(rpn(x));
    }    
  }

  public static String rpn(String x){
    String result = "";
    char c = 'a';
    int i;
    Stack<Character> s = new Stack<Character>();
    
    for(i=0;i<x.length();i++){
      c = x.charAt(i);
      if(c>='a'&&c<='z')
        result += c;
      else if(c==')'){
        while((c = s.pop())!='(')
          result += c;
      }
      else
        s.push(c);
    }
    return result;
  }

}