這是一道?困難?題。

題目來(lái)自：leetcode

題目

給你一個(gè)字符串表達(dá)式?s?，請(qǐng)你實(shí)現(xiàn)一個(gè)基本計(jì)算器來(lái)計(jì)算并返回它的值。

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

提示：

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

示例 1：

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

示例 2：

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

示例 3：

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

解題思路

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

在原來(lái)的解題方法中補(bǔ)充以下幾點(diǎn)：

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

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

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

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

代碼實(shí)現(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);}// 刪除左括號(hào)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ù)雜度分析

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

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