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