题解 | #表达式求值#

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

1. 使用两个栈 ops保存操作，val保存数值
2. 对字符串进行遍历，如果字符为数字，则将连续的数放入val栈，
3. 否则，字符只可能为括号或操作，
4. 如果ops栈为空或者当前字符为(或者ops栈顶元素为(，则入栈；
5. 否，则如果当前字符为''，因为''优先级比+，-高，所以向后移一位直接将后面连续的数与栈顶元素和val栈顶元素相乘放入val栈；
6. 否，则如果当前字符为），+，-，末尾，则将val中的两个数进行ops栈顶的操作，将结果进栈；
7. 此时，栈顶元素可能为+，-，*，
8. 如果当前字符为),那么将(也弹出栈，如果已到结尾，则直接退出循环。
9. val栈顶元素即为最终结果。