表达式的转换(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[];
string str;
int get_priority(const char& x)//获取优先级
{
switch(x)
{
case '+':
case '-': return ;break;
case '*':
case '/': return ;break;
case '^': return ;break;
case '(': return ;break;
case ')': return ;break;
default: return -;
}
}
int convert(const char& x)//将字符转换为较大的整数
{
switch(x)
{
case '+':return INT_MAX-; break;
case '-':return INT_MAX-; break;
case '*':return INT_MAX-; break;
case '/':return INT_MAX-; break;
case '^':return INT_MAX-; break;
}
}
void Cout()//输出处理 要将整数对应的字符转换过来
{
for(int i=;i<k;i++)
{
switch(data[i])
{
case INT_MAX-: cout<<'+'; break;
case INT_MAX-: cout<<'-'; break;
case INT_MAX-: cout<<'*'; break;
case INT_MAX-: cout<<'/'; break;
case INT_MAX-: cout<<'^'; break;
default: cout<<data[i];
}
if(i!=k-)cout<<" ";
}
}
int judge(const int& x) //判断这个较大的数表示的是那个字符
{
switch(x)
{
case INT_MAX-: return ; break;
case INT_MAX-: return ; break;
case INT_MAX-: return ; break;
case INT_MAX-: return ; break;
case INT_MAX-: return ; break;
default: return ;
}
}
void step()//按步计算
{
for(int i=;i<k;i++)
{
if(judge(data[i])!=)
{
switch(judge(data[i]))
{
case :data[i-]=data[i-]+data[i-]; data[i]=data[i-]=INT_MAX; break;
case :data[i-]=data[i-]-data[i-]; data[i]=data[i-]=INT_MAX; break;
case :data[i-]=data[i-]*data[i-]; data[i]=data[i-]=INT_MAX; break;
case :data[i-]=data[i-]/data[i-]; data[i]=data[i-]=INT_MAX; break;
case :data[i-]=pow(data[i-],data[i-]); data[i]=data[i-]=INT_MAX; break;
}
break;
}
}
int t=;
for(int i=;i<k;i++)//更新
{
if(data[i]!=INT_MAX)
data[t++]=data[i];
}
k=t;
}
int main()
{
while(cin>>str)
{
k=; stack<char>q;
for(int i=;i<str.size();i++)
{
if(get_priority(str[i])==-)
{data[k++]=str[i]-''; 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>)
{
step();
Cout(); cout<<endl;
}
}
return ;
}