题目描述
小明在学习了数据结构之后，突然想起了以前没有解决的算术表达式转化成后缀式的问题，今天他想解决一下。
因为有了数据结构的基础小明很快就解出了这个问题，但是他突然想到怎么求出算术表达式的前缀式和中缀式呢？小明很困惑。聪明的你帮他解决吧。
输入
输入一算术表达式，以\'#\'字符作为结束标志。（数据保证无空格,只有一组输入）
输出
输出该表达式转换所得到的前缀式 中缀式 后缀式。分三行输出，顺序是前缀式 中缀式 后缀式。
示例输入
a*b+(c-d/e)*f#
示例输出
+*ab*-c/defa*b+c-d/e*fab*cde/-f*+ 这个题的话，看了白皮书上的那个建树，然后再写上前后中序遍历就可以了，其余的话，注意一下输入就可以，代码中两种输入都可以。
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 const int maxn = 1000; 7 int lch[maxn],rch[maxn]; 8 char op[maxn]; 9 int nc=0; 10 int build_tree(char *s,int x,int y) 11 { 12 int i,c1=-1,c2=-1,p=0; 13 int u ; 14 if(y-x==1) 15 { 16 u=++nc; 17 lch[u]=rch[u] = 0; 18 op[u] = s[x] ; 19 return u; 20 } 21 22 for(i = x ; i < y ; i++) 23 { 24 switch(s[i]) 25 { 26 case '(': 27 p++; 28 break; 29 case ')': 30 p--; 31 break; 32 case '+': 33 case '-': 34 if(!p) c1=i; 35 break; 36 case '*': 37 case '/': 38 if(!p) c2=i; 39 break; 40 } 41 } 42 if(c1<0) c1 = c2 ; 43 if(c1 < 0) return build_tree(s,x+1,y-1); 44 u=++nc; 45 lch[u] = build_tree(s,x,c1); 46 rch[u] = build_tree(s,c1+1,y); 47 op[u] = s[c1]; 48 return u ; 49 } 50 void preorder(int u) 51 { 52 if(u) 53 { 54 printf("%c", op[u]); 55 preorder(lch[u]); 56 preorder(rch[u]); 57 } 58 } 59 60 void inorder(int u) 61 { 62 if(u) 63 { 64 inorder(lch[u]); 65 printf("%c", op[u]); 66 inorder(rch[u]); 67 } 68 } 69 70 void postorder(int u) 71 { 72 if(u) 73 { 74 postorder(lch[u]); 75 postorder(rch[u]); 76 printf("%c",op[u]); 77 } 78 } 79 int main() 80 { 81 char s[110]; 82 //int count ; 83 int i=0; 84 for(i = 0; ; i ++) 85 { 86 scanf("%c",&s[i]); 87 if(s[i]=='#') 88 break; 89 } 90 s[++i]='\0'; 91 /*scanf("%c",&s[i++]); 92 while(s[i-1]!='#') 93 { 94 scanf("%c",&s[i++]); 95 } 96 s[i]='\0';*/ 97 //scanf("%s",s); 98 int len = strlen(s); 99 int u = build_tree(s,0,len-1);100 preorder(u);101 printf("\n");102 inorder(u);103 printf("\n");104 postorder(u);105 printf("\n");106 return 0 ;107 }
这个题还有很多别的做法，可以借鉴一下大神们的博客
这个的话贵在也简单在用了栈和队列，