227. Basic Calculator II

问题描述：

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

Example 1:

Input: "3+2*2"
Output: 7

Example 2:

Input: " 3/2 "
Output: 1

Example 3:

Input: " 3+5 / 2 "
Output: 5

Note:

• You may assume that the given expression is always valid.
• Do not use the eval built-in library function.

解题思路：

这道题相对来说并没有特别复杂：对于正整数的加减乘除操作，且不包含括号。

需要注意的就是 * / 两个操作符的优先级不同。

我用deque存储了操作数和操作符：最后结果只存储最低优先级即 + - 的。

在遍历字符串时：

　　1. 跳过所有的空格

　　2. 判断当前是数字还是操作符

　　　　- 如果是数字，将字符串转化成数字后（这里一定要考虑字符串转化成的数字是否可能会溢出）判断之前的操作符是否为* /，如果是的话，弹出操作符与操作数进行计算

　　　　- 如果是符号，直接压入deque尾部

　　时间复杂度O(n) 实际上遍历两遍 n + n

　　空间复杂度O(n) 两个deque

代码：

class Solution {
public:
    int calculate(string s) {
        //traverse the string to get valid number
        //store the previous operand and operator
        deque<long> nums({0});
        deque<char> ops({'+'});
        int start = 0, end = 0;
        int n = s.size();
        while(start < n && end < n){
            //get valid number or operator
            while(start < n && s[start] == ' '){
                ++start;
                ++end;
            }
            if(isdigit(s[start])){
                while(++end < n && isdigit(s[end]));
                string str = s.substr(start, end-start);
                start = end;
                long num = stol(str);
                char lastSign = ops.back();
                long lastOp = nums.back();
                //std::cout << lastOp << " " << lastSign << " "<<  num <<std::endl;
                if(lastSign == '*'){
                    lastOp *= num;
                    ops.pop_back();
                    nums.pop_back();
                    nums.push_back(lastOp);
                }else if(lastSign == '/'){
                    lastOp /= num;
                    ops.pop_back();
                    nums.pop_back();
                    nums.push_back(lastOp);
                }else{
                    nums.push_back(num);
                }
                
            }else{
                //it should be operators
                char op = s[start];
                ++start;
                end = start;
                ops.push_back(op);
            }
        }
        long ret = nums.front();
        nums.pop_front();
        while(!nums.empty() && !ops.empty()){
            char sign = ops.front();
            ops.pop_front();
            int num = nums.front();
            nums.pop_front();
            if(sign == '+'){
                ret += num; 
            }else if(sign == '-'){
                ret -= num;
            }
        }
        return (int)ret;
    }
};

这里看到的O(1)的空间复杂度，简洁明了，可供参考

class Solution {
public:
    int calculate(string s) {
        int num = 0, t = 0, res = 0;
        char pre = '+';
        for (int i = 0; i < s.size(); i++) {
            if (isdigit(s[i])) {
                num = num * 10 + (s[i] - '0');
            }
            if (i == s.size() - 1 || !isdigit(s[i]) && s[i] != ' ') {
                switch (pre) {
                    case '+':
                        t += num;
                        break; 
                    case '-':
                        t -= num;
                        break;
                    case '*':
                        t *= num;
                        break;
                    case '/':
                        t /= num;
                        break;
                }
                if (s[i] == '+' || s[i] == '-' || i == s.size() - 1) {
                    res += t;
                    t = 0;
                }
                num = 0;
                pre = s[i];
            }
        }
        return res;
    }