后缀表达式

洛谷模板地址：https://www.luogu.org/problemnew/show/P1175

 

介绍

数学表达式分为三种：前缀表达式、中缀表达式、后缀表达式。

前缀表达式的运算符在两个运算数字（或表达式）前，中缀表达式的运算符在两个运算数字（或表达式）之间。后缀表达式的运算符在两个运算数字（或表达式）后。

举个栗子：

 8-(3+2*6)/5+2^2

前缀表达式：+ ^ 2 2 - / 5 + * 6 2 3 8

后缀表达式：8 3 2 6 * + 5 / - 2 2 ^ +

 

后缀表达式的计算方法：

从左向右，每遇到一个运算符，就讲前两个数字进行该运算，再将运算结果放到该位置

比如刚才的后缀表达式：8 3 2 6 * + 5 / - 2 2 ^ +

第一步*运算：8 3 12 + 5 / - 2 2 ^ +

第二步+运算：8 15 5 / - 2 2 ^ +

第三步/运算：8 3 - 2 2 ^ +

第四步：5 2 2 ^ +

第五步：5 4 +

第六步：9

 

在计算机中，我们通常这样实现： 从左向右遍历，遇到数就入栈，遇到运算符就从栈顶弹出两个元素，将后弹出的与先弹出的进行运算（运算顺序从左到右），再将运算结果入栈，直到栈中只有一个元素（或遍历完整个后缀表达式）

随手贴个代码

 1 void work(char a) 2 { 3     int x,y; 4     y=stack[tot--]; 5     x=stack[tot--]; 6     switch(a) 7     { 8         case '+':stack[++tot]=x+y;break; 9         case '-':stack[++tot]=x-y;break;10         case '*':stack[++tot]=x*y;break;11         case '/':stack[++tot]=x/y;break;12         case '^':stack[++tot]=pow(x,y);break;13     }14 }

 

中缀表达式转后缀表达式

我们平时日常生活中使用的就是中缀表达式，但后缀表达式便于计算机处理，所以我们常需要把中缀表达式转变后缀表达式。那么如何将中缀表达式转变为后缀表达式呢？

 

一、手算方法：

1、二叉树法：将每一个运算符放在树根，其两个运算部分（数字或表达式）放在左右孩子（按照原先顺序！），若此运算符前有同括号内运算符，则判断其优先级，优先级高的放在孩子，优先级低的放在父亲

2、括号法：按照运算顺序将每两个运算部分都加上括号，将每个括号内的运算符放到括号外，再将括号去掉即可

此处不是这篇文章的重点故不再赘述。想要深入了解的读者可以自行查阅资料

 

二、计算机实现方法：

从左向右遍历中缀表达式，遇到数字就直接写入后缀表达式；遇到运算符，若它比栈顶的运算符的优先级高，则直接入栈，若它比栈顶的运算符的优先级低，出栈直到它不比栈顶的运算符的优先级低，将出栈的运算符按出栈顺序放入后缀表达式并将当前运算符入栈；遇到左括号直接入栈；遇到右括号，出栈直到左括号，将出栈的运算符按出栈顺序放入后缀表达式。

这里有两个小tips：

1、判断运算符的优先级：利用哈希思想，用一个数组youxianji[]存放，变量就是运算符的ASCLL值，数值越大优先级越大。此方法一举两得，因为还能同时处理读入运算符时出栈到左括号的问题（左括号优先级为0）（我绝对不会告诉你百度百科的优先级判断函数就写了20行）

2、栈问题：后缀表达式的转换和计算都需要栈，但其实只需开一个int栈就可以了（字符会用ACSLL码储存）

 

代码如下（超简洁只有80行）

 1 #include<iostream> 2 #include<cstdio> 3 #include<string> 4 #include<cmath> 5 using namespace std; 6 string input,houzhui; 7 int tot,stack[1111];//栈组件  8 int youxianji[1111];//优先级hash表  9 void print1()10 {11     for(int i=0;i<houzhui.length();i++)12         printf("%c ",houzhui[i]);13     printf("\n");14 }15 void work(char a)//计算 16 {17     int x,y;18     y=stack[tot--];19     x=stack[tot--];20     switch(a)21     {22         case '+':stack[++tot]=x+y;break;23         case '-':stack[++tot]=x-y;break;24         case '*':stack[++tot]=x*y;break;25         case '/':stack[++tot]=x/y;break;26         case '^':stack[++tot]=pow(x,y);break;27     }28 }29 void print2(int x,int length)//栈中元素为计算所得，字符串中元素为未处理 30 {31     for(int i=1;i<=tot;i++)32         printf("%d ",stack[i]);33     for(int i=x;i<length;i++)34         printf("%c ",houzhui[i]);35     printf("\n");36 }37 int main()38 {39     youxianji['+']=youxianji['-']=1;//预处理优先级 40     youxianji['*']=youxianji['/']=2;41     youxianji['^']=3;42     cin>>input;43     for(int i=0;i<input.length();i++)44     {45         if(input[i]>='0'&&input[i]<='9')//数字，入栈 46             houzhui+=input[i];47         else if(input[i]=='(')//左括号，入栈 48             stack[++tot]=input[i];49         else if(input[i]==')')//右括号，出栈直到左括号 50         {51             while(stack[tot]!='(')52                 houzhui+=stack[tot--];53             tot--;//不要忘记将左括号出栈！ 54         }55         else//运算符，出栈直到栈顶运算符的优先级小于当前运算符的优先级 56         {57             while(youxianji[stack[tot]]>=youxianji[input[i]])58                 houzhui+=stack[tot--];59             stack[++tot]=input[i];60         }61     }62     while(tot)//一定要将栈中剩余元素入栈！ 63         houzhui+=stack[tot--];64     print1();65     tot=0;66     int length=houzhui.length();67     for(int i=0;i<length;i++)68     {69         if(houzhui[i]>='0'&&houzhui[i]<='9')//将数字入栈 70             stack[++tot]=houzhui[i]-'0';//不要忘记-'0'71         else72         {73             work(houzhui[i]);//遇到运算符，计算 74             print2(i+1,length);75         }76     }77     return 0;78 }

几点注意事项：

1、遇到右括号出栈时记得将左括号出栈！

2、转换完成后要将栈中所有元素出栈！

3、计算时将数字入栈记得-'0'！（我第一次就栽在这里……）

 

PS:洛谷的模板保证数字是一位数……多位数的处理会麻烦一些，留给读者自己思考实现

原文出处：https://www.cnblogs.com/LiHaozhe/p/9475072.html