[Leetcode 2021 刷题计划] 224. 基本计算器

发布于

每日一题时间: 2020-03-10 题目链接: 224. 基本计算器 官方题解链接: 基本计算器

题目

实现一个基本的计算器来计算一个简单的字符串表达式 s 的值。

代码语言：txt
复制
示例 1：
输入：s = "1 + 1"
输出：2

示例 2：

输入：s = " 2-1 + 2 "

输出：3


示例 3：

输入：s = "(1+(4+5+2)-3)+(6+8)"

输出：23

提示：

  • 1 <= s.length <= 3 * 105
  • s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
  • s 表示一个有效的表达式

解题方法

当看到题目和难度以为会有加减乘除和括号等，原本想要用分治法来解决。对括号进行分割成一个个子串。

由于只含有加减法和括号, 并不需要考虑运算优先级的问题，仅有由于括号外符号对括号内符号的影响。所以只需要考虑括号外符号对括号内符号的反转。

栈

代码语言：txt
复制
class Solution {

public:

int calculate(string s) {

stack<int> ops;

ops.push(1);

// 可能会产生用例边界

// 例如 A + B - C < INT_MAX

// 但 A + B > INT_MAX

long res = 0;

int i = 0, N = s.size(), sign = 1;

while (i < N) {

if (s[i] == ' ') {

i++;

} else if (s[i] == '+') {

sign = ops.top();

i++;

} else if (s[i] == '-') {

sign = -ops.top();

i++;

} else if (s[i] == '(') {

ops.push(sign);

i++;

} else if (s[i] == ')') {

ops.pop();

i++;

} else {

long num = 0;

while (i < N && s[i] >= '0' && s[i] <= '9') {

num = num * 10 + s[i] - '0';

i++;

}

res += sign * num;

}

}

return res;

}

};
  • 复杂度分析
    • 时间复杂度：O(N)
    • 空间复杂度: O(N)

参考资料

  1. 224. 基本计算器
  2. 基本计算器

#leetcode