快捷導(dǎo)航

JavaScript數(shù)據(jù)結(jié)構(gòu)中棧的應(yīng)用之表達(dá)式求值問題詳解

更新時(shí)間：2017年04月11日 15:09:23 作者：布瑞澤的童話

這篇文章主要介紹了JavaScript數(shù)據(jù)結(jié)構(gòu)中棧的應(yīng)用之表達(dá)式求值問題,詳細(xì)分析了中綴表達(dá)式、后綴表達(dá)式等概念、原理與轉(zhuǎn)換方法,以及基于后綴表達(dá)式實(shí)現(xiàn)的表達(dá)式求值相關(guān)操作技巧,需要的朋友可以參考下

本文實(shí)例講述了JavaScript數(shù)據(jù)結(jié)構(gòu)中棧的應(yīng)用之表達(dá)式求值問題。分享給大家供大家參考，具體如下：

下面來談一個(gè)比較經(jīng)典的表達(dá)式求值問題，這個(gè)問題主要是設(shè)計(jì)到操作符的優(yōu)先級(jí)。我們通?？吹降谋磉_(dá)式都是中綴表達(dá)式，存在很多優(yōu)先級(jí)差別，而后綴表達(dá)式則沒有這些優(yōu)先級(jí)問題。下面先看看兩種表達(dá)式的區(qū)別。

中綴表達(dá)式：a*b+c*d-e/f
后綴表達(dá)式：ab*cd*+ef/-

從中綴表達(dá)式轉(zhuǎn)換到后綴表示式是很難實(shí)現(xiàn)的，我們這里可以通過棧的思想來實(shí)現(xiàn)。下面進(jìn)行詳細(xì)的介紹是什么樣的思想：

在對(duì)一個(gè)中綴表示式進(jìn)行轉(zhuǎn)換的時(shí)候，遇到非操作符的字符則直接保存到后綴表示式的存儲(chǔ)空間中。

遇到（，則壓入棧，只有遇到對(duì)應(yīng)的）才能被彈出。
遇到），就將（之前的操作符全部彈出，并保存到存儲(chǔ)空間。
遇到*和/這樣優(yōu)先級(jí)高的，就判斷棧中的操作符優(yōu)先級(jí)是否低于當(dāng)前操作符。
如果棧中的遇到的低，則將遇到的繼續(xù)入棧；如果棧中的高，則將棧中的出棧，遇到的入棧。
最后，當(dāng)字符串遍歷完成，依次彈出操作符，保存到存儲(chǔ)空間。

為了方便理解，將上面的例子再次講解。a*b+c*d-e/f

首先是ab被保存到了存儲(chǔ)空間，然后*入?！，F(xiàn)在棧中只有*。
遇到+之后，由于*比+優(yōu)先級(jí)高，所以*出棧，+入棧，這樣存儲(chǔ)空間變?yōu)閍b*，棧中變?yōu)?。
再時(shí)候遇到c，存儲(chǔ)空間變?yōu)閍b*c，棧中還是+。
接下來遇到*和d，由于+比*低，所以*繼續(xù)入棧，棧中表為了+*，存儲(chǔ)空間為ab*cd。
之后遇到-，由于*比-高，所以+*出棧，-入棧，存儲(chǔ)空間變?yōu)閍b*cd*+
……后面不用解釋了，悟性再低也應(yīng)該會(huì)了。

下面我們用JavaScript代碼來實(shí)現(xiàn)下吧。

<!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 ')'://如果是）則將棧中左括號(hào)之前的對(duì)象彈出
    {
     if(myArray.length==0){
      return false;
     }
     temp=myArray.pop();//非空，彈出對(duì)象
     while(temp!='('){//只要不是左括號(hào)，則全部彈出
      b+=temp;//并輸出到后綴表達(dá)式中
      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=='-'){//如果遇到高的，則遇到的繼續(xù)入棧
       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;//保存到存儲(chǔ)空間
       }
       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>

當(dāng)然，以上程序還存在一點(diǎn)bug，但是思想應(yīng)該就是這樣子的。

下面，我們將講解如何通過后綴表達(dá)式計(jì)算出表達(dá)式的結(jié)果。

那么，我們將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式后，如何繼續(xù)計(jì)算呢？還是以這個(gè)例子為例。

中綴表達(dá)式：a*b+c*d-e/f
后綴表達(dá)式：ab*cd*+ef/-

基本思路如下：

遍歷后綴表達(dá)式，遇到非操作符的字符則直接進(jìn)棧，遇到操作符則出棧兩個(gè)元素，進(jìn)行對(duì)應(yīng)操作，然后將得到的結(jié)果再次入棧。依次直到遍歷完成，此處棧中保存的值就是當(dāng)前表達(dá)式的值。

實(shí)現(xiàn)的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])
    {//遇到數(shù)值則直接入棧
     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 '+':
     {//遇到操作符則出棧兩個(gè)元素進(jìn)行對(duì)應(yīng)操作
      temp=myArray.pop()+myArray.pop();
      myArray.push(temp);//再將結(jié)果入棧
      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);//再將結(jié)果入棧
      temp=null;
      break;
     }
     case '/':
     {
      s=myArray.pop();
      temp=myArray.pop()/s;
      myArray.push(temp);
      s=null;temp=null;
      break;
     }
    }
   }
   return myArray.pop();//算出結(jié)果
 }
 var a="12*34*+36/-";//1*2+3*4-3/6
 var b=getValue(a);//13.5
 alert(b);
</script>
 </body>
</html>

好啦，棧的應(yīng)用場(chǎng)景還有很多，比如進(jìn)制的轉(zhuǎn)換，行編輯程序，迷宮求解等。這里就不一一介紹了。

更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法技巧總結(jié)》、《JavaScript數(shù)學(xué)運(yùn)算用法總結(jié)》、《JavaScript排序算法總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》及《JavaScript錯(cuò)誤與調(diào)試技巧總結(jié)》

希望本文所述對(duì)大家JavaScript程序設(shè)計(jì)有所幫助。

您可能感興趣的文章: