本篇是栈篇的最后一篇，记录一下如何用栈实现中缀表达式转后缀表达式。
先举例一个后缀表达式9 3 1 – 2 * + 5 2 / + 他的中缀表达式是9+(3-1)*2+5/2
首先我们要找到这个表达式的优先级优先级最高的是括号 其次是乘法和除法再然后是加法 那么如何用栈来演示呢。
之前那个表达式很长难以理解，我们用A+(B*C)很明显B*\C的优先级高，所以把*置后 然后 A的操作数就变成了BC*
我们可以发现不管符号怎么后置，表达式的操作数的顺序都是不变的ABC 所以我们可以用一个字符串存放这些操作数，至于操作符我们发现只有找到他的右操作数时，表达式才会成立，也就可以置后操作符了。
如图，我们把操作数按次序放在了列表里，同时根据是否找到操作符的右操作数进行压栈操作，如果当前符号的优先级大于栈顶的符号，说明还没有找到这个优先级较大符号的有右操作数，如果当前符号小于栈顶的符号，说明已经找到了上一个符号的右操作数 比如A+B*C我们先不讨论括号+号已经入栈了，但是B后面是一个比+号优先级大的符号，难道我们要先算A+B吗 所以我们继续压栈，等到C之后没有符号了，说明C就是*的右操作数，分别pop *和+，再比如A*B+C，先入栈*，然后到下一个操作符判断和栈顶的优先级，很明显+号小于栈顶的*号，所以我们已经找到了最右操作数B，然后就可以在操作数列表里加入操作符了(后置),直接把栈顶的元素pop到字符串列表里，然后再把当前的操作符push到栈中，等待遍历其的右操作数。
我们直接用代码来说明，看看如何用代码实现。
#include<iostream>
#include<string>
#include<stack>
//不能友好显示十进制
//括号
using namespace std;
void infixtopostfix(string s);
bool Isnumber(char fix);
bool IsOperator(char c);
bool Hashigherpre(char top,char str);
int GetOperatorWeight(char op);
bool Isopening(char top);
int main()
{
string line;
printf("please input infix\n");
getline(cin, line);
infixtopostfix(line);
return 0;
}
void infixtopostfix(string str)
{
string fix;
stack<char> S;
int num = 0;
for (size_t i = 0; i < str.length(); i++)
{
if (Isnumber(str[i]))
{
fix.push_back(str[i]);
}
else if (str[i]=='(')
{
S.push(str[i]);
}
else if (IsOperator(str[i]))
{
while (!S.empty()&& Hashigherpre(S.top(),str[i])&&!Isopening(S.top()))
{
fix += S.top();
S.pop();
}
S.push(str[i]);
}
else if (str[i] == ')')
{
while (!S.empty()&& !Isopening(S.top()))
{
fix += S.top();
S.pop();
}
S.pop();
}
}
while (!S.empty())//表达式结束，操作符按顺序出栈
{
fix += S.top();
S.pop();
}
cout << fix;
}
bool Isnumber(char fix)
{
if (fix>='0' && fix <= '9')
{
return true;
}
return false;
}
bool IsOperator(char c)
{
if (c == '+' || c == '-' || c == '*' || c == '/')
{
return true;
}
return false;
}
bool Hashigherpre(char top, char str)
{
int weight01 = GetOperatorWeight(top);
int weight02 = GetOperatorWeight(str);
return weight01 >= weight02 ? true : false;
}
int GetOperatorWeight(char op)
{
int weight = -1;
switch (op)
{
case '+':
case '-':
weight = 1;
break;
case '*':
case '/':
weight = 2;
break;
case '$':
weight = 3;
break;
}
return weight;
}
bool Isopening(char top)
{
if (top == '(')
{
return true;
}
return false;
}
首先我们输入了中缀表达式之后，我们会用 string fix;存放我们新的后缀表达式，接着根据传入表达式的长度进入循环，如果是数字的话就加到字符串后面，如果是操作符的话，首先要看栈顶元素，如果栈不为空，而且当前操作符大于栈顶元素符号满足的话，就要push当前符号，如果不满足，就要把栈顶元素出栈，通过fix += S.top();S.pop();直到栈顶元素小于当前元素，执行push当前操作符，循环执行完成之后，如果栈内依然有元素的话，则需要把栈内元素都pop到表达式fix后面，这里再说一下括号，，毫无疑问，括号肯定是优先级最高的，所以我们遇到开放符号，先放入栈，然后等待右括号，如果等到右括号，说明已经找到右操作数了这时候就将括号里面的操作符按顺序出栈
看图
网站标题：CV鼻祖洋芋
原创文章，作者：locus，如若转载，请注明出处：https://blog.cvpotato.cn/forward-code/c-2/165/
本博客所发布的内容，部分为原创文章，转载注明来源，网络转载文章如有侵权请联系站长！
