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

这是一道 困难 题。

题目来自：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

解题思路

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

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

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)$，N 为字符串长度。

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