比赛 |
20100914 |
评测结果 |
C |
题目名称 |
表达式转换 |
最终得分 |
0 |
用户昵称 |
苏轼 |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2010-09-14 22:13:50 |
显示代码纯文本
#include <cstdio>
#include <cmath>
#include <iostream>
#include <string>
#include <stack>
#include <list>
using namespace std;
const char ope[7]={'+','-','*','/','^','(',')'};
const int youx[]={1,1,2,2,3,0,0};
struct Node
{
int tre;
bool ty;
Node(int a,bool b):tre(a),ty(b){}
};
string str;
string re;
stack<int> s1,s2;//s1 num s2 operator
int len;
bool first;
list<Node> tre;
void deal()
{
int t1=s1.top();s1.pop();
int t2=s1.top();s1.pop();
int opt=s2.top();s2.pop();
if (first)cerr<<"wrong\n";
re+=' ';
re+=ope[opt];
tre.push_back(Node(opt,true));
switch (opt)
{
case 0:s1.push(t1+t2);break;
case 1:s1.push(t1-t2);break;
case 2:s1.push(t1*t2);break;
case 3:s1.push(t1/t2);break;
case 4:s1.push(pow(t1,t2));break;
default : cerr<<"wrong\n";
}
}
void getstr(int num,string &nstr)
{
do
{
nstr+=num%10;
num/=10;
}while(num);
}
list<Node>::iterator it,it2;
void outbelong()
{
it=tre.begin();
if(it->ty)cerr<<"wrong\n";
cout<<it->tre;
for(it++;it!=tre.end();it++)
if (it->ty)cout<<' '<<ope[it->tre];
else cout<<' '<<it->tre;
cout<<'\n';
}
void out()
{
cout<<re<<endl;
// outbelong();
while(tre.size()!=1)
{
for(it=tre.begin();it!=tre.end();it++)
if (it->ty)
{
int opt=it->tre;
it2=it;
it2--;
tre.erase(it);
int t2=it2->tre;
it=it2;
it--;
tre.erase(it2);
int t1=it->tre;
it2=it;
it2--;
tre.erase(it);
it2++;
switch (opt)
{
case 0:tre.insert(it2,Node(t1+t2,false));break;
case 1:tre.insert(it2,Node(t1-t2,false));break;
case 2:tre.insert(it2,Node(t1*t2,false));break;
case 3:tre.insert(it2,Node(t1/t2,false));break;
case 4:tre.insert(it2,Node(pow(t1,t2),false));break;
default:cerr<<"wrong\n";
}
break;
}
outbelong();
}
}
void solve()
{
len=str.length();
first=true;
for(int i=0;i<len;i++)
{
if (str[i]=='(')
{
s2.push(5);
continue;
}
else if (str[i]==')')
{
while(s2.top()!=5)deal();
s2.pop();
continue;
}
if (str[i]>='0'&&str[i]<='9')
{
if (!first)re+=' ';
else first=false;
re+=str[i];
tre.push_back(Node(str[i]-'0',false));
s1.push(str[i]-'0');
}
else
{
char opc=str[i];
int op;
switch (opc)
{
case '+':op=0;break;
case '-':op=1;break;
case '*':op=2;break;
case '/':op=3;break;
case '^':op=4;break;
default : cerr<<"wrong\n";
}
while (!s2.empty()&&youx[op]<=youx[s2.top()])
deal();
s2.push(op);
}
}
}
int main()
{
freopen("express.in","r",stdin);
freopen("express.out","w",stdout);
getline(cin,str);
str='('+str+')';
solve();
out();
return 0;
}