外贸SOHO建公司网站,东莞建站响应式网站多少钱,迁安建设局官方网站,赣州网站制作找哪家好题目描述
中缀表达式是一个通用的算术或逻辑公式表示方法#xff0c;操作符是以中缀形式处于操作数的中间#xff08;例#xff1a;3 4#xff09;#xff0c;中缀表达式是人们常用的算术表示方法。后缀表达式不包含括号#xff0c;运算符放在两个运算对象的后面#…题目描述
中缀表达式是一个通用的算术或逻辑公式表示方法操作符是以中缀形式处于操作数的中间例3 4中缀表达式是人们常用的算术表示方法。后缀表达式不包含括号运算符放在两个运算对象的后面所有的计算按运算符出现的顺序严格从左向右进行不再考虑运算符的优先规则如(2 1) * 3 即2 1 3 *。利用栈结构将中缀表达式转换为后缀表达式。(测试数据元素为单个字符)
输入
中缀表达式
输出
后缀表达式
样例输入复制
A(B-C/D)*E
样例输出复制
ABCD/-E* 这个题我看到解法当中有通过编译原理当中的文法表达式来处理的也有用堆栈模拟的。
我的方案是用递归。
重点是要把表达式按优先级进行切割。我是这么想的对于表达式AB*C-(D*F*(FBC*D)-(A*H))*T先按优先级最低的、-号进行切分但是主要切分时要把括号内的表达式当成整体于是可以切割成AB*C(D*F*(FBC*D)-(A*H))*T三个子表达式【如果、-号无法切割就扫描*、/能不能切割还是不能就说明要么这个表达式只有一个原子要么就是整个表达式都用括号包起来了。】这里我们可以继续递归切割A已经是原子无需切割。第二个表达式可以继续切割成B和C这样每次切割我们可以得到两个列表一个用来装切割的表达式一个用来装两个表达式之间的符号。最后假设我们的处理函数为f那么对于这个例子实际上我要求f(AB*C-(D*F*(FBC*D)-(A*H))*T)根据刚才的分析显然他可以通过递归化简为f((D*F*(FBC*D)-(A*H))*T)f(A)f(B*C)-这样不断的递归f当中的表达式最后合并答案就是我们需要的逆波兰表达式可以观看代码#define _CRT_SECURE_NO_WARNINGS
#includestdio.h
#includestring.h
#includemath.h
#includealgorithm
#includevector
#includestring
#includemap
#includequeue
#includeiostream
#includelist
#includeset
#includestackusing namespace std;bool expr_cut(string root_expr,vectorstring expr_list,vectorchar op_list)
{stackint s;int lenroot_expr.size();if(len1)return true;string expr_now;bool first_flagfalse,second_flagfalse;for(int i0;ilen;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_flagtrue;continue;}else if(root_expr[i](){s.push(i);}else if(root_expr[i])){s.pop();}expr_nowexpr_nowroot_expr[i];}expr_list.push_back(expr_now);if(first_flag)return false;expr_list.clear(),op_list.clear(),expr_now.clear();for(int i0;ilen;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_flagtrue;continue;}else if(root_expr[i](){s.push(i);}else if(root_expr[i])){s.pop();}expr_nowexpr_nowroot_expr[i];}expr_list.push_back(expr_now);if(second_flag)return false;expr_list.clear(),op_list.clear(),expr_now.clear();root_exprroot_expr.substr(1,root_expr.size()-2);return expr_cut(root_expr,expr_list,op_list);
}string f(string root_expr)
{vectorstring expr_list;vectorchar op_list;bool is_atomexpr_cut(root_expr,expr_list,op_list);if(is_atom)return root_expr;else{string result;string first_itemf(expr_list[0]);for(int i1;iexpr_list.size();i){string second_itemf(expr_list[i]);resultfirst_itemsecond_itemresultop_list[i-1];first_itemsecond_item;}return result;}
}int main()
{string expr;while(cinexpr){string resultf(expr);coutresult;}return 0;
}/*
AB*C-(D*F*(FBC*D)-(A*H))*T
(AB*C)
*/
