表达式的转换(0088)
Time limit(ms): 5000
Memory limit(kb): 65535
Submission: 435
Accepted: 93
Accepted
16级卓越班选拔D 14级卓越班选拔D 15级卓越班选拔D
平常我们书写的表达式称为中缀表达式，因为它将运算符放在两个操作数中间，许多情况下为了确定运算顺序，括号是不可少的，而后缀表达式就不必用括号了。后缀标记法：书写表达式时采用运算紧跟在两个操作数之后，从而实现了无括号处理和优先级处理，使计算机的处理规则简化为：从左到右顺序完成计算，并用结果取而代之。例如：8-(3+2*6)/5+4可以写为：8 3 2 6*+5/-4+ 其计算步骤为：
(1):8 3 2 6 * + 5 / -4 +
(2):8 3 12 + 5 / - 4 +
(3):8 15 5 / - 4 +
(4):8 3- 4 +
(5):5 4 +
(6):9
编写一个程序，完成这个转换，要求输出的每一个数据间都留一个空格。
Description
就一行，是一个中缀表达式。输入的符号中只有这些基本符号“0123456789+-*/^()”，并且不会出现形如2*-3的格式。表达式中的基本数字也都是一位的，不会出现形如12形式的数字。所输入的字符串不要判错。
Input
若干个中缀表达式，第I+1行比第I行少一个运算符和一个操作数，最后一行只有一个数字，表示运算结果。运算的结果可能为负数，“/”以整除运算。并且中间每一步都不会超过2^31。
Output
|
1
|
8-(3+2*6)/5+4
|
Sample Input
|
1
2
3
4
5
6
|
8 3 2 6 * + 5 / - 4 +
8 3 12 + 5 / - 4 +
8 15 5 / - 4 +
8 3 - 4 +
5 4 +
9
|
Sample Output
温馨提示：优先级'^' > '*' = '/' > '+' = ‘-’
分析：（这道题需要中缀转后缀的基础） 有空我再写个中缀转后缀的 详解
这个题变态就变态在 每一步都要输出
所以转换为后缀表达式后还要一步一步处理
由于后缀表达式中既有数字也有字符 所以我采取的方法是 将字符转换为较大的数字 方便处理；
然后就是 后缀表达式的计算 输出 和 更新了。
还是直接贴代码吧；
#include<iostream> #include<stack> #include<cmath> #define INT_MAX 2147483647 using namespace std; int k,data[100]; string str; int get_priority(const char& x)//获取优先级 { switch(x) { case '+': case '-': return 1;break; case '*': case '/': return 2;break; case '^': return 3;break; case '(': return 4;break; case ')': return 0;break; default: return -1; } } int convert(const char& x)//将字符转换为较大的整数 { switch(x) { case '+':return INT_MAX-1; break; case '-':return INT_MAX-2; break; case '*':return INT_MAX-3; break; case '/':return INT_MAX-4; break; case '^':return INT_MAX-5; break; } } void Cout()//输出处理 要将整数对应的字符转换过来 { for(int i=0;i<k;i++) { switch(data[i]) { case INT_MAX-1: cout<<'+'; break; case INT_MAX-2: cout<<'-'; break; case INT_MAX-3: cout<<'*'; break; case INT_MAX-4: cout<<'/'; break; case INT_MAX-5: cout<<'^'; break; default: cout<<data[i]; } if(i!=k-1)cout<<" "; } } int judge(const int& x) //判断这个较大的数表示的是那个字符 { switch(x) { case INT_MAX-1: return 1; break; case INT_MAX-2: return 2; break; case INT_MAX-3: return 3; break; case INT_MAX-4: return 4; break; case INT_MAX-5: return 5; break; default: return 0; } } void step()//按步计算 { for(int i=0;i<k;i++) { if(judge(data[i])!=0) { switch(judge(data[i])) { case 1:data[i-2]=data[i-2]+data[i-1]; data[i]=data[i-1]=INT_MAX; break; case 2:data[i-2]=data[i-2]-data[i-1]; data[i]=data[i-1]=INT_MAX; break; case 3:data[i-2]=data[i-2]*data[i-1]; data[i]=data[i-1]=INT_MAX; break; case 4:data[i-2]=data[i-2]/data[i-1]; data[i]=data[i-1]=INT_MAX; break; case 5:data[i-2]=pow(data[i-2],data[i-1]); data[i]=data[i-1]=INT_MAX; break; } break; } } int t=0; for(int i=0;i<k;i++)//更新 { if(data[i]!=INT_MAX) data[t++]=data[i]; } k=t; } int main() { while(cin>>str) { k=0; stack<char>q; for(int i=0;i<str.size();i++) { if(get_priority(str[i])==-1) {data[k++]=str[i]-'0'; continue;} if(q.empty()) q.push(str[i]); else if(str[i]==')') { while(q.top()!='(') { data[k++]=convert(q.top()); q.pop(); } q.pop(); } else{ while(get_priority(q.top())>=get_priority(str[i])&&q.top()!='('&&!q.empty()) { data[k++]=convert(q.top()); q.pop(); if(q.empty()) break; } q.push(str[i]); } } while(!q.empty()) { data[k++]=convert(q.top()); q.pop(); } //前面的都是中缀表达式转后缀表达式的内容； Cout(); cout<<endl; while(k>1) { step(); Cout(); cout<<endl; } } return 0; }