// --------------
// InfixEval.java
// --------------

import java.util.Stack;
import java.util.StringTokenizer;

final class InfixEval {
    /**
     * O(n) in space
     * O(n) in time
     * Precondition: s.length() > 0
     * Precondition: ((s.charAt(i) >= '0') && (s.charAt(i) <= '9')) || (s.charAt(i) == '[ +-*]')
     * expr -> expr + expr
     *      |  expr - expr
     *      |  expr * expr
     *      |  number
     */
    public static long eval (String s) {
        final StringTokenizer  st = new StringTokenizer(s);
        final Stack<Character> sc = new Stack<Character>();
        final StringBuilder    sb = new StringBuilder();
        while (st.hasMoreTokens()) {
            final String t = st.nextToken();
            final char   c = t.charAt(0);
            if (c == '(')
                continue;
            if (c == ')') {
                final char v = sc.pop();
                sb.append(v + " ");}
            else if ((c == '+') || (c == '-') || (c == '*'))
                sc.push(c);
            else
                sb.append(t + " ");}
        return PostfixEval.eval(sb.toString());}}

final class InfixEvalTest {
    public static void main (String[] args) {
        System.out.println("InfixEval.java");

        assert InfixEval.eval("( 2 + 3 )")                 ==   5;
        assert InfixEval.eval("( 2 - 3 )")                 ==  -1;
        assert InfixEval.eval("( 2 * 3 )")                 ==   6;
        assert InfixEval.eval("( ( ( 2 * 3 ) - 4 ) + 5 )") ==   7;
        assert InfixEval.eval("( 2 + ( 3 - ( 4 * 5 ) ) )") == -15;
        assert InfixEval.eval("( 23 + 45 )")               ==  68;

        System.out.println("Done.");}}