224. Basic Calculator (Hard)

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

Example 1:

Input: "1 + 1"
Output: 2
Example 2:

Input: " 2-1 + 2 "
Output: 3
Example 3:

Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23
Note:
You may assume that the given expression is always valid.
Do not use the eval built-in library function.

我的答案：用stack

class Solution {
public:
    int calculate(string s) {
        s = "+(" + s + ")";
        // cout << s << endl;
        stack<int> sign({1});
        stack<int> value({0});
        
        unordered_map<char,int> type_map{
            {'+', 1}, {'-', -1}, {'(', 2}, {')', -2}
        };
        for (int i=0; i<10; ++i) {
            type_map[i] = 0;
        }
        
        int left = 0;
        int right = 0;
        int last_type = 3;
        for (int i=0; i<s.size(); ++i) {
            char c = s[i];
            if (c == ' ') {
                right = (last_type == 0)? i:-1;
                // cout << i << ": " << c << " is space, right is " << right << ", left is " << left << endl;
                continue;
            }
            
            int curr_type = type_map[c];
            // cout << i << ": " << c << ": " << curr_type << endl;
            if (last_type == 0 and curr_type != 0) {
                right = (right>left)? right:i;
                // cout << "[" << left << ", " << right << ")" << endl;
                // cout << s.substr(left, right-left) << endl;
                value.top() += stoi(s.substr(left, right-left))*sign.top();
                sign.pop();
            }
            if (last_type!= 0 and curr_type == 0) {
                left = i;
                if (abs(last_type) != 1) {
                    sign.push(1);
                }
            }
            if (abs(curr_type) == 1) {
                sign.push(curr_type);
            }
            if (curr_type == 2) {
                if (abs(last_type) != 1) {
                    sign.push(1);
                }
                value.push(0);
            }
            if (curr_type == -2) {
                int temp = value.top();
                value.pop();
                value.top() += temp*sign.top();
                sign.pop();
            }
                
            last_type = curr_type;
        }
        
        return value.top();
    }
};

Runtime: 32 ms, faster than 35.62% of C++ online submissions for Basic Calculator.
Memory Usage: 9.9 MB, less than 35.88% of C++ online submissions for Basic Calculator.

一遍过，开心！但是速度有点慢

主要是用stack存两个信息，一个是sign，一个是value
每个数结束之后要乘以sign，加到value的top上
每个括号结束的时候，要乘以sign，加到value的second top上，当前top pop出去

第一行处理了一下s成为s = "+(" + s + ")";，不然结尾

看了下答案：

// Author: Huahua
class Solution {
public:
  int calculate(string s) {    
    function<int(int&)> eval = [&](int& pos) {
      int ret = 0;
      int sign = 1;
      int val = 0;
      while (pos < s.size()) {
        const char ch = s[pos];
        if (isdigit(ch)) {
          val = val * 10 + (s[pos++] - '0');
        } else if (ch == '+' || ch == '-') {
          ret += sign * val;
          val = 0;
          sign = ch == '+' ? 1 : -1;
          ++pos;
        } else if (ch == '(') {
          val = eval(++pos);
        } else if (ch == ')') {          
          ++pos;
          break;
        } else {
          ++pos;
        }
      }
      return ret += sign * val;
    };
    int pos = 0;
    return eval(pos);
  }
};

8ms

我觉得我的代码比较慢的原因有2个，一个是其实是n^2，因为得回去看left right substring。小trick是用isdigit判断是否是0-9。

默写了一次：

class Solution {
public:
    int calculate(string s) {
        int pos = 0;
        return eval(pos, s);
    }
    int eval(int& pos, string& s) {
        int ret = 0;
        int val = 0;
        int sign = 1;
        while (pos < s.size()) {
            char c = s[pos];
            // cout << pos << " : " << c << endl;
            // cout << "sign = " << sign << ", val = " << val << ", ret = " << ret << endl;
            if (isdigit(c)) {
                val = val*10 + (c-'0');
                ++pos;
            }
            else if (c == '+' or c == '-') {
                ret += sign*val;
                val = 0;
                sign = (c == '+')? 1:-1;
                ++pos;
            }
            else if (c == '(') {
                ret += sign*eval(++pos, s);
            }
            else if (c == ')') {
                ++pos;
                return ret += val*sign;
            }
            else {
                ++pos;
            }
        }
        ret += val*sign;
        return ret;
    }
};

用recursion替代了写stack，sign也只需要当下的，pos是reference，所以是全局的index。处理结尾的方式是，在return之前再多做一次ret += val*sign;