2264 - 表达式的转换
时间限制 : 1 秒
内存限制 : 128 MB
平常我们书写的表达式称为中缀表达式，因为它将运算符放在两个操作数中间，许多情况下为了确定运算顺序，括号是不可少的，而中缀表达式就不必用括号了。
后缀标记法：书写表达式时采用运算紧跟在两个操作数之后，从而实现了无括号处理和优先级处理，使计算机的处理规则简化为：从左到右顺序完成计算，并用结果取而代之。
例如：8-(3+2*6)/5+4可以写为：8 3 2 6*+5/–4+
其计算步骤为：
8 3 2 6 * + 5 / - 4 +
8 3 12 + 5 / - 4 +
8 15 5 / - 4 +
8 3 - 4 +
5 4 +
9
编写一个程序，完成这个转换，要求输出的每一个数据间都留一个空格。
题目输入
就一行，是一个后缀表达式。输入的符号中只有这些基本符号“0123456789+-*/^()”，并且不会出现形如2*-3的格式。
表达式中的基本数字也都是一位的，不会出现形如12形式的数字。
所输入的字符串不要判错。
题目输出
若干个中缀表达式，第I+1行比第I行少一个运算符和一个操作数，数据项之间用空格分隔，最后一行只有一个数字，表示运算结果。
运算的结果可能为负数，“/”以整除运算。并且中间每一步绝对值都小于2^31。
输入/输出样例
输入格式
8-(3+2*6)/5+4
输出格式
8 3 2 6 * + 5 / - 4 + 8 3 12 + 5 / - 4 + 8 15 5 / - 4 + 8 3 - 4 + 5 4 + 9
C++解答
#include<iostream> #include<string> #include<cctype> #include<stack> using namespace std; struct node{ int data; bool isnum; node *lch,*rch; }; int pri[127]; stack<node *> opd; stack<node *> opr; void create(node *&root,const string &s) //建数据栈 和 符号栈 { int i,len; node *p,*q,*r; for (i=0,len=s.size();i<len;i++) { if (isdigit(s[i])) { //数据 p=new(node); p->data=s[i]-'0'; p->isnum=true; p->lch=p->rch=NULL; opd.push(p); continue; } if (s[i]=='(') { //左括号 p=new(node); p->data=(int)s[i]; p->isnum=false; p->lch=p->rch=NULL; opr.push(p); continue; } if (s[i]==')'){ //右括号，出到左括号与之配对 p=opr.top(); opr.pop(); while (p->data!=(int)'('){ //出到左括号与之配对 q=opd.top(); opd.pop(); p->rch=q; //出数据 q=opd.top(); opd.pop(); p->lch=q; //出数据 opd.push(p); //运算后再入数据栈 p=opr.top(); opr.pop(); } continue; } //以下是其它运算符 p=new(node); p->data=(int)s[i]; p->isnum =false; p->lch=p->rch=NULL; if (opr.empty()) { opr.push(p); continue; } char ch=(char)(opr.top()->data) ; if (ch=='('||pri[s[i]]>pri[ch]) { opr.push(p); continue; } while (ch!='('&&pri[s[i]]<=pri[ch]) { //当前字符优先级低于栈顶字符，注意左括号 r=opr.top(); opr.pop(); q=opd.top(); opd.pop(); r->rch=q; q=opd.top(); opd.pop(); r->lch=q; opd.push(r); if (opr.empty()) break; ch=(char)(opr.top()->data) ; } opr.push(p); } while (!opr.empty()) { p=opr.top(); opr.pop(); q=opd.top(); opd.pop(); p->rch=q; q=opd.top(); opd.pop(); p->lch=q; opd.push(p); } root=opd.top(); } void deal(node *root) { char ch=root->data; switch (ch) { case '+': root->data =root->lch->data + root->rch->data; break; case '-': root->data =root->lch->data - root->rch->data; break; case '*': root->data =root->lch->data * root->rch->data; break; case '/': root->data =root->lch->data / root->rch->data; break; case '^': int t=1; for (int i=0;i<root->rch->data;i++) t*=root->lch->data; root->data =t; break; } root->isnum =true; root->lch = root->rch = NULL; } void lastord(node *root,bool &merged) { if (root) { lastord(root->lch,merged); lastord(root->rch,merged); if (root->isnum) cout<<root->data<<" "; else cout<<(char)root->data<<" " ; if (root->lch&&!merged){ deal(root); merged=true; } } } int main() { pri['+']=1; pri['-']=1; pri['*']=2; pri['/']=2; pri['^']=3; string s; node *root; cin>>s; create(root,s); bool merged; while (root->lch){ merged=false; lastord(root->lch,merged); lastord(root->rch,merged); cout<<(char)root->data<<endl; //左右根，这时根是运算符 if (root->lch&&!merged){ //最后一次运算merged在这里必然为假 deal(root); merged=true; } } cout<<root->data<<endl; return 0; }