比赛 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;
}