SPOJ

ReversePolish.java

import java.io.*;
import java.util.*;

class ReversePolish {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            char[] arr = br.readLine().toCharArray();
            Stack<Character> operator = new Stack<Character>();
            StringBuilder sb = new StringBuilder();
            char p0 = '^';
            ArrayList<Character> p1 = new ArrayList<Character>();
            p1.add('*');
            p1.add('/');
            ArrayList<Character> p2 = new ArrayList<Character>();
            p1.add('+');
            p1.add('-');
            for (char a : arr) {
                if (a >= 'a' && a <= 'z') {
                    sb = sb.append(a);
                } else {
                    if (a == ')') {
                        while (!operator.isEmpty() && operator.peek() != '(') {
                            sb = sb.append(operator.pop());
                        }
                        operator.pop();
                    } else {
                        if (a == p0) {
                            operator.push(a);
                        } else if ((p1.contains(a) && p1.contains(operator.peek()))
                                || (p1.contains(a) && p2.contains(operator.peek()))) {
                            while ((!operator.isEmpty() && operator.peek() != '(')
                                    || (!operator.isEmpty() && operator.peek() == p0)) {
                                sb = sb.append(operator.pop());
                            }
                            operator.push(a);
                        } else if (p2.contains(a) && p2.contains(operator.peek())) {
                            while ((!operator.isEmpty() && operator.peek() != '(')
                                    || (!operator.isEmpty() && operator.peek() == p0)
                                    || (!operator.isEmpty() && p1.contains(operator.peek()))) {
                                sb = sb.append(operator.pop());
                            }
                            operator.push(a);
                        }
                        else{
                            operator.push(a);
                        }

                    }
                }
            }
            System.out.println(sb);
        }
    }
}