题解 | #表达式求值#

/**
     *       思路：
     *         每到一个符号，就把前面可以计算出的值计算出来，使用 符号栈OperatorStack和数字栈numberStack
     *         需要判断前后俩个符号来进行下一步动作
     *         operatorNow代表现在指向的运算符号，lastOperator表示上一个运算符号
     *         if operatorNow == '*' 
     *             if lastoperator == '+'|| lastOperator == '-'
     *                不进行任何操作
     *             if lastOperator == '*"
     *                计算lastOperator左右的两个数字(a * b,其中*是上一个*而不是现在指向的*)
     *         if  operatorNow == '+' || operatorNow == '-' 
     *             if lastOperator == '+' || lastOperator == '-' || lastOperator == '*'
     *               计算lastOperator左右的两个数字
     *         if operatorNow == '('
     *            入符号栈
     *         if operatorNow == ')'
     *            把括号里的值计算出来，括号里的值就两种情况：
     *                1.括号里最末尾的符号是*，那就先计算*，然后前面可能还有个+或-号待处理，再计算+或-
     *                2.括号里最末尾的符号是-或+，那括号里现在一定就只有两个操作数，
     *         
     *         
     *         **tips:因为每个值都被算出来了，所以每个算式在读到末尾时，只有两种情况
     *              1.两个数纯+-
     *              2.先+或-然后再*一个数
     */
    public int solve (String s) {
        // write code here
        //建立两个栈
        /*
        +,-时，
        括号里的东西看成一个数，每次到)括号结尾时，此括号的值必须被计算出来。
        */
        if (s==null||s.length()==0){
            return 0;
        }
        Deque<Character> operatorStack = new LinkedList<Character>();
        Deque<Integer> numberStack = new LinkedList<Integer>();

        int startIndex = 0;
        int p = 0 ;
        char charNow;
        while(p<s.length()){
            charNow = s.charAt(p);
            if (charNow>='0'&&charNow<='9'){
                startIndex = p;
                while( p<s.length()&&(charNow>='0'&&charNow<='9')){
                    p++;
                    if(p<s.length()){
                        charNow = s.charAt(p);
                    }
                }
                numberStack.push(Integer.valueOf(s.substring(startIndex,p)));
            }
            //s[p]非数字
            else{
                if (charNow == ')') {
                    while(operatorStack.size()>0&&operatorStack.peek() != '('){
                        calculate(operatorStack,numberStack);
                    }
                    operatorStack.pop();
                    //*(a+b)：括号前是+号的情况
                    //calculateFormer(operatorStack,numberStack);
                }
                else if(charNow == '+'||charNow == '-') {
                    calculateFormer(operatorStack,numberStack);
                    operatorStack.push(charNow);
                }
                else if(charNow == '*') {
                    if (operatorStack.size()>0&&operatorStack.peek() == '*') {
                        calculate(operatorStack,numberStack);
                    }
                    operatorStack.push(charNow);
                }
                else if(charNow == '('){
                    operatorStack.push(charNow);
                }
                p++;
            }
        }
        calculateFormer(operatorStack,numberStack);
        if(operatorStack.size()!=0){
            System.out.println("wrong");
        }
        return numberStack.pop();
    }
    public void calculate(Deque<Character> operatorStack,Deque<Integer> numberStack){
        if(operatorStack.size()>0){
            char operatorNow = operatorStack.peek();
            if(operatorNow == '+' ||operatorNow == '-'||operatorNow == '*'){
                operatorStack.pop();
                int num2 = numberStack.pop();
                int num1 = numberStack.pop();
                if(operatorNow == '+') {
                    numberStack.push(num1+num2);
                }
                else if(operatorNow == '-'){
                    numberStack.push(num1-num2);
                }
                else if(operatorNow == '*') {
                    numberStack.push(num1*num2);
                }
            }

        }
    }

    public void calculateFormer(Deque<Character> operatorStack,Deque<Integer> numberStack){
        if(operatorStack.size()>0&&operatorStack.peek() == '*'){
            calculate(operatorStack,numberStack);
        }
        if(operatorStack.size()>0&&(operatorStack.peek() == '+' || operatorStack.peek() == '-')){
            calculate(operatorStack,numberStack);
        }
    }