题目描述 Description
对于 加、减、乘、除这种四则运算的表达式，我们使用的是先乘除、后加减的从左到右的顺序进行运算，如果要指定特定的顺序，就要增加括号进行表达，比如 (A+B)*C , A+(F-(A+Y))*(B-C)/D 。
除了上述表达方式之外，在1929年，波兰逻辑学家Lukasiewicz提出一种不用括号的逻辑符号体系，后来人们称之为波兰表示法，波兰表达式的特点是运算符位于运算对象的后面，因此称为后缀表示。在对波兰表达式进行运算，严格按照自左至右的顺序进行。下面给出一些表达式及其相应的波兰表达式。
|
普通表达式 |
波兰表达式 |
|
A-B |
AB- |
|
(A-B)*C+D |
AB-C*D+ |
|
(B+C)/(A-D) |
BC+AD-/ |
【普通表达式】
普通表达式 (EXP) 定义如下：
1、 大写字母 A,B,C,D …Z 是 EXP
2、 EXP+EXP , EXP–EXP , EXP*EXP , EXP/EXP 是EXP
3、 (EXP) 是EXP
普通表达式使用习惯性的括号优先。先乘除后加减的顺序进行运算。
【普通表达式转换成波兰表达式】
普通表达式可以按照运算顺序构建二叉树然后转换成波兰表达式。
例如：
(A-B)*C+D*E
对应的运算二叉树如下：
然后对该二叉树进行后序遍历，就可以得到波兰表达式： AB-C*DE*+
输入描述 Input Description
输入包含一行，50个字符以内，代表普通表达式
输出描述 Output Description
输出包含一行，代表转换后的波兰表达式
样例输入 Sample Input
(A-B)*C+D*E
样例输出 Sample Output
AB-C*DE*+
数据范围及提示 Data Size & Hint
输入包含一行，50个字符以内
/* 简单的表达式分析 */ #include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #define ll int #define fo(i,l,r) for(int i = l;i <= r;i++) #define fd(i,l,r) for(int i = r;i >= l;i--) using namespace std; const int maxn = 1050; ll read(){ ll x=0,f=1; char ch=getchar(); while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();}; while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}; return x*f; } char s[maxn],bo[maxn]; int cnt,rt; struct exp_t{ int lch[maxn],rch[maxn]; char op[maxn]; int nc; void cler(){ memset(lch,0,sizeof(lch)); memset(rch,0,sizeof(rch)); nc = 0; } int build(int l,int r){ int c1 = -1,c2 = -1,p=0; int u; if(l == r){ u = ++nc; lch[u] = rch[u] = 0; op[u] = s[l]; return u; } fo(i,l,r){ switch(s[i]){ case '(':p++;break; case ')':p--;break; case '+':case '-':if(!p) c1 = i;break; case '*':case '/':if(!p) c2 = i;break; } } if(c1 < 0) c1 = c2; if(c1 < 0) return build(l+1,r-1); u = ++nc; lch[u] = build(l,c1-1); rch[u] = build(c1+1,r); op[u] = s[c1]; return u; } void dfs(int x){ if(lch[x]) dfs(lch[x]); if(rch[x]) dfs(rch[x]); bo[++cnt] = op[x]; } void get_b(){ cnt = 0; dfs(rt); } }e; int main(){ scanf("%s",s+1); e.cler(); rt = e.build(1,strlen(s+1)); e.get_b(); fo(i,1,cnt) cout<<bo[i]; return 0; }