“中序表达式”转换为“前序表达式”、“后序表达式”

青旅半醒 2022-07-18 01:21 150阅读 0赞

上周末参照书本写了个“计算器”的程序，其中最令我费解的就是“前序表达式”、“后续表达式”，好像记得老师在上课的时候讲过，估计当时也没听懂，看的稀里糊涂的，不过现在大概明白了……

在此仅做以笔记。

首先看下面所示表格：

<table style="margin:0px; padding:0px; border-collapse:collapse; border-spacing:0px; border:medium none; word-break:break-word; color:rgb(57,57,57); font-family:verdana,&quot;ms song&quot;,Arial,Helvetica,sans-serif; font-size:14px; line-height:21px; background-color:rgb(250,247,239)"> 
 <tbody style="margin:0px; padding:0px"> 
  <tr style="margin:0px; padding:0px; height:17.9pt"> 
   <td style="margin:0px; padding:0cm 5.4pt; border:1pt solid windowtext; border-collapse:collapse; width:192.05pt; height:17.9pt; background-color:transparent"> <p style="margin:10px auto; padding-top:0px; padding-bottom:0px"><span style="margin:0px; padding:0px; font-family:宋体">中序表达式</span></p> </td> 
   <td style="margin:0px; padding:0cm 5.4pt; border-top-width:1pt; border-right-width:1pt; border-bottom-width:1pt; border-top-style:solid; border-right-style:solid; border-bottom-style:solid; border-color:windowtext windowtext windowtext rgb(236,233,216); border-collapse:collapse; width:192.1pt; height:17.9pt; background-color:transparent"> <p style="margin:10px auto; padding-top:0px; padding-bottom:0px">2*3/(2-1)+3*(4-1)</p> </td> 
  </tr> 
  <tr style="margin:0px; padding:0px; height:17.05pt"> 
   <td style="margin:0px; padding:0cm 5.4pt; border-right-width:1pt; border-bottom-width:1pt; border-left-width:1pt; border-right-style:solid; border-bottom-style:solid; border-left-style:solid; border-color:rgb(236,233,216) windowtext windowtext; border-collapse:collapse; width:192.05pt; height:17.05pt; background-color:transparent"> <p style="margin:10px auto; padding-top:0px; padding-bottom:0px"><span style="margin:0px; padding:0px; font-family:宋体">前序表达式</span></p> </td> 
   <td style="margin:0px; padding:0cm 5.4pt; border-right-width:1pt; border-bottom-width:1pt; border-right-style:solid; border-bottom-style:solid; border-color:rgb(236,233,216) windowtext windowtext rgb(236,233,216); border-collapse:collapse; width:192.1pt; height:17.05pt; background-color:transparent"> <p style="margin:10px auto; padding-top:0px; padding-bottom:0px">+/*23-21*3-41</p> </td> 
  </tr> 
  <tr style="margin:0px; padding:0px; height:17.9pt"> 
   <td style="margin:0px; padding:0cm 5.4pt; border-right-width:1pt; border-bottom-width:1pt; border-left-width:1pt; border-right-style:solid; border-bottom-style:solid; border-left-style:solid; border-color:rgb(236,233,216) windowtext windowtext; border-collapse:collapse; width:192.05pt; height:17.9pt; background-color:transparent"> <p style="margin:10px auto; padding-top:0px; padding-bottom:0px"><span style="margin:0px; padding:0px; font-family:宋体">后序表达式</span></p> </td> 
   <td style="margin:0px; padding:0cm 5.4pt; border-right-width:1pt; border-bottom-width:1pt; border-right-style:solid; border-bottom-style:solid; border-color:rgb(236,233,216) windowtext windowtext rgb(236,233,216); border-collapse:collapse; width:192.1pt; height:17.9pt; background-color:transparent"> <p style="margin:10px auto; padding-top:0px; padding-bottom:0px">23*21-/341-*+</p> </td> 
  </tr> 
 </tbody> 
</table>

中序表达式对我们而言是很直观的（我们平时接触的就是这个），但计算机处理起来比较麻烦（括号、优先级之类的），前序和后序表达式中没有括号，而且在计算中只需单向扫描，不需要考虑运算符的优先级。  
　　以前序表达式“+/\*23-21\*3-41”为例，从右往左，先取出两个操作数“1”、“4”和一个运算符“-”，计算“4-1”，将结果3回填到字符串中，现在字符串变为“+/\*23-21\*33”。  
　　再从右至左取两个数“3”、“3”和“\*”，计算“3\*3”，将结果“9”回填到字符串，得“+/\*23-219’”,

再取数，连续取出“9”、“1”、“2”，直到取出一个运算符“-”，将与运算符最近的两个操作数进行计算，即“2-1”得“1”，回填字符串中，现在为“+/\*239”  
　　重复上述步骤，取出“2\*3”=6，回填字符串得到“+/619”，

再取“6/1”=6，得到“+69”,

再取“6+9”=15。运算完毕。

即从右至左取数，直到取出一个运算符，将刚取出的紧挨着运算符的两个操作数按运算符进行计算，结果回填至运算符。重复该步骤，直到最后只剩下一个字符串则剩下的字符串即为结果。  
　　后序表达式的字符串扫描方式正好和前序相反，是从左往右扫描，规则类似。

![复制代码][copycode.gif]

中序表达式转前序表达式步骤  
 1 、反转输入字符串，如“ 2 \* 3 / ( 2 \- 1 ) \+ 3 \* ( 4 \- 1 )” 反转后为“ ) 1 \- 4 ( \* 3 \+ ) 1 \- 2 ( / 3 \* 2 ”，  
 2 、从字符串中取出下一个字符  
　　 2.1 .如果是操作数，则直接输出  
　　 2.2 .如果是“)”，压入栈中  
　　 2.3 .如果是运算符但不是“(”，“)”,则不断循环进行以下处理  
　　　　 2.3.1. 如果栈为空，则此运算符进栈，结束此步骤  
　　　　 2.3.2. 如果栈顶是“)”,则此运算符进栈，结束此步骤  
　　　　 2.3.2. 如果此运算符与栈顶优先级相同或者更高，此运算符进栈，结束此步骤  
　　　　 2.3.4. 否则，运算符连续出栈，直到满足上述三个条件之一，然后此运算符进栈  
　　 2.4 、如果是“(”，则运算符连续出栈，直到遇见“)”为止,将“)”出栈且丢弃之  
 3 、如果还有更多的字符串，则转到第2步  
 4 、不在有未处理的字符串了，输出栈中剩余元素  
 5 、再次反转字符串得到最终结果

![复制代码][copycode.gif]

我第一次看到这个的时候就没看懂是什么意思，在网上查了点，又瞪了它好久才明白了，就以“2\*3/(2-1)+3\*(4-1)，”为例做以下说明：  
　　2\*3/(2-1)+3\*(4-1)，反转得“ )1-4(\*3+)1-2(/3\*2 ”；  
　　取第一个字符串为“）”，入栈（此时栈中为“）”）；  
　　取下一个“1”，是操作数，直接输出（目前输出“1”）；  
　　取下一个“-”，既不是“)”,也不是“（”，则转到2.3，此时栈顶为“）”,则该运算符进栈（栈中为“-、）”）；  
　　取下一个“4”，直接输出（目前输出的是“14”）；  
　　取下一个“(”，运算符连续出栈（栈中此时为“-、）”），直到遇见“)”,此时输出“-”（目前输出“14-”，栈为空）；  
　　取下一个“\*”，既不是“)”,也不是“（”，则转到2.3，进栈（栈为空）；  
　　取下一个“3”，直接输出（目前输出“14-3”）；  
　　取下一个“+”，此时栈顶为“\*”,“+”的优先级比“\*”低（2.3.4），则运算符连续出栈（只有一个\*出栈，此时栈为空符合2.3.1，继续下一步），“+”进栈；  
　　取下一个“)”，进栈（此时栈中为“）、+”）；  
　　取下一个“1”直接输出（目前输出为14-3\*1）；  
　　取下一个“-”，此时栈顶为“）”，“-”进栈（栈中此时为“-、）、+”）；  
　　取下一个“2”，直接输出（目前输出“14-3\*12”）；  
　　取下一个“（”，运算符连续出栈，直到遇见“）”，此时栈中为“-、）、+”，输出-，且抛弃“）”，此时输出为“14-3\*12-”,栈中为“+”；  
　　取下一个“/”，优先级比栈顶“+”高，此运算符进栈；  
　　取下一个“3”，直接输出（此时输出“14-3\*12-3”）；  
　　取下一个“\*”，优先级比栈顶“+”高，此运算符进栈；  
　　取下一个“2”，输出（此时输出“14-3\*12-32”）；  
　　不在有未处理的运算符，输出栈中剩余元素,结果的“14-3\*12-32\*/+”；  
　　反转字符串的“+/\*23-21\*3-41”。

