Basic Calculator

题目

Basic Calculator
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) {
        int ans = 0;
        // 2 sign
        vector<int> sign(2, 1);
        for (int i = 0; i < s.length();i++) {
            char c = s[i];
            if (isdigit(c)) {
                int n = 0;
                while (i < s.size() && isdigit(s[i]))
                    n = n * 10 + (s[i++] - '0');
                ans += sign.back() * n;
                sign.pop_back();
                i--;
            } else if (c == '(') {
                sign.pop_back();
            } else if (c == ' ') {
                sign.push_back(sign.back() * (c == '-' ? -1 : 1));
            }
        }
        return ans;
    }
};

例子

 remaining   sign stack      total
3-(2+(9-4))   [1, 1]            0
 -(2+(9-4))   [1]               3
  (2+(9-4))   [1, -1]           3
   2+(9-4))   [1, -1, -1]       3
    +(9-4))   [1, -1]           1
     (9-4))   [1, -1, -1]       1
      9-4))   [1, -1, -1, -1]   1
       -4))   [1, -1, -1]      -8
        4))   [1, -1, -1, 1]   -8
         ))   [1, -1, -1]      -4
          )   [1, -1]          -4
              [1]              -4

另一种解法

思路

• 括号内优先计算
• 碰到 ( ,将计算结果和操作符入栈
• 碰到数字就带着符号计算结果。

代码

class Solution {
public:
    int calculate(string s) {
        const int l = s.length();
        int sign = 1, ans = 0;
        stack<int> stk_;
        for (int i = 0; i < l; i++) {
            char c = s[i];
            if (isdigit(c)) {
                int d = c - '0';
                while (i+1 < l && isdigit(s[i+1])) {
                    d = d * 10 + (s[++i] - '0');
                }
                ans += d * sign;
            } else if (c == '+' || c == '-') {
                sign = c == '+' ? 1 : -1;
            } else if (c == '(') {
                stk_.push(ans);
                stk_.push(sign);
                ans = 0;
                sign = 1;
            } else if (c == ')') {
                ans *= stk_.top(); stk_.pop();
                ans += stk_.top(); stk_.pop();
            }
        }
        return ans;
    }
};