题解 | #表达式求值#

经典的中缀表达式求值。常用思路，将其转为后缀表达式，边转边求值。
后缀表达式的特点，遇到运算符则将前两个数拿出来运算，便于计算机计算。
这里简单描述一下算法过程：遍历字符串，当读到的是数字时，直接将其压入数字栈。当读到的是运算符时，若符号栈为空，则直接将其压入符号栈；若符号栈非空，则判断符号栈栈顶的运算符优先级，若其优先级大于等于读到的优先级，则将其出栈，并从数字栈弹出两个元素进行该运算，先弹出的为右操作数，后弹出的为左操作数，将结果压入数字栈。重复该操作，直到符号栈栈顶运算符的优先级小于读取的运算符，或符号栈空，则将读取的运算符压入符号栈。重复以上操作直到字符串读完。最后，若符号栈非空，则弹出栈顶元素，并从数字栈弹出两个元素来进行该运算。重复该操作直到符号栈空。弹出数字栈栈顶元素，即得结果。
注：本题中运算符优先级：')'<'+'='-'<'*'。左括号'('较为特殊，读到左括号时直接入栈，读到右括号时一直出栈直到一个左括号出栈。
最初遇到两个坑。一个是在判断运算符出栈条件时，优先级相等的运算符未出栈。这样就造成中缀表达式变为右结合，当算式运算中一直大于等于0时不会出现问题，而当其中出现负数减法时就会出错。如1-2-3，正常情况下左结合结果为-4，而右结合得到的结果时2。另一个坑是在遍历字符串数组时，最开始惯性思维默认了表达式中数字都是个位数，所以循环中每次仅读入1个字符。而提交的用例中有100+100的例子，这样数字栈就变成了先压入1，再压入0...最后改写了读入数据的逻辑，美中不足的是这样做会在循环体内改变循环控制变量i，容易出错。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    int solve(string s) {
        // write code here
        stack<char> sign;
        stack<int> num;
        for(int i = 0;i<s.length();i++){
            if(s[i] >= '0' && s[i] <= '9'){
                int rear = i;
                while((rear+1)<s.length() && s[rear+1] >= '0' && s[rear+1] <= '9'){
                    rear++;
                }
                int n = 0;
                for(int j=rear;j>=i;j--){
                    n += (s[j]-'0')*pow(10,(rear-j));
                }
                i = rear;
                num.push(n);
            }
            else if(sign.size() == 0 || s[i] == '*'|| s[i] == '('){
                sign.push(s[i]);
            }
            else if(s[i] == '+' || s[i] == '-'){
                while(1){
                    if(sign.size() == 0){
                        break;
                    }
                    if(sign.top() == '*'){
                        sign.pop();
                        int n2 = num.top();
                        num.pop();
                        int n1 = num.top();
                        num.pop();
                        num.push(n1*n2);
                    }
                    else if(sign.top() == '+'){
                        sign.pop();
                        int n2 = num.top();
                        num.pop();
                        int n1 = num.top();
                        num.pop();
                        num.push(n1+n2);
                    }
                    else if(sign.top() == '-'){
                        sign.pop();
                        int n2 = num.top();
                        num.pop();
                        int n1 = num.top();
                        num.pop();
                        num.push(n1-n2);
                    }
                    else{
                        break;
                    }
                }
                sign.push(s[i]);
            }
            else if(s[i] == ')'){
                while(1){
                    if(sign.size() == 0){
                        break;
                    }
                    else if(sign.top() == '('){
                        sign.pop();
                        break;
                    }
                    else if(sign.top() == '+'){
                        sign.pop();
                        int n2 = num.top();
                        num.pop();
                        int n1 = num.top();
                        num.pop();
                        num.push(n1+n2);
                    }
                    else if(sign.top() == '-'){
                        sign.pop();
                        int n2 = num.top();
                        num.pop();
                        int n1 = num.top();
                        num.pop();
                        num.push(n1-n2);
                    }
                    else if(sign.top() == '*'){
                        sign.pop();
                        int n2 = num.top();
                        num.pop();
                        int n1 = num.top();
                        num.pop();
                        num.push(n1*n2);
                    }
                }
            }
        }
        while(sign.size()!=0){
            if(sign.top() == '+'){
                sign.pop();
                int n2 = num.top();
                num.pop();
                int n1 = num.top();
                num.pop();
                num.push(n1+n2);
            }
            else if(sign.top() == '-'){
                sign.pop();
                int n2 = num.top();
                num.pop();
                int n1 = num.top();
                num.pop();
                num.push(n1-n2);
            }
            else if(sign.top() == '*'){
                sign.pop();
                int n2 = num.top();
                num.pop();
                int n1 = num.top();
                num.pop();
                num.push(n1*n2);
            }
        }
        return num.top();
    }
};