思路分析
- 遇到数字,直接输出
- 遇到符号
- 栈为空,符号直接入栈
- 若为 ( ,则直接入栈
- 用当前符号和栈顶符号比较优先级
- 当前符号 > 栈顶符号,当前符号直接入栈,结束
- 当前符号 <= 栈顶符号,栈顶符号出栈并输出,继续比较
- 把栈中符号弹空
- 遇到 ) ,要一直出栈,直到遇见 ) 为止
例子1:
中缀表达式:(1 + 2) * (3 + 4)
后缀表达式:12 + 34 + *
符号入栈情况图(从上到下,从左往右看):
例子2:
中缀表达式:2 + (4 + 6)/2 + 6 / 3
后缀表达式:2 4 6 + 2 / + 6 3
代码
// 中缀转后缀表达式
// 2024年03月31日10:57:06
#include <iostream>
#include <string>
#include <stack>
using namespace std;
bool Priority(char ch, char topch)
{
// ch优先级大的情况:
if((ch == '*' || ch == '/') && (topch == '+' || topch == '-')) return true;
// 栈顶的 ( 优先级小于任何其他符号(除了 ))
if(topch == '(' && ch != ')') return true;
return false;
}
string MiddleToPostExpr(string expr)
{
string res;
stack<char> s;
for(char ch : expr)
{
if(ch >= '0' && ch <= '9')
{
res.push_back(ch);
}
else
{
for(;;) // 用于处理可能得多次出栈(遇到 ), 或优先级不同)
{
// 栈空 或 遇到 ( ,直接入栈
if(s.empty() || ch == '(')
{
s.push(ch);
break;
}
// 比较当前符号ch和栈顶符号top
char topch = s.top();
// true if ch > topch
if(Priority(ch, topch)) // 当面符号优先级大于栈顶符号,入栈
{
s.push(ch);
break;
}
else /// 不断出栈的情况
{
s.pop();
if(topch == '(') // 遇见 ),一直出栈直到 (
break;
res.push_back(topch);
}
}
}
}
while(!s.empty()) // 栈还留存符号,直接输出到后缀表达式中
{
res.push_back(s.top());
s.pop();
}
return res;
}
int main()
{
cout << MiddleToPostExpr("(1+2)*(3+4)") << endl;
// cout << MiddleToPostExpr("2+(4+6)/2+6/3") << endl;
return 0;
}
执行结果
[root@centos01 stack]# g++ mid_to_post.cpp
[root@centos01 stack]# ./a.out
12+34+*