本文實例講述了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>
新聞熱點
疑難解答
圖片精選
