224.基本計算器 （點擊查看題目）
題目描述
實現一個基本的計算器來計算一個簡單的字符串表達式的值。
字符串表達式可以包含左括號 ( ，右括號 )，加號 + ，減號 -，非負 整數和空格 。
示例 1:
<code>輸入: "1 + 1"
輸出: 2/<code>
示例 2:
<code>輸入: " 2-1 + 2 "
輸出: 3/<code>
示例 3:
<code>輸入: "(1+(4+5+2)-3)+(6+8)"
輸出: 23/<code>
說明：
- 你可以假設所給定的表達式都是有效的。
- 請不要使用內置的庫函數 eval。
解決方案
概述
解決這個問題需要理解以下內容：
- 輸入始終包含有效的字符串。
- 加減法規則。
- 括號中的優先含義。
- 空格不影響輸入表達式的計算。
方法一：棧和反轉字符串
這個問題適合用棧來解決，因為表達式中包含括號，我們可以使用棧來查找每個子表達式的值。本質上，我們需要延遲處理主表達式，直到完成對括號種的中間子表達式的求值，我們使用棧來解決它。
我們將表達式的元素一個接一個的添加到棧上，直到我們遇到一個右括號 )。然後逐個彈出棧中的元素，在運行時對子表達式進行求值，直到遇到左括號 ( 為止。
我們需要理解 + 和 - 的區別。+ 遵循結合律。例如 A + B + C，等價於（A + B ）+ C = A +（B + C）。然後 - 不遵循這個一規則，這是該方法中所有問題的根本原因。
如果我們使用棧並從左到右讀取表達式的元素，則最終我們會從右到左計算表達式。就會出現 （A -B）- C 等於（C - B）- A 的情況，這是不正確的。減法即不遵循結合律也不遵循交換律。
這個問題很容易解決，我們通過反轉字符串，然後再按需添加到棧中，我們將字符串從右到左放入棧中，並從左到右正確的計算表達式。
算法：
- 按逆序迭代字符串。
- 操作數可以由多個字符組成，字符串 "123" 表示數字 123，它可以被構造為：123 >> 120 + 3 >> 100 + 20 + 3。如果我們讀取的字符是一個數字，則我們要將讀取的數字乘以 10 的冪並將當前數字相加，形成操作數。因為我們是按逆序處理字符串。
- 操作數由多個字符組成，一旦我們遇到的字符不是數字，則我們將操作數添加到棧上。
- 當我們遇到最括號 (，這意味這遇到了一個子表達式結束。由於我們是逆序，所以開括號成了表達式的結尾。則需要從棧中彈出操作數和運算髮來計算表達式，直到彈出相應的右括號。子表達式的最終結果最終添加到棧上。
- 將非數字字符添加到棧上。
- 這個做直到我們得到最終的結果。可能我們沒有更多的字符要處理，但是棧仍然是非空的。當主表達式沒有用括號括起來時，就會發生這種情況。因此，在完成對整個表達式求值之後，我們將檢查棧是否非空。如果是的話，我們將棧中的元素作為最終表達式處理，並像遇到左括號時那樣對其求值。我們還可以用一組括號覆蓋原表達式，以此避免額外調用。
Python 實現（電腦端查看代碼）
<code>class Solution:
def evaluate_expr(self, stack):
res = stack.pop() if stack else 0
# Evaluate the expression till we get corresponding ')'
while stack and stack[-1] != ')':
sign = stack.pop()
if sign == '+':
res += stack.pop()
else:
res -= stack.pop()
return res
def calculate(self, s: str) -> int:
stack = []
n, operand = 0, 0
for i in range(len(s) - 1, -1, -1):
ch = s[i]
if ch.isdigit():
# Forming the operand - in reverse order.
operand = (10**n * int(ch)) + operand
n += 1
elif ch != " ":
if n:
# Save the operand on the stack
# As we encounter some non-digit.
stack.append(operand)
n, operand = 0, 0
if ch == '(':
res = self.evaluate_expr(stack)
stack.pop()
# Append the evaluated result to the stack.
# This result could be of a sub-expression within the parenthesis.
stack.append(res)
# For other non-digits just push onto the stack.
else:
stack.append(ch)
# Push the last operand to stack, if any.
if n:
stack.append(operand)
# Evaluate any left overs in the stack.
return self.evaluate_expr(stack)/<code>
Java 實現（電腦端查看代碼）
<code>class Solution {
public int evaluateExpr(Stack<object> stack) {
int res = 0;
if (!stack.empty()) {
res = (int) stack.pop();
}
// Evaluate the expression till we get corresponding ')'
while (!stack.empty() && !((char) stack.peek() == ')')) {
char sign = (char) stack.pop();
if (sign == '+') {
res += (int) stack.pop();
} else {
res -= (int) stack.pop();
}
}
return res;
}
public int calculate(String s) {
int operand = 0;
int n = 0;
Stack<object> stack = new Stack<object>();
for (int i = s.length() - 1; i >= 0; i--) {
char ch = s.charAt(i);
if (Character.isDigit(ch)) {
// Forming the operand - in reverse order.
operand = (int) Math.pow(10, n) * (int) (ch - '0') + operand;
n += 1;
} else if (ch != ' ') {
if (n != 0) {
// Save the operand on the stack
// As we encounter some non-digit.
stack.push(operand);
n = 0;
operand = 0;
}
if (ch == '(') {
int res = evaluateExpr(stack);
stack.pop();
// Append the evaluated result to the stack.
// This result could be of a sub-expression within the parenthesis.
stack.push(res);
} else {
// For other non-digits just push onto the stack.
stack.push(ch);
}
}
}
//Push the last operand to stack, if any.
if (n != 0) {
stack.push(operand);
}
// Evaluate any left overs in the stack.
return evaluateExpr(stack);
}
}/<object>/<object>/<object>/<code>複雜度分析
時間複雜度：O(N)，其中 N 指的是字符串的長度。
空間複雜度：O(N)，其中 N 指的是字符串的長度。
方法二：棧和不反轉字符串
解決 - 結合律的問題的一個分廠簡單的方法就是使將 - 運算符看作右側操作數的大小。一旦我們將 - 看作操作數的大小，則表達式將只剩下一個操作符。就是 + 運算符，而 + 是遵循結合律的。
例如，A - B - C 等於 A +（-B）+（-C）。
重寫以後的表達式將遵循結合律，所以我們從左或從右計算表達式都是正確的。
我們需要注意的是給定的表達式會很複雜，即會有嵌套在其他表達式的表達式。即 (A - (B - C)，我們需要 B-C 外面的 - 號與 B-C 關聯起來，而不是僅僅與 B 關聯起來。
/ 我們可以通過遵循前面的基本練習並將符號與其右側的表達式關聯來解決此問題。然而，我們將採用的方法有一個小的轉折，因為我們將在運行中評估大多數表達式。這減少了推送和彈出操作的數量。
算法：
- 正序迭代字符串。
- 操作數可以由多個字符組成，字符串 "123" 表示數字 123，它可以被構造為：123 >> 120 + 3 >> 100 + 20 + 3。如果我們讀取的字符是一個數字，則我們要將先前形成的操作數乘以 10 並於讀取的數字相加，形成操作數。
- 每當我們遇到 + 或 - 運算符時，我們首先將表達式求值到左邊，然後將正負符號保存到下一次求值。
- 如果字符是左括號 (，我們將迄今為止計算的結果和符號添加到棧上，然後重新開始進行計算，就像計算一個新的表達式一樣。
- 如果字符是右括號 )，則首先計算左側的表達式。則產生的結果就是剛剛結束的子表達式的結果。如果棧頂部有符號，則將此結果與符號相乘。
Python 實現（電腦端查看代碼）
<code>class Solution:
def calculate(self, s: str) -> int:
stack = []
operand = 0
res = 0 # For the on-going result
sign = 1 # 1 means positive, -1 means negative
for ch in s:
if ch.isdigit():
# Forming operand, since it could be more than one digit
operand = (operand * 10) + int(ch)
elif ch == '+':
# Evaluate the expression to the left,
# with result, sign, operand
res += sign * operand
# Save the recently encountered '+' sign
sign = 1
# Reset operand
operand = 0
elif ch == '-':
res += sign * operand
sign = -1
operand = 0
elif ch == '(':
# Push the result and sign on to the stack, for later
# We push the result first, then sign
stack.append(res)
stack.append(sign)
# Reset operand and result, as if new evaluation begins for the new sub-expression
sign = 1
res = 0
elif ch == ')':
# Evaluate the expression to the left
# with result, sign and operand
res += sign * operand
# ')' marks end of expression within a set of parenthesis
# Its result is multiplied with sign on top of stack
# as stack.pop() is the sign before the parenthesis
res *= stack.pop() # stack pop 1, sign
# Then add to the next operand on the top.
# as stack.pop() is the result calculated before this parenthesis
# (operand on stack) + (sign on stack * (result from parenthesis))
res += stack.pop() # stack pop 2, operand
# Reset the operand
operand = 0
return res + sign * operand/<code>
Java 實現（電腦端查看代碼）
<code>
class Solution {
public int calculate(String s) {
Stack<integer> stack = new Stack<integer>();
int operand = 0;
int result = 0; // For the on-going result
int sign = 1; // 1 means positive, -1 means negative
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (Character.isDigit(ch)) {
// Forming operand, since it could be more than one digit
operand = 10 * operand + (int) (ch - '0');
} else if (ch == '+') {
// Evaluate the expression to the left,
// with result, sign, operand
result += sign * operand;
// Save the recently encountered '+' sign
sign = 1;
// Reset operand
operand = 0;
} else if (ch == '-') {
result += sign * operand;
sign = -1;
operand = 0;
} else if (ch == '(') {
// Push the result and sign on to the stack, for later
// We push the result first, then sign
stack.push(result);
stack.push(sign);
// Reset operand and result, as if new evaluation begins for the new sub-expression
sign = 1;
result = 0;
} else if (ch == ')') {
// Evaluate the expression to the left
// with result, sign and operand
result += sign * operand;
// ')' marks end of expression within a set of parenthesis
// Its result is multiplied with sign on top of stack
// as stack.pop() is the sign before the parenthesis
result *= stack.pop();
// Then add to the next operand on the top.
// as stack.pop() is the result calculated before this parenthesis
// (operand on stack) + (sign on stack * (result from parenthesis))
result += stack.pop();
// Reset the operand
operand = 0;
}
}
return result + (sign * operand);
}
}/<integer>/<integer>/<code>
複雜度分析
時間複雜度：O(N)，其中 N 指的是字符串的長度。這種方法與前一種方法的區別在於，這種方法的每個字符都將被精確的處理一次。但是前面的方法中，每個字符可能被處理兩次，一次是被添加到棧上，另一次是被彈出處理最終結果。這就是為什麼這種方法更快的原因。
空間複雜度：O(N)，其中 N 指的是字符串的長度。
分享到:
閱讀更多 力扣LeetCode 的文章
