文章目录

背景知识表达式转换问题（考研经典）一：手工转换（1）中缀转前缀和中缀转后缀（2）前缀转中缀和后缀转中缀二：用栈实现表达式转换（1）中缀转后缀（2）中缀转前缀表达式计算问题（使用栈实现）

背景知识

中缀表达式：a+b

前缀表达式（波兰式）：+ab

后缀表达式（逆波兰式）：ab+

表达式转换问题（考研经典）

一：手工转换

考研中有一类经典的问题就是表达式的转换问题，经常要把一个类型的表达式转换为另一个类型的表达式

所以这里我们主要说一下中缀转前缀，前缀转中缀，中缀转后缀和后缀转中缀即可。这样这三种形式任意两个之间的转换都可以借助上面四种转换直接或间接完成

所用表达式的三种形式如下

（1）中缀转前缀和中缀转后缀

首先每遇到两个操作数，一个运算符就把他们用括号扣起来（用括号括起来的可以看做一个操作数）

如下

把上面的结果全部抄一遍（对应位置，不要错乱），抄的时候不要抄操作数，把操作数的位置空出来。然后依据原来的结果，把运算符移出到括号前面面，注意只需要移动到该运算符原来所在的括号前面就可以了，不要一次移动多层

如下

转化为后缀表达式时，只需要移动到括号后面就可以了，由于非常简单，这里我就不演示了，结果在最上面

（2）前缀转中缀和后缀转中缀

前缀转中缀时，从后向前扫描前缀表达式，每遇到两个操作数一个运算符就把运算符放到两个操作数中间，注意有的时候可能会连续遇到三个及以上的操作数，这时就不要管后面的操作数了，你只需要向前找，一直找到运算符然后结合后面的两个操作数组合在一起

如下，其中红色部分表示待处理的运算符和操作数

对于后缀转中缀，和前缀转中缀实则是一样的，只不过后缀转中缀的时候需要从前向后扫描，由于也比较简单这里就不演示了

二：用栈实现表达式转换

表达式转换是栈的应用的一个非常典型的例子，主要利用的就是栈的先进后出的特性，代码的逻辑不复杂，但是就是比较多一点

这里用栈实现表达式转换主要指的是中缀转前缀或者后缀，后其他形式的表达式的转换没有具体的意义，因为转为前缀和后缀的目的就是让计算机进行求值，所以这里主要讲的就是中缀转换为前缀或后缀的代码。由于C语言中处理栈比较麻烦，所以这里采用C++，省去一些造轮子的步骤

（1）中缀转后缀

中缀式转后缀式需要两个栈完成，然后从后向前扫描中缀表达式，先不讨论怎样入栈，记住：所有的操作数入S1栈，所有的括号和运算符入S2栈

如下，首先由于S2空，此时扫描到了左括号，遇到左括号直接入栈

接着此时扫描到了操作数a，直接入S1，所有操作数直接入S1

接着此时扫描到了“+”号，此时S2栈顶元素为左括号，任何运算符遇到左括号直接入栈

继续进行，扫描到b直接入S1。然后此时扫描到了右括号，当扫描到右括号时将S2中从栈顶元素到左括号之间的元素依次出S2，入S1，但是左括号忽略掉，也就是不要了

接着扫描到“*”，入S2，然后扫描到操作数“c”，入S1。此时扫描到“+”，由于扫描到的元素符优先级小于等于S2栈顶运算符优先级，故将栈顶运算符出栈入S1，然后接着再拿扫描到的运算符与新的栈顶元素比较，如果还是小于等于重复上述步骤，如果是大于则直接入栈，这里由于“*”出栈后，S2为空，故直接入“+”

接着再入操作数d。此时来到运算符-，由于扫描到的运算符的优先级小于等于栈顶元素优先级，故重复

剩余部分就不再演示了，此时大家观看S1栈，是不是已经有了后缀式的雏形了呢

代码如下

