题解 | #表达式求值#

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */

    // 从s1中取两个值，从vv中取一个操作符 来运算
    void fun(stack<int>& s1, vector<char>& vv, int& top)
    {
        int right = s1.top();
        s1.pop();
        int left = s1.top();
        s1.pop();
        if (vv[top] == '+')
            s1.push(left + right);
        else if (vv[top] == '-')
            s1.push(left - right);
        else
            s1.push(left * right);
        top--; // 删除使用了的操作符
    }

    int solve(string s) {
        // write code here
        int size = s.size();
        stack<int> s1; // 数字的栈
        vector<char> vv(size); // 操作符的栈
        int top = -1;
        for (int i = 0;i<size;i++) {
            if (s[i] == '(') // 直接插入即可
                vv[++top] =s[i] ;
            else if (s[i] == '*') { // ‘(’之前的‘*’全部输出
                while (top != -1) {
                    if (vv[top] == '*') {
                        fun(s1, vv, top);
                    }
                    else
                        break;
                }
                vv[++top] = s[i];
            }
            else if (s[i] == '+' || s[i] == '-') {
                // 把‘（’之前的操作符全部输出
                while (top != -1) {
                    if (vv[top]!='(') {
                        fun(s1, vv, top);
                    }
                    else
                        break;
                }
                vv[++top] = s[i];
            }
            else if (s[i] == ')')
            {
                // 把左括号之前的全部出栈
                while (top != -1)
                {
                    if (vv[top] != '(')
                    {
                        fun(s1, vv, top);
                    }
                    else
                    {
                        top--;
                        break;
                    }
                }
            }
            else // 插入数字栈中
            {
                // 可能有多位数
                int num = s[i]-'0';
                while (i + 1 < size && s[i + 1] >= '0' && s[i + 1] <= '9')
                {
                    num = num * 10 + s[i + 1] - '0';
                    i++;
                }
                s1.push(num);
            }
        }
        fun(s1, vv, top);
        return s1.top();
    }
};

首先要了解中缀表达式的求解过程。

需要两个栈，一个存操作数，用stl中的stack来实现，一个存操作符，用vector<char>来实现，方便读取数据。

然后依次遍历，如果遇到操作数，则压入s1中，遇到操作符，则需要考虑。

如果此操作符为'*'号，则输出左括号之前的全部为'*'号的操作符，这里直接调用fun函数即可。

如果为'+' || '-' ，则需要将左括号之前的操作符全部输出。

如果为')' 则需要将'('之前的操作符输出，并且最终将'('也输出。

如果为'('，则直接压入栈中即可。

最后注意字符串的数字可能不是一位的，所以在插入数字时需要看一看后一位是否也是数字。