SWUST OJ 1042: 中缀表达式转换为后缀表达式【表达式转逆波兰表达式】

题目描述

中缀表达式是一个通用的算术或逻辑公式表示方法，操作符是以中缀形式处于操作数的中间（例：3 + 4），中缀表达式是人们常用的算术表示方法。后缀表达式不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则，如：(2 + 1) * 3 ， 即2 1 + 3 *。利用栈结构，将中缀表达式转换为后缀表达式。(测试数据元素为单个字符)

输入

中缀表达式

输出

后缀表达式

样例输入复制

A+(B-C/D)*E

样例输出复制

ABCD/-E*+

这个题我看到解法当中有通过编译原理当中的文法表达式来处理的，也有用堆栈模拟的。

我的方案是用递归。

重点是要把表达式按优先级进行切割。

我是这么想的：

对于表达式：A+B*C-(D*F*(F+B+C*D)-(A*H))*T

先按优先级最低的+、-号进行切分，但是主要切分时要把括号内的表达式当成整体，于是可以切割成：

A

B*C

(D*F*(F+B+C*D)-(A*H))*T

三个子表达式

【如果+、-号无法切割，就扫描*、/能不能切割，还是不能就说明要么这个表达式只有一个原子，要么就是整个表达式都用括号包起来了。】

这里我们可以继续递归切割，A已经是原子，无需切割。第二个表达式可以继续切割成B和C

这样，每次切割，我们可以得到两个列表，一个用来装切割的表达式，一个用来装两个表达式之间的符号。

最后，假设我们的处理函数为f

那么对于这个例子，实际上我要求：f(A+B*C-(D*F*(F+B+C*D)-(A*H))*T)

根据刚才的分析，显然他可以通过递归化简为：f((D*F*(F+B+C*D)-(A*H))*T)f(A)f(B*C)+-

这样不断的递归f当中的表达式，最后合并答案就是我们需要的逆波兰表达式！

可以观看代码：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<string>
#include<map>
#include<queue>
#include<iostream>
#include<list>
#include<set>
#include<stack>using namespace std;bool expr_cut(string root_expr,vector<string>& expr_list,vector<char>& op_list)
{stack<int> s;int len=root_expr.size();if(len==1)return true;string expr_now;bool first_flag=false,second_flag=false;for(int i=0;i<len;++i){if((root_expr[i]=='+' || root_expr[i]=='-') && s.empty()){expr_list.push_back(expr_now);op_list.push_back(root_expr[i]);expr_now.clear();first_flag=true;continue;}else if(root_expr[i]=='('){s.push(i);}else if(root_expr[i]==')'){s.pop();}expr_now=expr_now+root_expr[i];}expr_list.push_back(expr_now);if(first_flag)return false;expr_list.clear(),op_list.clear(),expr_now.clear();for(int i=0;i<len;++i){if((root_expr[i]=='*' || root_expr[i]=='/') && s.empty()){expr_list.push_back(expr_now);op_list.push_back(root_expr[i]);expr_now.clear();second_flag=true;continue;}else if(root_expr[i]=='('){s.push(i);}else if(root_expr[i]==')'){s.pop();}expr_now=expr_now+root_expr[i];}expr_list.push_back(expr_now);if(second_flag)return false;expr_list.clear(),op_list.clear(),expr_now.clear();root_expr=root_expr.substr(1,root_expr.size()-2);return expr_cut(root_expr,expr_list,op_list);
}string f(string root_expr)
{vector<string> expr_list;vector<char> op_list;bool is_atom=expr_cut(root_expr,expr_list,op_list);if(is_atom)return root_expr;else{string result="";string first_item=f(expr_list[0]);for(int i=1;i<expr_list.size();i++){string second_item=f(expr_list[i]);result=first_item+second_item+result+op_list[i-1];first_item=second_item;}return result;}
}int main()
{string expr;while(cin>>expr){string result=f(expr);cout<<result;}return 0;
}/*
A+B*C-(D*F*(F+B+C*D)-(A*H))*T
(A+B*C)
*/