中缀式变后缀式
时间限制：1000 ms | 内存限制：65535 KB
难度：3
- 描述
- 人们的日常习惯是把算术表达式写成中缀式，但对于机器来说更“习惯于”后缀式，关于算术表达式的中缀式和后缀式的论述一般的数据结构书都有相关内容可供参看，这里不再赘述，现在你的任务是将中缀式变为后缀式。
- 输入
- 第一行输入一个整数n，共有n组测试数据（n<10)。
每组测试数据只有一行，是一个长度不超过1000的字符串，表示这个运算式的中缀式，每个运算式都是以“=”结束。这个表达式里只包含+-*/与小括号这几种符号。其中小括号可以嵌套使用。数据保证输入的操作数中不会出现负数。
数据保证除数不会为0 - 输出
- 每组都输出该组中缀式相应的后缀式，要求相邻的操作数操作符用空格隔开。
- 样例输入
-
2 1.000+2/4= ((1+2)*5+1)/4=
- 样例输出
-
1.000 2 4 / + = 1 2 + 5 * 1 + 4 / =
伪算法： 先定义两个栈，一个为运算符栈S1，一个为后缀表达式S2，输入字符串，对字符依次处理。 a.若为'('入栈 b.若为')'，依次把栈中的运算符加入后缀表达式栈中，直至出现'('，删除'('。 c.若为除括号外的其它运算符，当其优先级高于除'('以外的栈顶运算符，入栈。 否则，从栈顶开始，依次弹出以前运算符优先级高和优先级相等的运算符。直到遇到优先级更低的或者'('。 注：运算符进入运算符栈，运算数均进入后缀表达式栈，运算符也进入一部分。伪算法最好在纸上模拟模拟。/*题解：
写了半天，总算A了，precede()是求优先关系的。参照《数据结构严蔚敏版》p53的优先关系表。
虽然参照伪算法写出程序，但是刚开始不知道如何处理小数，后来发现每次处理完小数后，在其后面加一个空格即可（进入S2的都加“ ”）。
*/#include<cstdio> #include<iostream> #include<cstring> #include<stack> using namespace std; char precede(char c1,char c2){ //判断优先关系 if(c1=='+'||c1=='-') { if(c2=='+'||c2=='-'||c2==')'||c2=='=') return '>'; else if(c2=='*'||c2=='/'||c2=='(') return '<'; } if(c1=='*'||c1=='/') { if(c2=='(') return '<'; else return '>'; } if(c1==')') { if(c2!='(') return '>'; } if(c1=='(') { if(c2==')') return '='; else if(c2!='='&&c2!=')')return '<'; } if(c1=='=') { if(c2=='=') return '='; else if(c2!='='&&c2!=')') return '<'; } } int main() { int n,i,k,len; string a; char b[1010]; cin>>n; while(n--) { stack<char>S1; stack<char>S2; cin>>a; len = a.length(); S1.push('='); for(i=0; i<len-1; ) { if(a[i]=='(') { S1.push(a[i]); i++; continue; } if(a[i]>='0'&&a[i]<='9'||a[i]=='.') { while(a[i]>='0'&&a[i]<='9'||a[i]=='.'){ S2.push(a[i]); i++; continue; } S2.push(' ') ; } else if(a[i]==')') { while(S1.top()!='(') { S2.push(S1.top()); S2.push(' '); S1.pop(); } S1.pop(); i++; continue; } else { if( (precede(S1.top(),a[i])=='<'&&S1.top()!='(')||S1.top()=='(' ){ S1.push(a[i]); i++; continue; } else { while(1) { S2.push(S1.top()); S2.push(' '); S1.pop(); if(S1.top()=='('||precede(S1.top(),a[i])=='<') break; } } } } k=0; while(S2.empty()==0) { b[k++]=S2.top(); S2.pop(); } for(i=k-1; i>=0; i--) cout<<b[i]; while(S1.top()!='=') { cout<<S1.top()<<" "; S1.pop(); } cout<<'='<<endl; } }