记录编号	42574	评测结果	AAAAAAAAAA
题目名称	表达式转换	最终得分	100
用户昵称	cqw	是否通过	通过
代码语言	C++	运行时间	0.009 s
提交时间	2012-09-26 16:13:53	内存使用	0.31 MiB

//date:201209
//author:cqw
//way:double stack
#include<fstream>
#include<stack>
#include<vector>
#include<cmath>
using namespace std;
ifstream fin("express.in");
ofstream fout("express.out");
class ep
{
public:int x;char ch;
} ept;
vector<ep> ep1;
stack<char> s2;//运算符栈
vector<char> s1;//后缀串栈(只进不出)
string s;//输入串
int fg(char x)//判定运算符等级
{
	if (x=='+'||x=='-') return 1;
	if (x=='*'||x=='/') return 2;
	if (x=='^') return 3;return 0;
}
void print()//输出结果到ep1
{
	for (int i=0;i<s1.size();i++)//输出后缀串栈
	{
		if (s1.at(i)>='0'&&s1.at(i)<='9')
			ept.x=s1.at(i)-48;else ept.x=-1;
		ept.ch=s1.at(i);
		ep1.push_back(ept);
	}
	while (!s2.empty())//输出运算符栈中剩余全部运算符
	{
		if (s2.top()>='0'&&s2.top()<='9')
			ept.x=s2.top()-48;else ept.x=-1;
		ept.ch=s2.top();
		ep1.push_back(ept);
		s2.pop();
	}
}
void right()
{
	while (s2.top()!='(')//括号内运算符处理
	{
		s1.push_back(s2.top());
		s2.pop();
	}s2.pop();//左括号出栈
}
void op(char x)
{
	while (!s2.empty()&&fg(s2.top())>=fg(x))//级别高的运算符先处理
	{
	   s1.push_back(s2.top());
	   s2.pop();
	}s2.push(x);//运算符入栈
}
bool isch(char x)
{
	if (x=='+'||x=='-'||x=='*'||x=='/'||x=='^') return 1;else return 0;
}
void pp()
{
	for (int i=0;i<ep1.size();i++)
	{
		if (ep1.at(i).x==-1) fout<<ep1.at(i).ch;else fout<<ep1.at(i).x;
		if (i==ep1.size()-1) fout<<endl;else fout<<' ';
	}
}
void zprint()
{
	int i,a,b;pp();
	while (ep1.size()>1)//计算完时只有一项：结果
	{
		i=0;while (ep1.at(i).x!=-1) i++;
		a=ep1.at(i-1).x;b=ep1.at(i-2).x;
		switch (ep1.at(i).ch)//根据运算符计算
	   {
	       case '+':ep1.at(i-2).x=b+a;break;
		   case '-':ep1.at(i-2).x=b-a;break;
		   case '*':ep1.at(i-2).x=b*a;break;
		   case '/':ep1.at(i-2).x=b/a;break;
		   case '^':ep1.at(i-2).x=(int)pow(double(b),double(a));break;
	      default:ep1.at(i-2).x=-1;//正确运行不会执行此句
	   }ep1.erase(ep1.begin()+i);ep1.erase(ep1.begin()+i-1);
	   pp();
	}
}
int main()
{
	fin>>s;
	for (int i=0;i<s.length();i++)
	{
		if (s[i]>='0'&&s[i]<='9') s1.push_back(s[i]);else
			if (s[i]=='(') s2.push(s[i]);else
				if (s[i]==')') right();else 
					op(s[i]);
	}
	print();
	zprint();
	return 0;
}