【算法题解】17. 实现一个包含“正负数和括号”的基本计算器

末蓝、 2024-03-26 15:48 74阅读 0赞

> 这是一道 **困难** 题。
> 
> 题目来自：[leetcode][]

### 题目 ###

给你一个字符串表达式 `s` ，请你实现一个基本计算器来计算并返回它的值。

**注意:** 不允许使用任何将字符串作为数学表达式计算的内置函数，比如 `eval()` 。

**提示：**

*  `s` 由数字、‘`+`’、‘`-`’、‘`(`’、‘`)`’、和 ’ ’ 组成
 *  `s` 表示一个有效的表达式
 *  ‘`+`’ 不能用作一元运算(例如， “`+1`” 和 “`+(2 + 3)`” 无效)
 *  输入中不存在两个连续的操作符
 *  每个数字和运行的计算将适合于一个有符号的 **32位** 整数

**示例 1：**

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

**示例 2：**

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

**示例 3：**

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

### 解题思路 ###

这道题是 [实现一个包含“加减乘除”的基本计算器][Link 1] 的扩展，在表达式中增加了 **括号 “(”, “)”** 和 **正负数**，但是删除了 “\***” 和 “/**”。

在原来的解题方法中补充以下几点：

1.  括号的处理：
    
     *  如果遇到**左括号**：直接压入操作符栈。
     *  如果遇到**右括号**：将操作符栈中左括号后面的所有操作符出栈，并与数字栈进行计算合并。
2.  正负数的处理：
    
     *  可以使用 **补0** 的思路，在正负数前面加一个“`0`”，将表达式转换为没有正负号的式子。

#### 那么如何确定“**+**”和“**-**”是代表算符还是正负号呢？ ####

1.  如果 “`+`”和“`-`” 是第一个非空字符，那么代表是正负号。
2.  如果 “`+`”和“`-`” 的前一个非空字符也是“`+`”或者“`-`”，那么代表是正负号。
3.  如果 “`+`”和“`-`” 的前一个非空字符是 **左括号** ，那么代表是正负号。

**注**：补0的思路只能用于加减法.

### 代码实现 ###

class Solution {
        
        private Deque<Integer> numStack = new LinkedList<>();
        private Deque<Character> optStack = new LinkedList<>();
    
        public int calculate(String s) {
        
            int n = s.length();
            boolean needZero = true;
            for(int i = 0; i < n; i++){
        
                char ch = s.charAt(i);
                if(this.isNumber(ch)){
        
                    int num = 0;
                    needZero = false;
                    while(i < n && this.isNumber(s.charAt(i))){
        
                        num = num * 10 + s.charAt(i) - '0';
                        i++;
                    }
                    numStack.push(num);
                    i--;
                }else if(ch == ' '){
        
                    continue;
                }else if(ch == '('){
        
                    optStack.push('(');
                    needZero = true;
                    continue;
                }else if(ch == ')'){
        
                    while(optStack.peek() != '('){
        
                        this.calc(numStack, optStack);
                    }
                    // 删除左括号
                    optStack.pop();
                    needZero = false;
    
                }else{
        
                    if(needZero){
        
                        numStack.push(0);
                    }
                    while(!optStack.isEmpty() && optStack.peek() != '('){
        
                        this.calc(numStack, optStack);
                    }
                    optStack.push(ch);
                    needZero = true;
                }
            }
    
            while(!optStack.isEmpty()){
        
                this.calc(numStack, optStack);
            }
            return numStack.pop();
    
        }
    
        private boolean isNumber(char ch){
        
            return ch >= '0' && ch <= '9';
        }
    
    
        private void calc(Deque<Integer> numStack, Deque<Character> optStack){
        
            int num2 = numStack.pop();
            int num1 = numStack.pop();
            char opt = optStack.pop();
            if(opt == '+'){
          
                numStack.push(num1 + num2);
            }else{
        
                numStack.push(num1 - num2);
            }
    
        }
    
    }

### 复杂度分析 ###

时间复杂度： O ( N ) O(N) O(N)，N 为字符串长度。

空间复杂度： O ( N ) O(N) O(N)，N 为字符串长度。

[leetcode]: https://leetcode.cn/problems/basic-calculator/description/
[Link 1]: https://mp.weixin.qq.com/s?__biz=MzU1OTYwMjk1OQ==&mid=2247486181&idx=1&sn=c1eaa7f121762fed4c48580737e9d183&chksm=fc158685cb620f9359b3224379cfe5e380b7568d5fbe6c13ff2e89ba81834e961bffd91afe4c#rd