P1175 表达式的转换

#include <bits/stdc++.h>
using namespace std;
struct node{
	int l,r,v;
	char op;
}tree[1100];
int id;
int level(char c){
	if(c=='+'||c=='-')return 1;
	if(c=='*'||c=='/')return 2;
	if(c=='^')return 3;
	return 0;
}
void calc(stack<int> &st,stack<char> &op){
	int R=st.top();st.pop();
	int L=st.top();st.pop();
	++id;
	tree[id].l=L;
	tree[id].r=R;
	tree[id].op=op.top();
	op.pop();
	switch(tree[id].op){
		case '+':tree[id].v=tree[L].v+tree[R].v;break;
		case '-':tree[id].v=tree[L].v-tree[R].v;break;
		case '*':tree[id].v=tree[L].v*tree[R].v;break;
		case '/':tree[id].v=tree[L].v/tree[R].v;break;
		case '^':tree[id].v=(int)pow(tree[L].v,tree[R].v);break;
	}
	st.push(id);
}
void build(string s){
	stack<int>st;
	stack<char>op;
	s='('+s+')';
	for(int i=0;i<s.size();++i){
		if(s[i]>='0'&&s[i]<='9'){
			tree[++id].l=s[i]-'0';
			tree[id].r=0;
			tree[id].v=0;
			tree[id].op=0;
			st.push(id);
		}
		else{
			if(s[i]=='('||s[i]=='^')op.push(s[i]);
			else if(s[i]==')'){
				while(op.top()!='(')calc(st,op);
				op.pop();
			}
			else{
				while(!op.empty()&&level(op.top())>=level(s[i]))calc(st,op);
				op.push(s[i]);
			}
		}
	}
}
void write(int p){
	if(!p)return;
	write(tree[p].l);
	write(tree[p].r);
	if(tree[p].op)cout<<tree[p].op;
	else cout<<tree[p].v;
	if(p==id)cout<<"\n";
	else cout<<" ";
}
void solve(int p){
	if(!tree[p].op)return;
	solve(tree[p].l);
	solve(tree[p].r);
	tree[p].op=tree[p].l=tree[p].r=0;
	write(id);
}
int main(){
	string s;
	cin>>s;
	build(s);
	write(id);
	solve(id);
}

0分