PotD4.java

import java.util.Stack;
import java.util.HashMap;
import java.io.*;

public class PotD_4 {

    public static void main(String[] args) throws IOException {
		HashMap<String, Integer> compare;
		compare = new HashMap<>();
		compare.put("+", 1);
		compare.put("-", 1);
		compare.put("*", 2);
		compare.put("/", 2);
		compare.put("(", 5);
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int i = Integer.parseInt(br.readLine());
		for (; i-- > 0;) {
			Stack<String> output = new Stack<String>(), operator = new Stack<String>(), other = new Stack<String>();
			int temp;
			boolean num = true, success = true;
			for (String val : br.readLine().split("\\s")) {
				if (val.matches("\\d+")) {
					if (num) {
						output.push(val);
						num = false;
					} else {
						success = false;
						break;
					}
				} else if (val.equals(")")) {
					try {
						num = true;
						while (!"(".equals(output.push(operator.pop())))
							;
						output.pop();
					} catch (Exception e) {
						success = false;
						break;
					}
				} else if (compare.containsKey(val)) {
					num = true;
					temp = compare.get(val);
					try {
						while (temp <= compare.get(operator.peek())
								&& !operator.peek().equals("(")
								&& !operator.isEmpty()) {
							output.push(operator.pop());
						}
					} catch (Exception e) {
					}
					operator.push(val);
				} else {
					success = false;
					break;
				}
			}
			if (!success) {
				System.out.println("-1");
				continue;
			}
			while (!operator.isEmpty()) {
				if ("(" == output.push(operator.pop())) {
					success = false;
					break;
				}
			}
			if (!success) {
				System.out.println("-1");
				continue;
			}
			String current;
			int a, b;
			while (!(output.isEmpty())) {
				other.push(output.pop());
			}
			output = other;
			while (!output.isEmpty()) {
				try {
					current = output.pop();
					if (compare.containsKey(current)) {
						a = Integer.parseInt(operator.pop());
						b = Integer.parseInt(operator.pop());
						switch (current) {
						case "+":
							operator.push(a + b + "");
							break;
						case "-":
							operator.push(b - a + "");
							break;
						case "*":
							operator.push(a * b + "");
							break;
						case "/":
							operator.push(b / a + "");
							break;
						}
					} else {
						operator.push(current);
					}
				} catch (Exception e) {
					success = false;
					break;
				}
			}
			if (operator.size() != 1)
				success = false;
			if (!success) {
				System.out.println("-1");
				continue;
			}
			System.out.println(operator.pop());
		}
	}
}