时间戳

首页 > 技术文章 > SDUT2484算术表达式的转换

SDUT2484算术表达式的转换

luyingfeng 2013-07-30 20:40 原文

http://acm.sdut.edu.cn/sdutoj/showproblem.php?pid=2484&cid=1182

题目描述

小明在学习了数据结构之后，突然想起了以前没有解决的算术表达式转化成后缀式的问题，今天他想解决一下。
   因为有了数据结构的基础小明很快就解出了这个问题，但是他突然想到怎么求出算术表达式的前缀式和中缀式呢？小明很困惑。聪明的你帮他解决吧。

输入

 输入一算术表达式，以\'#\'字符作为结束标志。（数据保证无空格,只有一组输入）

输出

 输出该表达式转换所得到的前缀式 中缀式 后缀式。分三行输出，顺序是前缀式 中缀式 后缀式。

示例输入

a*b+(c-d/e)*f#

示例输出

+*ab*-c/def
a*b+c-d/e*f
ab*cde/-f*+

这个题的话，看了白皮书上的那个建树，然后再写上前后中序遍历就可以了，其余的话，注意一下输入就可以，代码中两种输入都可以。
  1 #include<cstdio>
  2 #include<cstring>
  3 #include<iostream>
  4 #include<cstdlib>
  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 }
View Code 


 这个题还有很多别的做法，可以借鉴一下大神们的博客


http://blog.csdn.net/lin375691011/article/details/9372245


这个的话贵在也简单在用了栈和队列，


http://www.cnblogs.com/kongkaikai/archive/2013/07/30/3224683.html


 













	

		


推荐阅读