讀完本文，你可以去力扣拿下如下題目：
224.基本計算器
227.基本計算器II
772.基本計算器III
-----------
我們最終要實現的計算器功能如下：
1、輸入一個字串，可以包含+ - * /、數字、括號以及空格，你的演算法返回運算結果。
2、要符合運演算法則，括號的優先順序最高，先乘除後加減。
3、除號是整數除法，無論正負都向 0 取整（5/2=2，-5/2=-2）。
4、可以假定輸入的算式一定合法，且計算過程不會出現整型溢位，不會出現除數為 0 的意外情況。
比如輸入如下字串，演算法會返回 9：
3 * (2-6 /(3 -7))
可以看到，這就已經非常接近我們實際生活中使用的計算器了，雖然我們以前肯定都用過計算器，但是如果簡單思考一下其演算法實現，就會大驚失色：
1、按照常理處理括號，要先計算最內層的括號，然後向外慢慢化簡。這個過程我們手算都容易出錯，何況寫成演算法呢！
2、要做到先乘除，後加減，這一點教會小朋友還不算難，但教給計算機恐怕有點困難。
3、要處理空格。我們為了美觀，習慣性在數字和運算子之間打個空格，但是計算之中得想辦法忽略這些空格。
我記得很多大學資料結構的教材上，在講棧這種資料結構的時候，應該都會用計算器舉例，但是有一說一，講的真的垃圾，不知道多少未來的計算機科學家就被這種簡單的資料結構勸退了。
那麼本文就來聊聊怎麼實現上述一個功能完備的計算器功能，關鍵在於層層拆解問題，化整為零，逐個擊破，相信這種思維方式能幫大家解決各種複雜問題。
下面就來拆解，從最簡單的一個問題開始。
一、字串轉整數是的，就是這麼一個簡單的問題，首先告訴我，怎麼把一個字串形式的正整數，轉化成 int 型？
string s = "458";int n = 0;for (int i = 0; i < s.size(); i++) { char c = s[i]; n = 10 * n + (c - '0');}// n 現在就等於 458這個還是很簡單的吧，老套路了。但是即便這麼簡單，依然有坑：(c - '0')的這個括號不能省略，否則可能造成整型溢位。
因為變數c是一個 ASCII 碼，如果不加括號就會先加後減，想象一下s如果接近 INT_MAX，就會溢位。所以用括號保證先減後加才行。
二、處理加減法現在進一步，如果輸入的這個算式只包含加減法，而且不存在空格，你怎麼計算結果？我們拿字串算式1-12+3為例，來說一個很簡單的思路：
1、先給第一個數字加一個預設符號+，變成+1-12+3。
2、把一個運算子和數字組合成一對兒，也就是三對兒+1，-12，+3，把它們轉化成數字，然後放到一個棧中。
3、將棧中所有的數字求和，就是原算式的結果。
我們直接看程式碼，結合一張圖就看明白了：
int calculate(string s) { stack<int> stk; // 記錄算式中的數字 int num = 0; // 記錄 num 前的符號，初始化為 + char sign = '+'; for (int i = 0; i < s.size(); i++) { char c = s[i]; // 如果是數字，連續讀取到 num if (isdigit(c)) num = 10 * num + (c - '0'); // 如果不是數字，就是遇到了下一個符號， // 之前的數字和符號就要存進棧中 if (!isdigit(c) || i == s.size() - 1) { switch (sign) { case '+': stk.push(num); break; case '-': stk.push(-num); break; } // 更新符號為當前符號，數字清零 sign = c; num = 0; } } // 將棧中所有結果求和就是答案 int res = 0; while (!stk.empty()) { res += stk.top(); stk.pop(); } return res;}我估計就是中間帶switch語句的部分有點不好理解吧，i就是從左到右掃描，sign和num跟在它身後。當s[i]遇到一個運算子時，情況是這樣的：
所以說，此時要根據sign的 case 不同選擇nums的正負號，存入棧中，然後更新sign並清零nums記錄下一對兒符合和數字的組合。
另外注意，不只是遇到新的符號會觸發入棧，當i走到了算式的盡頭（i == s.size() - 1），也應該將前面的數字入棧，方便後續計算最終結果。
至此，僅處理緊湊加減法字串的演算法就完成了，請確保理解以上內容，後續的內容就基於這個框架修修改改就完事兒了。
三、處理乘除法其實思路跟僅處理加減法沒啥區別，拿字串2-3*4+5舉例，核心思路依然是把字串分解成符號和數字的組合。
比如上述例子就可以分解為+2，-3，*4，+5幾對兒，我們剛才不是沒有處理乘除號嗎，很簡單，其他部分都不用變，在switch部分加上對應的 case 就行了：
for (int i = 0; i < s.size(); i++) { char c = s[i]; if (isdigit(c)) num = 10 * num + (c - '0'); if (!isdigit(c) || i == s.size() - 1) { switch (sign) { int pre; case '+': stk.push(num); break; case '-': stk.push(-num); break; // 只要拿出前一個數字做對應運算即可 case '*': pre = stk.top(); stk.pop(); stk.push(pre * num); break; case '/': pre = stk.top(); stk.pop(); stk.push(pre / num); break; } // 更新符號為當前符號，數字清零 sign = c; num = 0; }}乘除法優先於加減法體現在，乘除法可以和棧頂的數結合，而加減法只能把自己放入棧。
現在我們思考一下如何處理字串中可能出現的空格字元。其實也非常簡單，想想空格字元的出現，會影響我們現有程式碼的哪一部分？
// 如果 c 非數字if (!isdigit(c) || i == s.size() - 1) { switch (c) {...} sign = c; num = 0;}顯然空格會進入這個 if 語句，但是我們並不想讓空格的情況進入這個 if，因為這裡會更新sign並清零nums，空格根本就不是運算子，應該被忽略。
那麼只要多加一個條件即可：
if ((!isdigit(c) && c != ' ') || i == s.size() - 1) { ...}好了，現在我們的演算法已經可以按照正確的法則計算加減乘除，並且自動忽略空格符，剩下的就是如何讓演算法正確識別括號了。
四、處理括號處理算式中的括號看起來應該是最難的，但真沒有看起來那麼難。
為了規避程式語言的繁瑣細節，我把前面解法的程式碼翻譯成 Python 版本：
def calculate(s: str) -> int: def helper(s: List) -> int: stack = [] sign = '+' num = 0 while len(s) > 0: c = s.pop(0) if c.isdigit(): num = 10 * num + int(c) if (not c.isdigit() and c != ' ') or len(s) == 0: if sign == '+': stack.append(num) elif sign == '-': stack.append(-num) elif sign == '*': stack[-1] = stack[-1] * num elif sign == '/': # python 除法向 0 取整的寫法 stack[-1] = int(stack[-1] / float(num)) num = 0 sign = c return sum(stack) # 需要把字串轉成列表方便操作 return helper(list(s))這段程式碼跟剛才 C++ 程式碼完全相同，唯一的區別是，不是從左到右遍歷字串，而是不斷從左邊pop出字元，本質還是一樣的。
那麼，為什麼說處理括號沒有看起來那麼難呢，因為括號具有遞迴性質。我們拿字串3*(4-5/2)-6舉例：
calculate(3*(4-5/2)-6) = 3 * calculate(4-5/2) - 6 = 3 * 2 - 6 = 0
可以腦補一下，無論多少層括號巢狀，透過 calculate 函式遞迴呼叫自己，都可以將括號中的算式化簡成一個數字。換句話說，括號包含的算式，我們直接視為一個數字就行了。
現在的問題是，遞迴的開始條件和結束條件是什麼？遇到(開始遞迴，遇到)結束遞迴：
def calculate(s: str) -> int: def helper(s: List) -> int: stack = [] sign = '+' num = 0 while len(s) > 0: c = s.pop(0) if c.isdigit(): num = 10 * num + int(c) # 遇到左括號開始遞迴計算 num if c == '(': num = helper(s) if (not c.isdigit() and c != ' ') or len(s) == 0: if sign == '+': ... elif sign == '-': ... elif sign == '*': ... elif sign == '/': ... num = 0 sign = c # 遇到右括號返回遞迴結果 if c == ')': break return sum(stack) return helper(list(s))你看，加了兩三行程式碼，就可以處理括號了，這就是遞迴的魅力。至此，計算器的全部功能就實現了，透過對問題的層層拆解化整為零，再回頭看，這個問題似乎也沒那麼複雜嘛。
五、最後總結本文借實現計算器的問題，主要想表達的是一種處理複雜問題的思路。
我們首先從字串轉數字這個簡單問題開始，進而處理只包含加減法的算式，進而處理包含加減乘除四則運算的算式，進而處理空格字元，進而處理包含括號的算式。
可見，對於一些比較困難的問題，其解法並不是一蹴而就的，而是步步推進，螺旋上升的。如果一開始給你原題，你不會做，甚至看不懂答案，都很正常，關鍵在於我們自己如何簡化問題，如何以退為進。
退而求其次是一種很聰明策略。你想想啊，假設這是一道考試題，你不會實現這個計算器，但是你寫了字串轉整數的演算法並指出了容易溢位的陷阱，那起碼可以得 20 分吧；如果你能夠處理加減法，那可以得 40 分吧；如果你能處理加減乘除四則運算，那起碼夠 70 分了；再加上處理空格字元，80 有了吧。我就是不會處理括號，那就算了，80 已經很 OK 了好不好。