import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;

// Copyright (c) 2018 Ryan Greene
public class Parser {

    private static Stack<ParseToken> stack;
    private static Queue<String> remainingTokens;
    private static final Runnable[][] table;
    private static final int[][] reductionTable;
    private static boolean accepted = false;

    static {
        table = new Runnable[12][128];
        for (int state : new int[]{0, 4, 6, 7}) {
            table[state]['n'] = () -> shift(5);
            table[state]['('] = () -> shift(4);
        }
        table[1]['+'] = () -> shift(6);
        table[1]['-'] = () -> shift(6);
        table[1]['$'] = Parser::accept;
        for (char c : new char[]{'+', '-', ')', '$'})
            table[2][c] = () -> reduce('E', 'T');
        table[2]['*'] = () -> shift(7);
        table[2]['/'] = () -> shift(7);
        for (char c : new char[]{'+', '-', '*', '/', ')', '$'})
            table[3][c] = () -> reduce('T', 'F');
        for (char c : new char[]{'+', '-', '*', '/', ')', '$'})
            table[5][c] = () -> reduce('F', 'n');
        table[8]['+'] = () -> shift(6);
        table[8]['-'] = () -> shift(6);
        table[8][')'] = () -> shift(11);
        for (char c : new char[]{'+', '-', ')', '$'})
            table[9][c] = () -> reduce('E', 'E', 'T', '+', '-');
        table[9]['*'] = () -> shift(7);
        table[9]['/'] = () -> shift(7);
        for (char c : new char[]{'+', '-', '*', '/', ')', '$'})
            table[10][c] = () -> reduce('T', 'T', 'F', '*', '/');
        for (char c : new char[]{'+', '-', '*', '/', ')', '$'})
            table[11][c] = Parser::reduceParentheses;

        reductionTable = new int[12][128];
        reductionTable[0]['E'] = 1;
        reductionTable[0]['T'] = 2;
        reductionTable[0]['F'] = 3;
        reductionTable[4]['E'] = 8;
        reductionTable[4]['T'] = 2;
        reductionTable[4]['F'] = 3;
        reductionTable[6]['T'] = 9;
        reductionTable[6]['F'] = 3;
        reductionTable[7]['F'] = 10;
    }

    public static void main(String[] args) {
        try {
            System.out.println("Valid Expression = " + parse(args[0]) + ".");
        } catch (final Exception e) {
            System.out.println("Invalid Expression");
        }
    }

    private static void shift(int state) {
        String token = remainingTokens.poll();
        int tokenValue = token.matches("\\d+") ? Integer.parseInt(token) : -1;
        stack.push(new ParseToken(tokenValue == -1 ? token.charAt(0) : 'n', state, tokenValue));
        print();
    }

    private static void reduce(char to, char from) {
        ParseToken token = stack.pop();
        if (from != token.symbol)
            throw new IllegalStateException();
        int state = stack.peek().state;
        stack.push(new ParseToken(to, reductionTable[state][to], token.value));
        print();
    }

    private static void reduce(char to, char operand1, char operand2, char operator1, char operator2) {
        ParseToken operandToke1 = stack.pop(), operatorToke = stack.pop(), operandToke2 = stack.pop();
        if (operatorToke.symbol != operator1 && operatorToke.symbol != operator2 || (operandToke1.value == -1
                || operandToke2.value == -1) || (operandToke2.symbol != operand1 || operandToke1.symbol != operand2))
            throw new IllegalStateException();
        int value = 0;
        if (operatorToke.symbol == '+')
            value = operandToke2.value + operandToke1.value;
        else if (operatorToke.symbol == '-')
            value = operandToke2.value - operandToke1.value;
        else if (operatorToke.symbol == '*')
            value = operandToke2.value * operandToke1.value;
        else if (operatorToke.symbol == '/')
            value = operandToke2.value / operandToke1.value;
        stack.push(new ParseToken(to, reductionTable[stack.peek().state][to], value));
        print();
    }

    private static void reduceParentheses() {
        ParseToken rightParentheses = stack.pop(), eToken = stack.pop(), leftParentheses = stack.pop();
        if (leftParentheses.symbol != '(' || rightParentheses.symbol != ')' || eToken.symbol != 'E')
            throw new IllegalStateException();
        stack.push(new ParseToken('F', reductionTable[stack.peek().state]['F'], eToken.value));
        print();
    }

    private static void accept() {
        if (stack.size() == 2 && remainingTokens.poll().equals("$"))
            accepted = true;
        else
            throw new IllegalStateException();
    }

    private static void print() {
        stack.forEach(System.out::print);
        System.out.print("\t\t");
        remainingTokens.stream().map(t -> t + " ").forEach(System.out::print);
        System.out.println();
    }

    private static int parse(String expression) {
        stack = new Stack<>();
        stack.push(new ParseToken('-', 0, -1));

        remainingTokens = new LinkedList<>();
        StringTokenizer tokenizer = new StringTokenizer(expression.endsWith("$") ? expression : expression + "$",
                "+-*/()$", true);
        while (tokenizer.hasMoreTokens())
            remainingTokens.offer(tokenizer.nextToken());

        accepted = false;
        while (!accepted) {
            String token = remainingTokens.peek();
            table[stack.peek().state][token.matches("\\d+") ? 'n' : token.charAt(0)].run();
        }
        return stack.pop().value;
    }

    private static class ParseToken {
        final char symbol;
        final int state;
        final int value;

        ParseToken(char symbol, int state, int value) {
            this.symbol = symbol;
            this.state = state;
            this.value = value;
        }

        @Override
        public String toString() {
            return symbol == 'n' ? "[" + value + ":" + this.state + "]" : "[" + symbol + ":" + this.state + "]";
        }
    }
}