题解 | #表达式求值#

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

    vector<int> function(string s,int index){
        stack<int> ms;
        int num=0;
        int i=0;
        char op = '+';
        for(i=index;i<s.size();i++){
            if(isdigit(s[i])){
                num = s[i]-'0'+ num*10 ;
c
            }
            if(s[i]=='('){
                vector<int> res = function(s, i+1);
                num = res[0];
                i=res[1];
                if(i!=s.size()-1) continue;
            }
            switch (op) {
                case '+':
                    ms.push(num);
                    break;
                case '-':
                    ms.push(-num);
                    break;
                case '*':
                    int temp = ms.top();
                    ms.pop();
                    ms.push(temp*num);
                    break;
            }
            num=0; 
            if(s[i]==')') break;
            else op=s[i];
        }
        int sum=0;
        while(!ms.empty()){
            sum+=ms.top();
            ms.pop();
        }
        return vector<int> {sum,i};
    }

    int solve(string s) {
        // write code here
        return function(s,0)[0];
    }
};

有一种延迟的思想。

一开始如果是数字，那么就会一直依靠sum=sum*10 + s[i]-'0'累加，并且保存在num里面。

如果运算符号是+or-，把num里面的数字push到栈里面，在下一个运算符号的时候进行计算；如果最后一个数字没有计算符号了，就不执行下面的语句，继续后续的operator此操作，完成+-*，再压入栈内。值得注意的是，乘法的实现需要先从栈里pop一个元素，与当前num相乘之后再push回去。

            if(i!=s.size()-1){
                continue;
            }

经过运算之后，栈内的元素进行相加就能得到最后的结果了。

以上部分没有考虑到小括号。小括号使用递归进行处理，当字符串中出现'('时，递归进入该函数计算，直到出现')'。其实我感觉'('和')'可以算作是一个运算符，负责得到一个新的num，这个时候应该跟出现符号的处理方式相同，即：如果不是最后一个字符，那么就到下个字符后压入栈内；若是最后一个字符，按前面的操作符号跟前面的栈元素进行运算。