跳到主要内容

Basic Calculator

描述​

TODO

分析​

典型的栈的题目，不过这道题属于hard级别，因为很难写对。

表达式中只有加减，没有乘除，那就不需要考虑优先级，于是这道题就变的简单很多了。我们需要一个栈来辅助计算，用个变量sign来表示当前的符号，遍历给字符串s，

  • 如果遇到了数字，就用while循环把之后的数字都读进来，然后用sign*num来更新结果res；
  • 如果遇到了加号，则sign赋为1；
  • 如果遇到了减号，则sign赋为-1；
  • 如果遇到了左括号，则把当前结果res和符号sign压入栈，res重置为0，sign重置为1；
  • 如果遇到了右括号，结果res乘以栈顶的符号，栈顶元素出栈，结果res加上栈顶的数字，栈顶元素出栈。

代码​

// Basic Calculator
// Time complexity O(n), space complexity O(n)
class Solution {
public:
    int calculate(const string& s) {
        int res = 0, sign = 1, n = s.size();
        stack<int> stk;
        for (int i = 0; i < n; ++i) {
            const char c = s[i];
            if (isdigit(c)) {
                int num = 0;
                while (i < n && isdigit(s[i])) {
                    num = 10 * num + (s[i++] - '0');
                }
                res += sign * num;
                --i;
            } else if (c == '+') {
                sign = 1;
            } else if (c == '-') {
                sign = -1;
            } else if (c == '(') {
                stk.push(res);
                stk.push(sign);
                res = 0;
                sign = 1;
            } else if (c == ')') {
                res *= stk.top(); stk.pop();
                res += stk.top(); stk.pop();
            }
        }
        return res;
    }
};

相关题目​