Basic Calculator

问题：

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

思路：

　　栈的经典应用

我的代码：

public class Solution {
    private Stack<Character> opers = new Stack<Character>();
    private Stack<Integer> values = new Stack<Integer>();
    public int calculate(String s)
    {
        if(s== null || s.length()==0)    return 0;
        char[] tokens = s.toCharArray();
        for(int i=0; i<tokens.length; i++)
        {
            char c = tokens[i];
            if(c == ' ') continue;
            else if(c<='9' && c>='0')
            {
                int result = 0;
                while(i<tokens.length && tokens[i] >='0' && tokens[i] <='9')
                {
                    result = result*10 + (tokens[i]-'0');
                    i++;
                }
                values.push(result);
                i--;
            }
            else if(c == '(') opers.push(c);
            else if(c == ')')
            {
                while(!opers.isEmpty() && opers.peek() != '(')
                    values.push(applyOp(opers.pop(), values.pop(), values.pop()));
                opers.pop();
            }
            else
            {
                while(!opers.isEmpty() && hasPrecedence(c, opers.peek()))
                {
                    values.push(applyOp(opers.pop(), values.pop(), values.pop()));
                }
                opers.add(c);
            }
        }
        while (!opers.empty())
        {   
            values.push(applyOp(opers.pop(), values.pop(), values.pop()));
        }
        return values.pop();
    }

    public static boolean hasPrecedence(char op1, char op2)
    {
        return op2 == '(' || op2 == ')' ? false : true; 
    }
    public static int applyOp(char op, int b, int a)
    {
        switch (op)
        {
            case '+':
                return a + b;
            case '-':
                return a - b;
        }
        return 0;
    }

}

View Code

学习之处：

最近不好的习惯有点多啊，差评，得改正啊
最近做题的习惯也不好，懒的动脑子，就想着看答案，早点AC。
这道题的收获有两个地方：

　　（1）对于在一次循环里面，需要用之前的结果的问题，不要试图单纯的for就解决问题，也可以尝试用两个for，因为用两个for时间复杂度上不会增加，而且更加简练，何乐而不为呢。

        for(int i=0; i<tokens.length; i++)
        {
            char c = tokens[i];
            if(c == ' ') continue;
            else if(c<='9' && c>='0')
            {
                int result = 0;
                while(i<tokens.length && tokens[i] >='0' && tokens[i] <='9')
                {
                    result = result*10 + (tokens[i]-'0');
                    i++;
                }
                values.push(result);
                i--;
            }

　　（2）对于条件特别多的判断，如本题里面的出现的字符是（还是+还是-，不要求毕其功于一役，每一个条件都拿出来，都做不同的处理，更好一些，毕其功于一役代码好看，但是同样很容易把自己弄晕了。