C++ :

#include<iostream>
#include<string>
#include<cctype>
#include<stack>
using namespace std;
struct node{
	int data;
	bool isnum;
	node *lch,*rch;
};
int pri[127];
stack<node *> opd;
stack<node *> opr;
void create(node *&root,const string &s) //建数据栈 和 符号栈 
{
	int i,len;
	node *p,*q,*r;
	for (i=0,len=s.size();i<len;i++)
	{
		if (isdigit(s[i])) {   //数据 
			p=new(node);
			p->data=s[i]-'0';   p->isnum=true;
			p->lch=p->rch=NULL;
			opd.push(p);
			continue;
		}
		if (s[i]=='(') {  //左括号 
			p=new(node);
			p->data=(int)s[i];   p->isnum=false;
			p->lch=p->rch=NULL;
			opr.push(p);
			continue;
		}
		if (s[i]==')'){  //右括号，出到左括号与之配对 
			p=opr.top();
			opr.pop();
			while (p->data!=(int)'('){ //出到左括号与之配对
				q=opd.top(); opd.pop(); p->rch=q; //出数据 
				q=opd.top(); opd.pop(); p->lch=q; //出数据 
				opd.push(p);  //运算后再入数据栈 
				p=opr.top();
				opr.pop();
			}
			continue;
		}
		//以下是其它运算符 
		p=new(node);
		p->data=(int)s[i];  p->isnum =false;
		p->lch=p->rch=NULL;		
		
		if (opr.empty())   { opr.push(p); continue; }
		char ch=(char)(opr.top()->data)	;	
		if (ch=='('||pri[s[i]]>pri[ch])	{ opr.push(p); continue; }			

		while (ch!='('&&pri[s[i]]<=pri[ch])	{  //当前字符优先级低于栈顶字符，注意左括号 
			r=opr.top(); opr.pop();
			q=opd.top(); opd.pop(); r->rch=q;
			q=opd.top(); opd.pop(); r->lch=q;
			opd.push(r);
			if (opr.empty()) break;
			ch=(char)(opr.top()->data)	;
		}
		opr.push(p);	
	}
	while (!opr.empty())
	{
		p=opr.top(); opr.pop();
		q=opd.top(); opd.pop(); p->rch=q;
		q=opd.top(); opd.pop(); p->lch=q;
		opd.push(p);
	}
	root=opd.top();
}
void deal(node *root)
{
	char ch=root->data;
	switch (ch)
	{
		case '+': root->data =root->lch->data + root->rch->data; break;
		case '-': root->data =root->lch->data - root->rch->data; break;
		case '*': root->data =root->lch->data * root->rch->data; break;
		case '/': root->data =root->lch->data / root->rch->data; break;
		case '^': int t=1;
				  for (int i=0;i<root->rch->data;i++)
				  	t*=root->lch->data;
				  root->data =t; 
				  break;
	}
	root->isnum =true;
	root->lch = root->rch = NULL;
}
void lastord(node *root,bool &merged)
{
	if (root) {
		lastord(root->lch,merged);
		lastord(root->rch,merged);
		if (root->isnum)
			cout<<root->data<<" ";
		else cout<<(char)root->data<<" " ;
		if (root->lch&&!merged){
			deal(root);
			merged=true;
		}
	}	
}
int main()
{
	pri['+']=1; pri['-']=1; pri['*']=2; pri['/']=2; pri['^']=3; 
	string s;
	node *root;
	cin>>s;
	create(root,s);
	bool merged;
	while (root->lch){		
		merged=false;
		lastord(root->lch,merged);
		lastord(root->rch,merged);
		cout<<(char)root->data<<endl; //左右根，这时根是运算符 
		if (root->lch&&!merged){  //最后一次运算merged在这里必然为假 
			deal(root);
			merged=true;
		}
	}
	cout<<root->data<<endl;
	return 0;
}