[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

0 人点赞