本文實例講述了JavaScript數據結構中棧的應用之表達式求值問題。分享給大家供大家參考，具體如下：
下面來談一個比較經典的表達式求值問題，這個問題主要是設計到操作符的優先級。我們通常看到的表達式都是中綴表達式，存在很多優先級差別，而后綴表達式則沒有這些優先級問題。下面先看看兩種表達式的區別。
中綴表達式：a*b+c*d-e/f
后綴表達式：ab*cd*+ef/-
從中綴表達式轉換到后綴表示式是很難實現的，我們這里可以通過棧的思想來實現。下面進行詳細的介紹是什么樣的思想：
在對一個中綴表示式進行轉換的時候，遇到非操作符的字符則直接保存到后綴表示式的存儲空間中。
遇到（，則壓入棧，只有遇到對應的）才能被彈出。
遇到），就將（之前的操作符全部彈出，并保存到存儲空間。
遇到*和/這樣優先級高的，就判斷棧中的操作符優先級是否低于當前操作符。
如果棧中的遇到的低，則將遇到的繼續入棧；如果棧中的高，則將棧中的出棧，遇到的入棧。
最后，當字符串遍歷完成，依次彈出操作符，保存到存儲空間。
為了方便理解，將上面的例子再次講解。a*b+c*d-e/f
首先是ab被保存到了存儲空間，然后*入棧。現在棧中只有*。
遇到+之后，由于*比+優先級高，所以*出棧，+入棧，這樣存儲空間變為ab*，棧中變為+。
再時候遇到c，存儲空間變為ab*c，棧中還是+。
接下來遇到*和d，由于+比*低，所以*繼續入棧，棧中表為了+*，存儲空間為ab*cd。
之后遇到-，由于*比-高，所以+*出棧，-入棧，存儲空間變為ab*cd*+
……后面不用解釋了，悟性再低也應該會了。
下面我們用JavaScript代碼來實現下吧。
<!DOCTYPE html><html> <head> <meta charset="utf-8"> <title></title> </head> <body><script type="text/javascript"> function midTOLast(a){ var a_len=a.length; var myArray=new Array(); b=''; for(var i=0;i<a_len;i++){ switch (a[i]){ case '(': { myArray.push(a[i]); break; } case ')'://如果是）則將棧中左括號之前的對象彈出 { if(myArray.length==0){ return false; } temp=myArray.pop();//非空，彈出對象 while(temp!='('){//只要不是左括號，則全部彈出 b+=temp;//并輸出到后綴表達式中 if(myArray.length==0){//保證棧為空 break; } temp=myArray.pop(); } break; } case '*': case '/': { if(myArray.length==0){//如果棧為空則直接入棧 myArray.push(a[i]); }else{ temp=myArray[myArray.length-1]; if(temp=='+'||temp=='-'){//如果遇到高的，則遇到的繼續入棧 myArray.push(a[i]);//遇到的入棧 } } break; } case '+': case '-': { if(myArray.length==0){//如果棧為空則直接入棧 myArray.push(a[i]); }else{ temp=myArray[myArray.length-1]; if(temp=='/'||temp=='*'){//如果遇到低的，則棧中的出棧，遇到的入棧 while(myArray.length!=0){ temp=myArray.pop();//棧中的出棧 b+=temp;//保存到存儲空間 } myArray.push(a[i]);//遇到的入棧 } } break; } default: { b+=a[i]; break; } } } //最后將棧中剩下的操作符輸出 while(myArray.length!=0){ temp=myArray.pop(); b+=temp; } return true; } var x="a*b+c*d-e/f"; midTOLast(x); alert(b);//ab*cd*+ef/-</script> </body></html>當然，以上程序還存在一點bug，但是思想應該就是這樣子的。
下面，我們將講解如何通過后綴表達式計算出表達式的結果。
那么，我們將中綴表達式轉化為后綴表達式后，如何繼續計算呢？還是以這個例子為例。
中綴表達式：a*b+c*d-e/f
后綴表達式：ab*cd*+ef/-
基本思路如下：
遍歷后綴表達式，遇到非操作符的字符則直接進棧，遇到操作符則出棧兩個元素，進行對應操作，然后將得到的結果再次入棧。依次直到遍歷完成，此處棧中保存的值就是當前表達式的值。
實現的JavaScript代碼如下：
<!DOCTYPE html><html> <head> <meta charset="utf-8"> <title></title> </head> <body><script type="text/javascript"> function getValue(a){ var a_len=a.length, myArray=new Array(); for(var i=0;i<a_len;i++){ switch (a[i]) {//遇到數值則直接入棧 case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': { myArray.push(a[i]); break; } case '+': {//遇到操作符則出棧兩個元素進行對應操作 temp=myArray.pop()+myArray.pop(); myArray.push(temp);//再將結果入棧 temp=null; break; } case '-': { s=myArray.pop(); temp=myArray.pop()-s; myArray.push(temp); s=null;temp=null; break; } case '*': { temp=myArray.pop()*myArray.pop(); myArray.push(temp);//再將結果入棧 temp=null; break; } case '/': { s=myArray.pop(); temp=myArray.pop()/s; myArray.push(temp); s=null;temp=null; break; } } } return myArray.pop();//算出結果 } var a="12*34*+36/-";//1*2+3*4-3/6 var b=getValue(a);//13.5 alert(b);</script> </body></html>好啦，棧的應用場景還有很多，比如進制的轉換，行編輯程序，迷宮求解等。這里就不一一介紹了。
更多關于JavaScript相關內容感興趣的讀者可查看本站專題：《JavaScript數據結構與算法技巧總結》、《JavaScript數學運算用法總結》、《JavaScript排序算法總結》、《JavaScript遍歷算法與技巧總結》、《JavaScript查找算法技巧總結》及《JavaScript錯誤與調試技巧總結》
希望本文所述對大家JavaScript程序設計有所幫助。
新聞熱點
疑難解答
