Interview problem (Shunting-yard algorithm)

PolishParser.java

package petrglad;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Stack;

/**
 * Converts expession in infix notation with braces into polish (postfix)
 * notation with shunting-yard algorithm and evaulates it. Values are decimal
 * integers, operations are left associative. Example input:
 * "((4)+(3-50)**2)/21*32" (result is 3360).
 * 
 * @author petr
 */
public class PostfixParser {

    /**
     * Operation priorities.
     */
    final static Map<Character, Integer> priorities;

    static {
        priorities = new HashMap<Character, Integer>();
        priorities.put(')', 0);
        priorities.put('(', 1);
        priorities.put('+', 2);
        priorities.put('-', 2);
        priorities.put('*', 3);
        priorities.put('/', 3);
        priorities.put('^', 4); // Written as "**" in input text
    }

    public static void main(String[] args) throws IOException {
        String input = new BufferedReader(new InputStreamReader(System.in)).readLine();
        PostfixParser parser = new PostfixParser();
        System.out.println(parser.eval(parser.parse(input)));
    }

    /**
     * @return List of tokens in postfix notation
     */
    public List<String> parse(String input) {
        final List<String> result = new ArrayList<String>();
        final Stack<Character> opStack = new Stack<Character>();
        for (int pos = 0; pos < input.length(); pos++) {
            char ch = input.charAt(pos);
            if (Character.isDigit(ch)) {
                // Read integer
                int begin = pos;
                while (pos < input.length() && Character.isDigit(input.charAt(pos)))
                    pos++;
                result.add(input.substring(begin, pos));
                pos--;
            } else if (ch == '(')
                opStack.push(ch);
            else {
                char operation;
                if (ch == '*' && (pos < input.length() + 1) && input.charAt(pos + 1) == '*') {
                    operation = '^';
                    pos++;
                } else
                    operation = ch;

                if (operation == '(')
                    opStack.push(operation);
                else
                    while (!opStack.isEmpty()
                            && priorities.get(opStack.peek()) >= priorities.get(operation)) {
                        char top = opStack.pop();
                        if (top == '(')
                            break;
                        result.add(Character.toString(top));
                    }

                if (operation != ')')
                    opStack.add(operation);
            }
        }
        while (!opStack.isEmpty())
            result.add(Character.toString(opStack.pop()));
        return result;
    }

    int eval(Iterable<String> polishTokens) {
        final Stack<Integer> result = new Stack<Integer>();
        final Iterator<String> it = polishTokens.iterator();
        while (it.hasNext()) {
            String t = it.next();
            if (priorities.containsKey(t.charAt(0))) { // is operation token
                int right = result.pop();
                result.push(evalOperation(result.pop(), right, t));
            } else
                result.push(Integer.parseInt(t));
        }
        assert result.size() == 1;
        return result.pop();
    }

    int evalOperation(int left, int right, String operation) {
        switch (operation.charAt(0)) {
        case '+':
            return left + right;
        case '-':
            return left - right;
        case '*':
            return left * right;
        case '/':
            return left / right;
        case '^':
            return (int) Math.pow(left, right);
        default:
            throw new RuntimeException("Unknown operation '" + operation + "'");
        }
    }
}