前段時間面試一個候選人，問了一個資料結構與算法的問題，表達式求值。
題目大概是這樣的：
輸入長度為n的字元串，例如：1+2+345
輸出表達式的值，即：63
我暗示的問：應該用什麼資料結構？
候選人回答：棧。
畫外音：算是答對。
問：時間複雜度呢？
回答：O(n^2)
畫外音：額，應該不需要兩個for循環吧。
我接着提示：應該先計算哪一步？
候選人回答：先計算3*4。
畫外音：額，難道是乘除大于加減？
實際應該先計算1+2，說明候選人對“表達式求值”并沒有搞透。
怎麼用棧來實作呢？
候選人：…
本來以為是送分題，候選人竟一時語塞。
為了廣大面試的同學不再在這一題上送命，今天花幾分鐘把這個問題講透徹。
畫外音：希望沒有幫面試官增加題庫。
“表達式求值”問題，兩個核心關鍵點：
（1）雙棧，一個操作數棧，一個運算符棧；
（2）運算符優先級，棧頂運算符，和，即将入棧的運算符的優先級比較：
如果棧頂的運算符優先級低，新運算符直接入棧
如果棧頂的運算符優先級高，先出棧計算，新運算符再入棧
仍以1+2+345舉例，看是如何利用上述兩個關鍵點實施計算的。
首先，這個例子隻有+和*兩個運算符，是以它的運算符表是：
這裡的含義是：
（1）如果棧頂是+，即将入棧的是+，棧頂優先級高，需要先計算，再入棧；
（2）如果棧頂是+，即将入棧的是*，棧頂優先級低，直接入棧；
（3）如果棧頂是*，即将入棧的是+，棧頂優先級高，需要先計算，再入棧；
（4）如果棧頂是，即将入棧的是，棧頂優先級高，需要先計算，再入棧；
畫外音：運算符有+-/()~^&都沒問題，如果共有n個運算符，會有一個nn的優先級表。
有了運算符表，一切就好辦了。
一步步，掃描字元串，操作數一個個入棧，運算符也入棧。
畫外音：如果有“789”這樣的多個字元的多位數，要先轉化為數字789，這個過程很容易。
下一個操作符要入棧時，需要先比較優先級。
棧内的優先級高，必須先計算，才能入棧。
計算的過程為：
（1）操作數出棧，作為num2；
（2）操作數出棧，作為num1；
（3）運算符出棧，作為op；
（4）計算出結果；
接下來，運算符和操作數才能繼續入棧。下一個操作符要入棧時，繼續比較與棧頂的優先級。
棧内的優先級低，可以直接入棧。
總結
這個方法的時間複雜度為O(n)，整個字元串隻需要掃描一遍。
思路比結論重要，學到了嗎？
架構師之路-分享技術思路