LeetCode 224. 基本计算器

LeetCode 224. 基本计算器

思路：

使用两个栈来处理符号以及数字，如果是'(',我们直接压入栈op中，如果')'，我们一直计算到'('，然后记得把'('弹出栈，如果是数字，压入栈nums中。
接下来就是符号的情况，我们定义

        unordered_map<char,int> hash;
        hash['+'] = 1;
        hash['-'] = 1;
        hash['*'] = 2;
        hash['/'] = 2;

如果当前的符号优先级大于栈顶的符号，则压入栈中，
例如 2 + 3 * 5 这样计算的时候是先计算 3 * 5
如果当前符号的优先级小于栈顶的符号
例如2 * 3 + 5 要先计算栈顶的符号

ps：
这道题里面没有 * /号，所以比较好处理，但是我在这道题的代码里也加入了* / 号的情况，如果出现了其他的符号 比如^等，只需要在hash里面以及eval函数里面进行修改就可以了。

代码：

class Solution {
public:
    stack<int> nums;
    stack<char> op;


    void eval(){
        int b = nums.top();nums.pop();
        int a = nums.top();nums.pop();
        int c = op.top();op.pop();

        if(c == '+') nums.push(a + b);
        if(c == '-') nums.push(a - b);
        if(c == '*') nums.push(a * b);
        if(c == '/') nums.push(a / b);
    }

    int calculate(string s) {
        unordered_map<char,int> hash;
        hash['+'] = 1;
        hash['-'] = 1;
        hash['*'] = 2;
        hash['/'] = 2;
        int n = s.size();

        for(int i = 0;i < n;i++){
            auto c = s[i];
            if(c == ' ') continue;
            if(isdigit(c)){
                string num;
                num += c;
                int j = i + 1;
                while(j < n && isdigit(s[j])) num+=s[j++];
                nums.push(stoi(num));
                //cout<<num<<endl;
                i = j - 1;
            }
            else if(c == '(') op.push(c);
            else if(c == ')'){
                while(op.top() != '(') eval();
                op.pop();
            }
            //是符号
            else{
                //如果当前的符号优先级大于栈顶的符号，则压入栈中，
                //例如 2 + 3 * 5 这样计算的时候是先计算 3 * 5
                //如果当前符号的优先级小于栈顶的符号
                //例如2 * 3 + 5 要先计算栈顶的符号
                //是负数
                if (!i || s[i - 1] == '(' || s[i - 1] == '+' || s[i - 1] == '-')  // 特殊处理符号和正号
                    nums.push(0);
                while(op.size() && hash[c] <= hash[op.top()] && op.top() != '(') eval();
                op.push(c);
            }
            
        }
        while(op.size()) eval();
        return nums.top();
    }
};