题目描述编译器和计算器中常用的三种遍历方法中缀infix\texttt{infix}infix如a b c前缀prefix\texttt{prefix}prefix如 a b c后缀postfix\texttt{postfix}postfix如a b c 前缀和后缀表示法的优点是不需要括号来避免歧义。运算符优先级从高到低^乘方*/乘除-加减|与、或!非输入格式输入包含两行字符串。第一行是中缀表达式第二行是前缀表达式。所有输入字符由空格分隔。输出格式输出后缀表达式同样以空格分隔。样例输入a b - c a - b c样例输出INFIX a b - c PREFIX a - b c POSTFIX a b c - 题目分析问题的本质这是一个表达式树重构问题。给定中缀表达式和前缀表达式需要生成对应的后缀表达式。中缀、前缀、后缀的关系这三种表示法对应二叉树的不同遍历顺序中缀左子树→\to→根→\to→右子树前缀根→\to→左子树→\to→右子树后缀左子树→\to→右子树→\to→根解题方法利用前缀和中缀序列可以唯一地重构表达式树然后进行后序遍历得到后缀表达式。算法步骤前缀序列的第一个字符是树的根在中缀序列中找到该根的位置root中缀序列中根左边的部分是左子树的中缀序列右边的部分是右子树的中缀序列前缀序列中根之后的前root个字符是左子树的前缀序列剩余是右子树的前缀序列递归处理左右子树后序输出先左、后右、再根参考代码// WhatFix Notation// UVa ID: 372// Verdict: Accepted// Submission Date: 2017-02-21// UVa Run Time: 0.000s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;vectorcharsequences;// 存储后缀表达式字符// 根据前缀和中缀序列递归生成后缀序列voidpostfix(string prefix,string infix){if(prefix.length()0)return;// 找到根结点在中缀序列中的位置introot0;for(;rootinfix.length();root)if(infix[root]prefix.front())break;// 递归处理左子树// 左子树的中缀序列infix[0..root-1]// 左子树的前缀序列prefix[1..root]postfix(prefix.substr(1,root),infix.substr(0,root));// 递归处理右子树// 右子树的中缀序列infix[root1..end]// 右子树的前缀序列prefix[root1..end]postfix(prefix.substr(root1),infix.substr(root1));// 后序输出先左、后右、再根sequences.push_back(prefix.front());}intmain(intargc,char*argv[]){string infix,prefix;while(getline(cin,infix),getline(cin,prefix)){coutINFIX infix\n;coutPREFIX prefix\n;// 去除空格for(intiinfix.size()-1;i0;i--)if(isblank(infix[i]))infix.erase(infix.begin()i);for(intiprefix.size()-1;i0;i--)if(isblank(prefix[i]))prefix.erase(prefix.begin()i);sequences.clear();postfix(prefix,infix);coutPOSTFIX ;for(inti0;isequences.size();i)cout sequences[i];cout\n;}return0;}