#include <iostream>#include <stack>#include <string>using namespace std;int getpriority(char c){if (c == '+' || c == '-'){return -1;//加减优先级小}else{return 1;//乘除优先级大}}void convert(string& express, stack<char>& s1, stack<char>& s2){int i = 0;while (express[i] != '\0')//扫描中缀表达式{if ('0' <= express[i] && express[i] >= '9')//如果扫描到了操作数，直接入s1{s1.push(express[i++]);}else if (express[i] == '(')//如果扫描到了左括号，直接入s2{s2.push(express[i++]);}else if (express[i] == '+' || express[i] == '-' || express[i] == '*' || express[i] == '/')//扫描到运算符进行优先级判断{if (s2.empty() || s2.top() == '(' || getpriority(express[i]) > getpriority(s2.top()))//如果此时S2为空或者栈顶元素为左括号，或者扫描到的运算符优先级大于栈顶运算符优先级，则S2{s2.push(express[i++]);}else//反之优先级如果是小于等于的话，那么就要把运算符出栈然后入S1{char temp = s2.top();s2.pop();s1.push(temp);}}else if (express[i] == ')')//最后一种情况就是扫描到了右括号，那么就把S2从栈顶到左括号的元素依次出栈入栈{while (s2.top() != '('){char temp = s2.top();s2.pop();s1.push(temp);}//注意最后停止循环的时候S2的栈顶元素是左括号，但是不要把左括号入栈，所以直接丢掉左括号s2.pop();i++;//不要忘记后移}}while (!(s2.empty()))//如果S2没有空，那么依次出S2，入S1{char temp = s2.top();s2.pop();s1.push(temp);}}int main(){stack<char> s1;//结果栈，入操作数stack<char> s2;//辅助栈，入运算符和括号stack<char> result;//输出用string expression("(a+b)*c+d-(e+g)*h");cout << "转换前为中缀式：" << expression << endl;convert(expression, s1, s2);cout << "转换为中缀式：";while (!(s1.empty())){char temp = s1.top();s1.pop();result.push(temp);}while (!(result.empty())){cout << result.top();result.pop();}}

（2）中缀转前缀

中缀转前缀基本和中缀转后缀一致，不同点如下

扫描时从后向前扫描中缀式遇到右括号直接入栈，遇到左括号进行出栈扫描到的运算符优先级如果大于等于栈顶运算符优先级，直接入栈

void convert2(string& express, stack<char>& s1, stack<char>& s2)//中缀转前缀{int i = express.size()-1;while (i>=0)//扫描中缀表达式{if ('a' <= express[i] && express[i] <= 'z')//如果扫描到了操作数，直接入s1{s1.push(express[i--]);}else if (express[i] == ')')//如果扫描到了右括号，直接入s2{s2.push(express[i--]);}else if (express[i] == '+' || express[i] == '-' || express[i] == '*' || express[i] == '/')//扫描到运算符进行优先级判断{if (s2.empty() || s2.top() == ')' || getpriority(express[i]) >= getpriority(s2.top()))//如果此时S2为空或者栈顶元素为左括号，或者扫描到的运算符优先级大于等于栈顶运算符优先级，则入S2{s2.push(express[i--]);}else//反之优先级如果是大于等于的话，那么就要把运算符出栈然后入S1{char temp = s2.top();s2.pop();s1.push(temp);}}else if (express[i] == '(')//最后一种情况就是扫描到了左括号，那么就把S2从栈顶到右括号的元素依次出栈入栈{while (s2.top() != ')'){char temp = s2.top();s2.pop();s1.push(temp);}//注意最后停止循环的时候S2的栈顶元素是右括号，但是不要把右括号入栈，所以直接丢掉右括号s2.pop();i--;//不要忘记后移}}while (!(s2.empty()))//如果S2没有空，那么依次出S2，入S1{char temp = s2.top();s2.pop();s1.push(temp);}}

表达式计算问题（使用栈实现）

我们转换表达式的目的就在于让计算机实现表达式的求值，或者说，计算机是不认识也不清楚中缀式的含义的，只有人能读懂，但是我们转换为前缀或者后缀后却可以借助栈的性质来完成计算

这里我们就以LeetCode 150：逆波兰式求值，也就是后缀表达式求值为例，前缀式基本一致

求解时，准备一个栈，从左向右扫描后缀表达式，遇到操作数就入栈，遇到运算符则出栈两个操作数，先出栈的作为右操作数，后出栈的作为左操作数，然后运算之后把结果继续压入栈内，重复以上步骤，最后栈中的栈顶元素就是结果

class Solution {public:void calculate(int& opnd1,string& op,int& opnd2,int& result)//计算{if(op=="+")result=opnd1+opnd2;if(op=="-")result=opnd1-opnd2;if(op=="*")result=opnd1*opnd2;if(op=="/")result=opnd1/opnd2;}int evalRPN(vector<string>& tokens) {stack<int> ret;//结果栈for(int i=0;i<tokens.size();i++){if(tokens[i].size()==1 && (tokens[i] =="+" || tokens[i] =="-" || tokens[i] =="*" || tokens[i] =="/" ))//运算符{int opnd1,opnd2,result;//两个操作数和结果string op;//运算符op=tokens[i];//运算符opnd2=ret.top();ret.pop();//先出来的是右操作数opnd1=ret.top();ret.pop();//后出来的是左操作数calculate(opnd1,op,opnd2,result);ret.push(result);//计算结果仍然压入栈}else//操作数{int temp=atoi(tokens[i].c_str());ret.push(temp);}}return ret.top();//栈顶元素是结果}};

前缀表达式和这个基本一致，不同点就是要从后向前扫描，然后先出栈的是左操作数，后出栈的是右操作数

使用栈解决的一类经典问题：表达式转换及求值；中缀表达式；前缀表达式 后缀表达式 中缀转前缀；中缀转后缀；后缀表达式求值；波兰式 逆波兰式