拜托，面試別再問我表達式求值了?。?！
上周面試一個候選人，問了一個數(shù)據(jù)結(jié)構(gòu)與算法的問題，表達式求值。
題目大概是這樣的：
| 輸入長度為n的字符串，例如：1+2+3*4*5
輸出表達式的值，即：63 我暗示的問：應(yīng)該用什么數(shù)據(jù)結(jié)構(gòu)? 候選人回答：棧。 畫外音：算是答對。 問：時間復(fù)雜度呢? 回答：O(n^2) 畫外音：額，應(yīng)該不需要兩個for循環(huán)吧。 我接著提示：應(yīng)該先計算哪一步? 候選人回答：先計算3*4。 畫外音：額，難道是乘除大于加減? 實際應(yīng)該先計算1+2，說明候選人對“表達式求值”并沒有搞透。 怎么用棧來實現(xiàn)呢? 候選人：… |
本來以為是送分題，候選人竟一時語塞。
為了廣大面試的同學(xué)不再在這一題上送命，今天花幾分鐘把這個問題講透徹。
畫外音：希望沒有幫面試官增加題庫。
“表達式求值”問題，兩個核心關(guān)鍵點：
(1)雙棧，一個操作數(shù)棧，一個運算符棧;
(2)運算符優(yōu)先級，棧頂運算符，和，即將入棧的運算符的優(yōu)先級比較：
- 如果棧頂?shù)倪\算符優(yōu)先級低，新運算符直接入棧
- 如果棧頂?shù)倪\算符優(yōu)先級高，先出棧計算，新運算符再入棧
仍以1+2+3*4*5舉例，看是如何利用上述兩個關(guān)鍵點實施計算的。
首先，這個例子只有+和*兩個運算符，所以它的運算符表是：
這里的含義是：
- 如果棧頂是+，即將入棧的是+，棧頂優(yōu)先級高，需要先計算，再入棧;
- 如果棧頂是+，即將入棧的是*，棧頂優(yōu)先級低，直接入棧;
- 如果棧頂是*，即將入棧的是+，棧頂優(yōu)先級高，需要先計算，再入棧;
- 如果棧頂是*，即將入棧的是*，棧頂優(yōu)先級高，需要先計算，再入棧;
畫外音：運算符有+-*/()~^&都沒問題，如果共有n個運算符，會有一個n*n的優(yōu)先級表。
有了運算符表，一切就好辦了。
一開始，初始化好輸入的字符串，以及操作數(shù)棧，運算符棧。
一步步，掃描字符串，操作數(shù)一個個入棧，運算符也入棧。
畫外音：如果有“789”這樣的多個字符的多位數(shù)，要先轉(zhuǎn)化為數(shù)字789，這個過程很容易。
下一個操作符要入棧時，需要先比較優(yōu)先級。
棧內(nèi)的優(yōu)先級高，必須先計算，才能入棧。
計算的過程為：
- 操作數(shù)出棧，作為num2;
- 操作數(shù)出棧，作為num1;
- 運算符出棧，作為op;
- 計算出結(jié)果;
- 結(jié)果入操作數(shù)棧;
棧內(nèi)的優(yōu)先級低，可以直接入棧。
字符串繼續(xù)移動。
又要比較優(yōu)先級了。
棧內(nèi)的優(yōu)先級高，還是先計算(3*4=12)，再入棧。
不斷入棧，直到字符串掃描完畢。
不斷出棧，直到得到最終結(jié)果3+60=63，算法完成。
總結(jié)
“表達式求值”問題，兩個核心關(guān)鍵點：
(1)雙棧，一個操作數(shù)棧，一個運算符棧;
(2)運算符優(yōu)先級，棧頂運算符，和，即將入棧的運算符的優(yōu)先級比較：
- 如果棧頂?shù)倪\算符優(yōu)先級低，新運算符直接入棧
- 如果棧頂?shù)倪\算符優(yōu)先級高，先出棧計算，新運算符再入棧
這個方法的時間復(fù)雜度為O(n)，整個字符串只需要掃描一遍。
思路比結(jié)論重要，學(xué)到了嗎?
【本文為51CTO專欄作者“58沈劍”原創(chuàng)稿件，轉(zhuǎn)載請聯(lián)系原作者】
