[LeetCode] Basic Calculator II

Problem:

Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, +, -, *, and / operators. The integer division should truncate toward zero.
You may assume that the given expression is always valid.
Some examples:
"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5
Note: Do not use the eval built-in library function.

Thinking:

和 #224 Basic Calculator思路基本一样，先转换为后缀式（postfix notation），然后计算后缀式的值，照抄了 #224 讨论区的一个支持*/的解法，那个链接的讲解很清楚。

（脑洞：这次是Leetcode全网第六个AC的，头一次排名这么靠前呢！虽然可以说是作弊了的T_T）

Java Code:

(ref:https://leetcode.com/discuss/39454/accepted-infix-postfix-based-solution-explaination-600ms)

public class Solution {
    int rank(char op){
        // the bigger the number, the higher the rank
        switch(op){
            case '+':return 1;
            case '-':return 1;
            case '*':return 2;
            case '/':return 2;
            default :return 0; // '(' 
        }
    }
    List<Object> infixToPostfix(String s) {
        Stack<Character> operators = new Stack<Character>();
        List<Object> postfix = new LinkedList<Object>();

        int numberBuffer = 0;
        boolean bufferingOperand = false;
        for (char c : s.toCharArray()) {
            if (c >= '0' && c <= '9') {
                numberBuffer = numberBuffer * 10 + c - '0';
                bufferingOperand = true;
            } else {
                if(bufferingOperand)
                    postfix.add(numberBuffer);
                numberBuffer = 0;
                bufferingOperand = false;

                if (c == ' '|| c == '\t')
                    continue;

                if (c == '(') {
                    operators.push('(');
                } else if (c == ')') {
                    while (operators.peek() != '(')
                        postfix.add(operators.pop());
                    operators.pop(); // popping "("
                } else { // operator
                    while (!operators.isEmpty() && rank(c) <= rank(operators.peek()))
                        postfix.add(operators.pop());
                    operators.push(c);
                }
            }

        }
        if (bufferingOperand)
            postfix.add(numberBuffer);

        while (!operators.isEmpty())
            postfix.add(operators.pop());

        return postfix;
    }

    int evaluatePostfix(List<Object> postfix) {
        Stack<Integer> operands = new Stack<Integer>();
        int a = 0, b = 0;
        for (Object s : postfix) {
            if(s instanceof Character){
                char c = (Character) s;
                b = operands.pop();
                a = operands.pop();
                switch (c) {
                    case '+': operands.push(a + b); break;
                    case '-': operands.push(a - b); break;
                    case '*': operands.push(a * b); break;
                    default : operands.push(a / b); 
                }
            }else { // instanceof Integer
                operands.push((Integer)s);
            }
        }
        return operands.pop();
    }

    public int calculate(String s) {
        return evaluatePostfix(infixToPostfix(s));
    }

}