Expression Evaluator

Lab Java Advanced 30 points

Evaluate infix expressions with + - * / and parentheses on integers (integer division), using the shunting-yard algorithm with two stacks. Tokens are separated by spaces. Print the result of each expression.

Input

n, then n expressions.

Output

n results.

Example

Input

4
2 + 3 * 4
( 2 + 3 ) * 4
100 / ( 2 + 3 ) - 7
8 - 3 - 2

Output

Sample input available Sample output available

Editor

Java

Hints

Operators wait on a stack until an operator of lower or equal precedence arrives.

Applying equal precedence left-to-right makes 8 - 3 - 2 equal 3.

Solution explanation

Shunting-yard (Dijkstra, 1961) is how calculators and compilers handle operator precedence.

Show solution

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class Main {
    static int prec(String op) {
        return op.equals("+") || op.equals("-") ? 1 : 2;
    }

    static void apply(Deque<Long> values, String op) {
        long b = values.pop(), a = values.pop();
        switch (op) {
            case "+": values.push(a + b); break;
            case "-": values.push(a - b); break;
            case "*": values.push(a * b); break;
            default: values.push(a / b);
        }
    }

    static long evaluate(String expr) {
        Deque<Long> values = new ArrayDeque<>();
        Deque<String> ops = new ArrayDeque<>();
        for (String t : expr.trim().split("\\s+")) {
            if (t.equals("(")) {
                ops.push(t);
            } else if (t.equals(")")) {
                while (!ops.peek().equals("(")) apply(values, ops.pop());
                ops.pop();
            } else if ("+-*/".contains(t)) {
                while (!ops.isEmpty() && !ops.peek().equals("(") && prec(ops.peek()) >= prec(t)) {
                    apply(values, ops.pop());
                }
                ops.push(t);
            } else {
                values.push(Long.parseLong(t));
            }
        }
        while (!ops.isEmpty()) apply(values, ops.pop());
        return values.pop();
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine().trim());
        for (int i = 0; i < n; i++) {
            System.out.println(evaluate(sc.nextLine()));
        }
    }
}

Output

Answer