前缀、中缀、后缀表达式之间的相互转换及部分实现数据结构

背景介绍前缀表达式（又称为波兰表达式）
中缀表达式
后缀表达式（又称为逆波兰表达式）
平时我们见到的都是：2+3*5，这样的算数表达式（中缀），我们数学中也就是用这种
这种表达式（中缀）只适合人来读写，不适合计算机，所以为了方便计算机读取正确的表达式就有了前缀和后缀表达式
本文将会介绍：前缀转中缀，中缀转前缀
中缀转后缀，后缀转中缀
前后缀之间的相互转换可以用中缀作为中间商来解决，或者也可以构造语法树遍历来解决

前缀转后缀的具体实现代码（构造树实现）
https://www.cnblogs.com/breakthings/p/4053444.html

例子：2+（3-1）*4（中缀，语法树中序遍历可以得到）
231-4 * + （后缀，语法树后序遍历可以得到，其他方法得到也行，表达式不唯一）
+2*-314 （前缀，语法树先序遍历可以得到）
为了方便理解，我画了表达式的语法树：
叶子节点都是数，非叶子节点都是运算符。画图很简单就不赘述了

文章图片

1. 中缀转前缀 【前缀、中缀、后缀表达式之间的相互转换及部分实现】如果仅仅是写题目，仅需把语法树用前序遍历（又称为先序遍历）一遍即可得到答案 +2*-314(前缀表达式)
但一般实现是使用栈
思路：

首先要处理字符串，运算符的优先级，多位数字看成整体（比如23看成一个整体而不是2和3），我的例子中没那么复杂
创建两个栈，一个是数字栈（里面存的是最终结果），一个是运算符栈
从右往左扫描中缀表达式
若是运算符，则与运算符栈顶元素比较优先级：
若该运算符优先级大于等于栈顶元素，则将该运算符入栈；
若该运算符优先级小于栈顶元素，则运算符栈内元素出栈并压入数字栈，再与其比较，直到该运算符优先级大于等于栈顶元素的优先级时，将该运算符压入栈中。
注意：我们先在运算符栈中压入一个‘#’ 规定其优先级为最低这样解决了开始时候的边界问题）
注意：遇到右括号直接压入栈中，遇到一个左括号，那么就将运算符栈元素弹出并压入数字栈直到遇到右括号，并且把右括号弹出，停止弹出。这个过程，两个括号都不加入数字栈。
表达式遍历完后，若运算符栈还有元素，则依次弹出压入数字栈。
把数字栈元素从栈顶依次弹出，就得到前缀表达式。

代码实现：

例：1-(2+3) 转换前缀是：- 1 + 2 3
例：1+((2+3)*4)-5 转换前缀是：- + 1 * + 2 3 4 5
例：123+((246+39)*48)-55 转换前缀是：- + 123 * + 246 39 48 55
参考博客：https://blog.csdn.net/holly_Z_P_F/article/details/98724274

#include #include #include #include using namespace std; const int maxn=1005; typedef struct NODE{ string ch; int level; }NODE; NODE node[maxn]; string s; int change(){ int w1=0; for(int i=0; i.size(); i++){//划分优先级 if(s[i]=='*'||s[i]=='/'){ node[w1].ch=s[i]; node[w1++].level=2; } else if(s[i]=='+'||s[i]=='-'){ node[w1].ch=s[i]; node[w1++].level=1; } else if(s[i]=='('||s[i]==')'){ node[w1].ch=s[i]; node[w1++].level=0; } else if(s[i]>='0'&&s[i]<='9'){ //分割字符串 int j=i; while(s[j]>='0'&&s[j]<='9'){ j++; } node[w1].ch=s.substr(i,j-i); node[w1].level=100; w1++; i=j-1; } } return w1; } void solove(int l){ NODE ans[maxn]; //结果栈 NODE q[maxn]; //运算符栈 int w2=0,w3=0; q[w3].ch="#"; q[w3++].level=-1; //先压入 # for(int i=l-1; i>=0; i--){ if(node[i].level==100){ ans[w2++]=node[i]; } else{ if(node[i].ch==")") q[w3++]=node[i]; else if(node[i].ch=="("){ while(q[w3-1].ch!=")"){ w3--; ans[w2++]=q[w3]; //压入结果栈 } w3--; } else{ while(node[i].level=0; i--){//倒序输出 cout<>s; //输入表达式 int l=change(); //处理表达式 solove(l); //转换为前缀表达式 return 0; }

2. 前缀转中缀（这一点网上的资料很少）
例子：+2*-314（前缀）-----> 2+（（3-1）*4）（中缀）
思路：准备一个栈

从右往左扫描前缀表达式
遇见数字压入数字栈
遇见运算符栈，则弹出数字栈的两个元素，并且运算，前后还要添加括号，然后压入栈
例如：栈中有2和3（2个元素），现在遇见+了，则把（2+3）压入栈，栈中现在就有5个元素了，后面的依次类推
结果中肯定会出现很多多余的括号，也可以解决但是比较复杂就不详细说了

代码实现：实现起来较为复杂，有机会补上…
3. 中缀转后缀写答案的话后序遍历的语法树，可以直接得到答案
思路：和中缀转前缀差不多，只是方向改变了

从左往右扫描中缀表达式
其他的与中缀转前缀的操作一样

这里有一篇图解博客，方便大家理解
https://www.cnblogs.com/lanhaicode/p/10776166.html

4. 后缀转中缀思路：与前缀转中缀的思路一样

从右往左扫描后缀表达式
遇见数字压入数字栈
遇见运算符栈，则弹出数字栈的两个元素，并且运算，前后还要添加括号，然后压入栈
例如：栈中有2和3（2个元素），现在遇见+了，则把（2+3）压入栈，栈中现在就有5个元素了，后面的依次类推

1 2 3 + 4 *5 - +

例如：
从左往右扫描先碰到+号，取+号前面两个操作数：2，3 得到：（2+3）.
继续往下扫碰到*号，取4 和2+3 得到：（（2+3）*4）
-号，取（2+3）*4和5得到：：（（（2+3）*4）-5））
+号：取（2+3）*4-5和1得到：：1+（（（2+3）*4）-5））
如果把多余的括号省略就是1+（2+3）*4-5
如有错误，不吝赐教