建站
咨詢
售后
建站咨詢
新聞中心
上周面試一個(gè)候選人，問(wèn)了一個(gè)數(shù)據(jù)結(jié)構(gòu)與算法的問(wèn)題，表達(dá)式求值。
10年積累的成都網(wǎng)站建設(shè)、網(wǎng)站建設(shè)經(jīng)驗(yàn)，可以快速應(yīng)對(duì)客戶對(duì)網(wǎng)站的新想法和需求。提供各種問(wèn)題對(duì)應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認(rèn)識(shí)你，你也不認(rèn)識(shí)我。但先建設(shè)網(wǎng)站后付款的網(wǎng)站建設(shè)流程，更有臨沭免費(fèi)網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。
題目大概是這樣的：
- 輸入長(zhǎng)度為n的字符串，例如：1+2+3*4*5
- 輸出表達(dá)式的值，即：63
我暗示的問(wèn)：應(yīng)該用什么數(shù)據(jù)結(jié)構(gòu)？候選人回答：棧。
畫外音：算是答對(duì)。?
問(wèn)：時(shí)間復(fù)雜度呢？回答：O(n^2)
畫外音：額，應(yīng)該不需要兩個(gè)for循環(huán)吧。?
我接著提示：應(yīng)該先計(jì)算哪一步？候選人回答：先計(jì)算3*4。
畫外音：額，難道是乘除大于加減？
實(shí)際應(yīng)該先計(jì)算1+2，說(shuō)明候選人對(duì)“表達(dá)式求值”并沒(méi)有搞透。?
怎么用棧來(lái)實(shí)現(xiàn)呢？候選人：…
本來(lái)以為是送分題，候選人竟一時(shí)語(yǔ)塞。
為了廣大面試的同學(xué)不再在這一題上送命，今天花幾分鐘把這個(gè)問(wèn)題講透徹。
畫外音：希望沒(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ì)算，再入棧；
畫外音：運(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)算符也入棧。
畫外音：如果有“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é)果；
(5) 結(jié)果入操作數(shù)棧；
接下來(lái)，運(yùn)算符和操作數(shù)才能繼續(xù)入棧。下一個(gè)操作符要入棧時(shí)，繼續(xù)比較與棧頂?shù)膬?yōu)先級(jí)。
棧內(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é)到了嗎？?
標(biāo)題名稱：表達(dá)式求值，有些候選人總以為自己懂了！
文章出自：http://www.5511xx.com/article/djddheg.html
