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

这是一道困难题。

题目来自：https://leetcode.cn/problems/basic-calculator/description/

题目

给你一个字符串表达式 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
























题解



















01



解题思路










这道题是 【算法题解】17. 实现一个包含“加减乘除”的基本计算器 的扩展，在表达式中增加了 括号 “(“, “)” 和 正负数，但是删除了 “*” 和 “/“。题解还是使用 “双栈” 的思路来解决 “通用表达式” 问题。



在上一题的解题方法中补充以下几点：
括号的处理：
1.  如果遇到 左括号：直接压入操作符栈。
2. 如果遇到 右括号：将操作符栈中左括号后面的所有操作符出栈，并与数字栈进行计算合并。


正负数的处理：
可以使用 补0 的思路，在正负数前面加一个“0”，将表达式转换为没有正负号的式子。


那么如何确定“+”和“–”是代表算符还是正负号呢？
1.  如果 “+”和“–” 是 第一个 非空字符，那么代表是正负号。
2.  如果 “+”和“–” 的前一个非空字符也是“+”或者“–”，那么代表是正负号。
3.  如果 “+”和“–” 的前一个非空字符是 左括号 ，那么代表是正负号。


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






02



Java 代码实现











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);
        }

    }

}










03



复杂度分析










时间复杂度：, N 为字符串长度。


空间复杂度：, N 为字符串长度。









END


















点个在看你最好看