程序实现完整代码

![ExpandedBlockStart.gif][]

![复制代码][copycode.gif]

using  System;  
 using  System.Collections.Generic;  
 using  System.Linq;  
 using  System.Text;  
 using  System.Collections;  
  
  
 namespace  ConsoleApplication7  
\{  
     class  program  
    \{  
         static   void  Main()  
        \{  
            MyExpression myExpr  =   new  MyExpression();  
             // string str = "5.5+8\*3-(4\*2)";   
              string  str  =   " 2\*3/(2-1)+3\*(4-1) " ;  
             // string str = "5\*4-1";   
             Console.WriteLine( " 原表达式： "   \+  str);  
            myExpr.Expression  =  str;  
            myExpr.calcaute();  
            Console.ReadKey();  
        \}  
  
    \}  
  
     class  MyExpression  
    \{  
         ///   <summary>   
         ///  运算表达式  
         ///   </summary>   
          public   string  Expression  
        \{  
             get ;  
             set ;  
        \}  
  
         //  新的表达式（由前序或后续表达式转换而来，即最终参与运算的表达式）           
          private  ArrayList newExpression  =   new  ArrayList();  
  
         // 队列  ，对数据处理，识别数字，如11+8识别出11和8    
          private  Queue queueTmp  =   new  Queue();  
  
         // 数组，将转变后的数据放入数组   
          private  ArrayList arrltmp  =   new  ArrayList();  
  
         // 栈，将中序表达式转为前序表达式时使用   
         Stack stackTmp  =   new  Stack();  
  
         \#region  处理字符串中的数字   
  
         ///   <summary>   
         ///  处理字符串中的数字  
         ///   </summary>   
          private   void  HandleNumberinExpression()  
        \{  
             string  expression  =   this .Expression.Trim();  
             foreach  ( char  character  in  Expression)  
            \{                  
                 string  tmp  =   "" ;  
                 // 如果不是运算符，则放入Queue，直到遇到运算符，   
                  if  ( ! IsOperator(character.ToString()))  
                \{  
                    queueTmp.Enqueue(character.ToString());  
                \}  
                 else   
                \{  
                     // 运算符，先将Queue中的数据输出从而得到一个数字(如1和1，得到11)，并将得到的数字放入ArrayList   
                      int  count  =  queueTmp.Count;  
                     // Count不为0 ，里面存放的就是数字，否则就是null（连着几个运算符情况，如“\*（”）   
                      if  (count  !=   0 )  
                    \{  
                         for  ( int  i  =   0 ; i  <  count; i \++ )  
                        \{  
                            tmp  \+=  queueTmp.Dequeue();  
                        \}  
                        arrltmp.Add(tmp);  
                    \}  
                     // 放入运算符   
                     arrltmp.Add(character.ToString());  
                \}  
            \}  
             // 得到最后一个数字(最后一个不是“）”，就是数字)   
              string  end  =   "" ;  
             int  QueueCount  =  queueTmp.Count;  
             if  (QueueCount  !=   0 )  
            \{  
                 for  ( int  i  =   0 ; i  <  QueueCount; i \++ )  
                \{  
                    end  \+=  queueTmp.Dequeue();  
                \}  
                arrltmp.Add(end);  
            \}               
        \}  
  
         \#endregion          
  
  
         \#region  将中序表达式转为后序表达式   
  
         ///   <summary>   
         ///  将中序表达式转为后序表达式  
         ///   </summary>   
          private   void  ChangeMiddleToAfter()  
        \{             
             foreach  ( string  s  in  arrltmp)  
            \{  
                 // 如果是操作数，直接输出   
                  if  ( ! IsOperator(s))  
                \{                    
                    newExpression.Add(s);  
                \}  
                 // 如果是“（”，压入栈中   
                  else   if  (s  ==   " ( " )  
                \{  
                    stackTmp.Push(s);  
                \}  
                 // 如果是右括号，则运算符连续出栈，直到遇见左括号为止，左括号出栈且丢弃它   
                  else   if  (s  ==   " ) " )  
                \{  
                     // 右括号   
                      while  (stackTmp.Count  >   0   &&  stackTmp.Peek().ToString()  !=   " ( " )  
                    \{  
                         string  ss  =  stackTmp.Pop().ToString();                        
                        newExpression.Add(ss);  
                    \}  
                    stackTmp.Pop();  
                \}  
                 // 是运算符，且不是右括号，不断循环进行   
                  else   
                \{  
                     // 如果栈为空，次运算符进栈，结束此步骤，取下一个字符   
                      if  (stackTmp.Count  ==   0 )  
                    \{  
                        stackTmp.Push(s);  
                    \}  
                     // 如果栈顶是“（”，此运算符进栈，结束次步骤，读取下一个字符   
                      else   if  (stackTmp.Peek().ToString()  ==   " ( " )  
                    \{  
                        stackTmp.Push(s);  
                    \}  
                     // 如果此运算符与栈顶优先级相同或更高，此运算符进栈，结束次步骤，取下一个字符，   
                      else   if  (myOperator.notBiggerthan(s.ToString(), stackTmp.Peek().ToString()))  
                    \{  
                       newExpression.Add(stackTmp.Pop());  
                        stackTmp.Push(s);  
                    \}  
                     // 否则，运算符连续出栈，直至满足上述三个条件之一退出此步骤   
                      else   
                    \{  
                         do   
                        \{                            
                            stackTmp.Push(s);                              
                        \}  while  ( ! (stackTmp.Count  ==   0   ||   
                            stackTmp.Peek().ToString()  ==   " ( "   ||   
                            myOperator.notBiggerthan(s.ToString(), stackTmp.Peek().ToString())));  
                    \}  
                \}  
            \}  
             while  (stackTmp.Count  !=   0 )  
            \{  
                 string  popstr  =  stackTmp.Pop().ToString();              
                newExpression.Add(popstr);  
            \}  
        \}  
         \#endregion   
  
  
         \#region  将中序表达式转为前序表达式   
  
         ///   <summary>   
         ///  将中序表达式转为前序表达式  
         /// </summary>   
          private   void  ChangeMiddleToBefore()  
        \{  
             // 将处理后的数组反转   
             arrltmp.Reverse();              
             foreach  ( string  s  in  arrltmp)  
            \{                           
                 // 如果是操作数，直接输出   
                  if  ( ! IsOperator(s))  
                \{                   
                    newExpression.Add(s);  
                \}  
                 // 如果是“）”，压入栈中   
                  else   if  (s  ==   " ) " )  
                \{  
                    stackTmp.Push(s);  
                \}  
                 // 如果是左括号，则运算符连续出栈，直到遇见右括号为止，右括号出栈且丢弃它   
                  else   if  (s  ==   " ( " )  
                \{  
                     // 右括号   
                      while  (stackTmp.Count  >   0   &&  stackTmp.Peek().ToString()  !=   " ) " )  
                    \{  
                         string  ss  =  stackTmp.Pop().ToString();                          
                        newExpression.Add(ss);  
                    \}  
                    stackTmp.Pop();  
                \}  
                 // 是运算符，且不是左括号，不断循环进行   
                  else   
                \{  
                     // 如果栈为空，次运算符进栈，结束此步骤，取下一个字符   
                      if  (stackTmp.Count  ==   0 )  
                    \{  
                        stackTmp.Push(s);  
                    \}  
                     // 如果栈顶是“）”，此运算符进栈，结束次步骤，读取下一个字符   
                      else   if  (stackTmp.Peek().ToString()  ==   " ) " )  
                    \{  
                        stackTmp.Push(s);  
                    \}  
                     // 如果此运算符与栈顶优先级相同或更高，此运算符进栈，结束次步骤，取下一个字符，   
                      else   if  (myOperator.notLessthan(s.ToString(), stackTmp.Peek().ToString()))  
                    \{  
                        stackTmp.Push(s);  
                    \}  
                     // 否则，运算符连续出栈，直至满足上述三个条件之一退出此步骤   
                      else   
                    \{  
                         do   
                        \{  
                             string  podstr  =  stackTmp.Pop().ToString();                             
                            newExpression.Add(podstr);  
                        \}  while  ( ! (stackTmp.Count  ==   0   ||   
                            stackTmp.Peek().ToString()  ==   " ) "   ||   
                            myOperator.notLessthan(s.ToString(), stackTmp.Peek().ToString())));  
  
                        stackTmp.Push(s);  
                         
                    \}  
                \}  
            \}  
             while (stackTmp.Count  !=   0 )  
            \{  
                 string  popstr  =  stackTmp.Pop().ToString();               
                newExpression.Add(popstr);  
            \}  
        \}  
         \#endregion     
  
         ///   <summary>   
         ///  计算  
         ///   </summary>   
          public   void  calcaute()  
        \{  
             // 进行第一次处理，识别数字   
             HandleNumberinExpression();  
  
             // 中序表达式转为后序表达式   
             ChangeMiddleToAfter();  
            Console.Write( " 后序表达式： " );  
             foreach  ( string  t  in  newExpression)  
            \{  
                Console.Write(t);  
            \}  
            calcauteAfterExpression();  
  
             /// /中序表达式转为前序表达式   
              // ChangeMiddleToBefore();  
             // Console.Write("倒序的前序表达式：");  
             // foreach (string t in newExpression)  
             // \{  
             //     Console.Write(t);  
             // \}  
             // calcauteBeforeExpression();   
   
            Console.WriteLine( " \\n计算结果：  "   \+  newExpression\[ 0 \]);  
        \}  
  
         \#region  计算前序表达式   
  
         ///   <summary>   
         ///  计算前序表达式  
         ///   </summary>   
          private   void  calcauteBeforeExpression()  
        \{  
             double  result  =   0 ;  
             if  (newExpression.Count  >   1 )  
            \{  
                 int  i  =   0 ;  
                 for  (i  =   0 ; i  <  newExpression.Count; i \++ )  
                \{  
                     if  (IsOperator(newExpression\[i\].ToString()))  
                    \{  
                         if  (newExpression\[i\].ToString()  ==   " \+ " )  
                        \{  
                            result  =  Convert.ToDouble(newExpression\[i  \-   1 \])  \+  Convert.ToDouble(newExpression\[i  \-   2 \]);  
                        \}  
                         else   if  (newExpression\[i\].ToString()  ==   " \- " )  
                        \{  
                            result  =  Convert.ToDouble(newExpression\[i  \-   1 \])  \-  Convert.ToDouble(newExpression\[i  \-   2 \]);  
                        \}  
                         else   if  (newExpression\[i\].ToString()  ==   " \* " )  
                        \{  
                            result  =  Convert.ToDouble(newExpression\[i  \-   1 \])  \*  Convert.ToDouble(newExpression\[i  \-   2 \]);  
                        \}  
                         else   if  (newExpression\[i\].ToString()  ==   " / " )  
                        \{  
                            result  =  Convert.ToDouble(newExpression\[i  \-   1 \])  /  Convert.ToDouble(newExpression\[i  \-   2 \]);  
                        \}  
                         break ;  
                    \}  
                \}  
                newExpression\[i\]  =  result;  
                newExpression.RemoveAt(i  \-   1 );  
                newExpression.RemoveAt(i  \-   2 );  
                calcauteBeforeExpression();  
            \}  
             else   
            \{  
                 
            \}  
        \}  
         \#endregion   
  
         \#region  计算后序表达式   
         ///   <summary>   
         ///  计算后序表达式  
         ///   </summary>   
          private   void  calcauteAfterExpression()  
        \{  
             double  result  =   0 ;  
             if  (newExpression.Count  >   1 )  
            \{  
                 int  i  =   0 ;  
                 for  (i  =   0 ; i  <  newExpression.Count; i \++ )  
                \{  
                     if  (IsOperator(newExpression\[i\].ToString()))  
                    \{  
                         if  (newExpression\[i\].ToString()  ==   " \+ " )  
                        \{  
                            result  =  Convert.ToDouble(newExpression\[i  \-   2 \])  \+  Convert.ToDouble(newExpression\[i  \-   1 \]);  
                        \}  
                         else   if  (newExpression\[i\].ToString()  ==   " \- " )  
                        \{  
                            result  =  Convert.ToDouble(newExpression\[i  \-   2 \])  \-  Convert.ToDouble(newExpression\[i  \-   1 \]);  
                        \}  
                         else   if  (newExpression\[i\].ToString()  ==   " \* " )  
                        \{  
                            result  =  Convert.ToDouble(newExpression\[i  \-   2 \])  \*  Convert.ToDouble(newExpression\[i  \-   1 \]);  
                        \}  
                         else   if  (newExpression\[i\].ToString()  ==   " / " )  
                        \{  
                            result  =  Convert.ToDouble(newExpression\[i  \-   2 \])  /  Convert.ToDouble(newExpression\[i  \-   1 \]);  
                        \}  
                         break ;  
                    \}  
                \}  
                newExpression\[i\]  =  result;  
                newExpression.RemoveAt(i  \-   1 );  
                newExpression.RemoveAt(i  \-   2 );  
                calcauteAfterExpression();  
            \}  
             else   
            \{  
                 // Console.WriteLine(result);   
             \}  
        \}  
         \#endregion   
  
         \#region  判断是否是运算符，包括+-\*/（）   
         ///   <summary>   
         ///  判断是否是运算符，包括+-\*/（）  
         ///   </summary>   
         ///   <param name="character"></param>   
         ///   <returns></returns>   
          private   bool  IsOperator( string  str)  
        \{  
             if  (str.ToString()  !=   " \+ "   &&  str.ToString()  !=   " \- "   &&  str.ToString()  !=   " \* "   &&  str.ToString()  !=   " / "   &&  str.ToString()  !=   " ( "   &&  str.ToString()  !=   " ) " )  
            \{  
                 return   false ;  
            \}  
             else   
            \{  
                 return   true ;  
            \}  
        \}  
  
         \#endregion   
    \}  
  
  
  
     class  myOperator  
    \{  
         ///   <summary>   
         ///  比较运算符优先级，operator\_1不小于operator\_2  
         ///   </summary>   
         ///   <param name="operator\_1"></param>   
         ///   <param name="operator\_2"></param>   
         ///   <returns></returns>   
          public   static   bool  notLessthan( string  operator\_1,  string  operator\_2)  
        \{  
             int  tmp\_1  =  change(operator\_1);  
             int  tmp\_2  =  change(operator\_2);  
             if  (tmp\_1  >=  tmp\_2)  
            \{  
                 return   true ;  
            \}  
             else   
            \{  
                 return   false ;  
            \}  
        \}  
  
         ///   <summary>   
         ///  比较运算符优先级，operator\_1不大于operator\_2  
         ///   </summary>   
         ///   <param name="operator\_1"></param>   
         ///   <param name="operator\_2"></param>   
         ///   <returns></returns>   
          public   static   bool  notBiggerthan( string  operator\_1,  string  operator\_2)  
        \{  
             int  tmp\_1  =  change(operator\_1);  
             int  tmp\_2  =  change(operator\_2);  
             if  (tmp\_1  <=  tmp\_2)  
            \{  
                 return   true ;  
            \}  
             else   
            \{  
                 return   false ;  
            \}  
        \}  
  
         ///   <summary>   
         ///  给运算符赋优先级  
         ///   </summary>   
         ///   <param name="myOperator"></param>   
         ///   <returns></returns>   
          private   static   int  change( string  myOperator)  
        \{  
             switch  (myOperator)  
            \{  
                 case   " \+ " :  
                     return   1 ;  
                 case   " \- " :  
                     return   1 ;  
                 case   " \* " :  
                     return   2 ;  
                 case   " / " :  
                     return   2 ;  
                 default :  
                     return   0 ;  
            \}  
        \}  
    \}  
\}

![复制代码][copycode.gif]

在上述处理中需要首先对输入的字符串进行处理，识别出运算符和操作数，另外在计算前序表达式结果的时候我并没有将其反转，而是直接参与了运算（计算的时候是从左往右计算的，参与运算的是反转的前序表达式，结果是一样的）。

参考书籍：《.NET 2.0 面向对象揭秘》

[copycode.gif]: /images/20220717/184d592ffe374d8da4b3e5062b728d31.png
[ExpandedBlockStart.gif]: /images/20220717/c161eb978fdd4fd08c7a29ad6fb66270.png