Time Limit: 1000 ms Memory Limit: 65536 KiB
Problem Description
小明在学习了数据结构之后，突然想起了以前没有解决的算术表达式转化成后缀式的问题，今天他想解决一下。
因为有了数据结构的基础小明很快就解出了这个问题，但是他突然想到怎么求出算术表达式的前缀式和中缀式呢？小明很困惑。聪明的你帮他解决吧。
Input
输入一算术表达式，以\'#\'字符作为结束标志。（数据保证无空格,只有一组输入）
Output
输出该表达式转换所得到的前缀式 中缀式 后缀式。分三行输出，顺序是前缀式 中缀式 后缀式。
Sample Input
a*b+(c-d/e)*f#Sample Output
+*ab*-c/def a*b+c-d/e*f ab*cde/-f*+Hint
Source
#include <bits/stdc++.h> using namespace std; typedef struct node { char *base; char *top; } Stack; char s1[123], s2[123]; void push(Stack &S, char e) { * S.top = e; S.top++; } void pop(Stack &S, char &e) { S.top--; e = *S.top; } void intit(Stack &S) { S.base = (char *)malloc(100 * sizeof(char)); S.top = S.base; } int Empty(Stack S) { if(S.base==S.top) return 1; else return 0; } void tofront(Stack &S, int n) { int i; int j = 0; for(i = n-2; i>=0; i--) { if(s1[i]>='a'&&s1[i]<='z') s2[j++] = s1[i]; else if((s1[i]=='-'||s1[i]=='+')&&!Empty(S)&&(*(S.top-1)=='*'||*(S.top-1)=='/')) { pop(S, s2[j++]); push(S, s1[i]); } else if(s1[i]=='(') { while(*(S.top-1)!=')') { pop(S, s2[j++]); } S.top--; } else { push(S, s1[i]);//转化为前缀式优先级相同的运算符压入栈中 } } while(!Empty(S)) { pop(S, s2[j++]); } s2[j] = '\0'; for(j = j-1; j>=0; j--) printf("%c", s2[j]); printf("\n"); } void fx() { int i; for(i = 0; s1[i]!='#'; i++) if(s1[i]!='('&&s1[i]!=')') printf("%c", s1[i]); printf("\n"); } void tolast(Stack &S, int n) { int i; int j = 0; for(i = 0; i<n-1; i++) { if(s1[i]>='a'&&s1[i]<='z') s2[j++] = s1[i]; else if(((s1[i]=='-'||s1[i]=='+')&&!Empty(S)&&*(S.top-1)!='(') ||((s1[i]=='/'||s1[i]=='*')&&!Empty(S)&&(*(S.top-1)=='*'||*(S.top-1)=='/'))) { pop(S, s2[j++]); push(S, s1[i]); } else if(s1[i]==')') { while(*(S.top-1)!='(') { pop(S, s2[j++]); } S.top--; } else { push(S, s1[i]); } } while(!Empty(S)) { pop(S, s2[j++]); } s2[j] = '\0'; for(i = 0; s2[i]!='\0'; i++) printf("%c", s2[i]); printf("\n"); } int main() { int n; Stack S; intit(S); gets(s1); n = strlen(s1); tofront(S, n); fx(); tolast(S, n); return 0; }