题目描述

实现一个简易的计算器，只包含正整数和+ - * / 和空格” “，不包含括号，输入一个字符串，计算它的值。

样例

输入："3+2*2"
输出：7

算法1

(栈) $O(n)$

这道题主要是需要考虑加减和乘除的优先级问题，用栈来处理，遇到加减就把数字压栈，遇到乘除就把栈顶弹出，与数字进行乘除处理。主要注意的是运算符是放在两个数字的中间，而我们想要的是在遇到运算符时，用于运算的两个数字已经被解析出来了，因此用sign来记录前一个运算符，在遇到一个新的运算符或者到字符串的结尾时再考虑对前一个运算符进行处理。

C++ 代码

class Solution {
public:
    int calculate(string s) {
        if(s.size()==0)
            return 0;
        int res = 0;
        stack<int>stk;
        int num = 0;
        char sign = '+';
        for(int i = 0;i<s.size();i++){
            if(s[i] >= '0' && s[i] <= '9'){
                num *= 10;
                num = num - '0' + s[i];
            }
            if((s[i]=='+'||s[i]=='-'||s[i]=='*'||s[i]=='/')||i==s.size()-1){
                if(sign=='+')
                    stk.push(num);
                if(sign=='-')
                    stk.push(-num);
                if(sign=='*'){
                    int topnum = stk.top();
                    stk.pop();
                    stk.push(num*topnum);
                }
                if(sign=='/'){
                    int topnum = stk.top();
                    stk.pop();
                    stk.push(topnum/num);
                }
                sign=s[i];
                num = 0;
            }
        }
        while(!stk.empty()){
            int topnum = stk.top();
            res += topnum;
            stk.pop();
        }
        return res;
    }
};