這是一道?困難?題。

題目來自：leetcode

題目

給你一個字符串表達(dá)式?s?，請你實現(xiàn)一個基本計算器來計算并返回它的值。

注意: 不允許使用任何將字符串作為數(shù)學(xué)表達(dá)式計算的內(nèi)置函數(shù)，比如?eval()?。

提示：

• s?由數(shù)字、‘+’、‘-’、‘(’、‘)’、和 ’ ’ 組成
• s?表示一個有效的表達(dá)式
• ‘+’ 不能用作一元運(yùn)算(例如， “+1” 和 “+(2 + 3)” 無效)
• 輸入中不存在兩個連續(xù)的操作符
• 每個數(shù)字和運(yùn)行的計算將適合于一個有符號的?32位?整數(shù)

示例 1：

輸入：s =?"1 + 1"
輸出：2

示例 2：

輸入：s =?" 2-1 + 2 "
輸出：3

示例 3：

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

解題思路

這道題是 實現(xiàn)一個包含“加減乘除”的基本計算器 的擴(kuò)展，在表達(dá)式中增加了 括號 “(”, “)” 和 正負(fù)數(shù)，但是刪除了 “*” 和 “/”。

在原來的解題方法中補(bǔ)充以下幾點：

1. 括號的處理：
   • 如果遇到左括號：直接壓入操作符棧。
   • 如果遇到右括號：將操作符棧中左括號后面的所有操作符出棧，并與數(shù)字棧進(jìn)行計算合并。
2. 正負(fù)數(shù)的處理：
   • 可以使用 補(bǔ)0 的思路，在正負(fù)數(shù)前面加一個“0”，將表達(dá)式轉(zhuǎn)換為沒有正負(fù)號的式子。

那么如何確定“+”和“-”是代表算符還是正負(fù)號呢？

1. 如果 “+”和“-” 是第一個非空字符，那么代表是正負(fù)號。
2. 如果 “+”和“-” 的前一個非空字符也是“+”或者“-”，那么代表是正負(fù)號。
3. 如果 “+”和“-” 的前一個非空字符是 左括號 ，那么代表是正負(fù)號。

注：補(bǔ)0的思路只能用于加減法.

代碼實現(xiàn)

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

復(fù)雜度分析

時間復(fù)雜度：$O(N)$，N 為字符串長度。

空間復(fù)雜度：$O(N)$，N 為字符串長度。