国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發設計 > 正文

數據結構輔導---棧和隊列(2)

2019-11-17 05:31:41
字體：大 中 小
來源：轉載
供稿：網友
3. 把中綴表達式轉換為后綴表達式的算法
    設以’@’字符作為結束符的中綴算術表達式已經保存在s1字符串中，轉換后得到的后綴算術表達式擬存于s2字符串中。由中綴表達式轉換為后綴表達式的規則可知：轉換前后，表達式中的數值項的次序不變，而運算符的次序發生了變化，由處在兩個運算對象的中間變為處在兩個運算對象的后面，同時去掉了所有的括號。為了使轉換正確，必須設定一個運算符棧，并在棧底放入一個非凡算符，假定為’@’字符，讓它具有最低的運算符優先級，假定為數值0，此棧用來保存掃描中綴表達式得到的暫不能放入后綴表達式中的運算符，待它的兩個運算對象都放入到后綴表達式以后，再令其出棧并寫入到后綴表達式中。
    把中綴表達式轉換為后綴表達式算法的基本思路是從頭到尾地掃描中綴表達式中的每個字符，對于不同類型的字符按不情況進行處理。若碰到的是空格則認為是分隔符，不需要進行處理；若碰到的是數字或小數點，則直接寫入到s2中，并在每個數值的最后寫入一個空格；若碰到的是左括號，則應把它壓入到運算符棧中，待以它開始的括號內的表達式轉換完畢后再出棧；若碰到的是右括號，則表明括號內的中綴表達式已經掃描完畢，把從棧底直到保存著的對應左括號之間的運算符依次退棧并寫入s2串中；若碰到的是運算符，當該運算符的優先級大于棧頂運算符的優先級（加減運算符的優先級設定為1，乘除運算符的優先級設定為2，在棧中保存的非凡運算符’@’和’(’的優先級設定為0)時，表明該運算符的后一個運算對象還沒有被掃描并放入到s2串中，應把它暫存于運算符棧中，待它的后一個運算對象從s1串中讀出并寫入到s2串中后，再另其出棧并寫入s2串中；若碰到的運算符的優先級小于等于棧頂運算符的優先級，這表明棧頂運算符的兩個運算對象已經被保存到s2串中，應將棧頂運算符退棧并寫入到s2串中，對于新的棧頂運算符仍繼續進行比較和處理，直到被處理的運算符的優先級大于棧頂運算符的優先級為止，然后另該運算符進棧即可。
按照以上過程掃描到中綴表達式結束符’@’時，把棧中剩余的運算符依次退棧并寫入到后綴表達式中，再向s2寫入表達式結束符’@’和字符串結束符’/0’，整個轉換過程就處理完畢，在s2中就得到了轉換成的后綴表達式。
    例如，設中綴算術表達式s1為：10+(18+9*3)/15-6@，使用的運算符棧用R表示，則轉換過程如下：
    （1）開始時存放后綴表達式的字符串s2為空，R中壓入有’@’算符，它具有最低的優先級0：
                        
@                    
  
（2）當掃描到s1中的左括號時，s2和R中的數據變化如下：
1 0                   
@ + (                      （3）當掃描到s1中的數值3時，s2和R中的數據變化為：
1 0   1 8  9  3            
@ + ( + *                    （4）當掃描到s1中的右括號時，s2和R變為：
1 0   1 8  9  3  * +         
@ +                       （5）當掃描到s1中的數值15時，s2和R又變為：
1 0   1 8  9  3  * + 1 5       
@ + /                      （6）當掃描到s1中的’@’字符時，s2和R為：
1 0   1 8  9  3  * + 1 5  / + 6   
@ -                   
1 0   1 8  9  3  * + 1 5  / + 6  - @ Ù
    （7）當整個處理過程結束后，R棧為空，s2為：    將中綴算術表達式轉換為后綴算術表達式的算法描述如下：
         void Change(char* s1, char* s2)
                //  將字符串s1中的中綴表達式轉換為存于字符串s2中的后綴表達式
        {
         Stack R;  //  定義用于暫存運算符的棧
            InitStack(R);  //  初始化棧
         Push(R,'@');  //  給棧底放入'@'字符，它具有最低優先級0
         int i,j;
         i=0;  //  用于指示掃描s1串中字符的位置，初值為0
         j=0;  //  用于指示s2串中待存字符的位置，初值為0
         char ch=s1[i];  //  ch保存s1串中掃描到的字符，初值為第一個字符
         while(ch!='@')
         {        //  順序處理中綴表達式中的每個字符
          if(ch==' ')
             //  對于空格字符不做任何處理，順序讀取下一個字符
           ch=s1[++i]; 
          else if(ch=='(')
          {    //  對于左括號，直接進棧
           Push(R,ch);
           ch=s1[++i];
          }
          else if(ch==')')
          {    //  對于右括號，使括號內的仍停留在棧中的運算符依次
            //  出棧并寫入到s2中
           while(Peek(R)!='(')
                        s2[j++]=Pop(R);
           Pop(R);  //  刪除棧頂的左括號
           ch=s1[++i];
          }
          else if(ch=='+'ch=='-'ch=='*'ch=='/')
          {    //  對于四則運算符，使暫存在棧中的不低于ch優先級
            //  的運算符依次出棧并寫入到s2中
           char w=Peek(R);
           while(PRecedence(w)>=Precedence(ch))
                    {    //   Precedence(w)函數返回運算符形參的優先級
            s2[j++]=w;
            Pop(R); w=Peek(R);
         &n


發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板： 辽阳县| 江安县| 阳原县| 东至县| 永康市| 高州市| 延安市| 武平县| 临朐县| 南漳县| 凌云县| 闽侯县| 铜鼓县| 温泉县| 石狮市| 梓潼县| 宜阳县| 宽甸| 犍为县| 北川| 辽中县| 凤翔县| 庐江县| 贵阳市| 治多县| 个旧市| 阜康市| 清水河县| 永年县| 扎兰屯市| 博野县| 新津县| 灵石县| 呈贡县| 大足县| 固始县| 湖南省| 西丰县| 海原县| 松潘县| 凭祥市|