当前位置：VC爱好者 → 一般性编程 → Data Structure(数据结构) → 正文
逆波兰表达式_数据结构作业
本文适合中级读者阅读  作者：郭郭    来源：vcLover.com    日期: 2008/01/31    浏览：

逆波兰表达式 rpn（Reverse Polish Notation）
逆波兰表达式，它的语法规定，表达式必须以逆波兰表达式的方式给出。逆波兰表达式又叫做后缀表达式。这个知识点在数据结构和编译原理这两门课程中都有介绍，下面是一些例子：

正常的表达式   逆波兰表达式
a+b                      a,b,+
a+(b-c)                 a,b,c,-,+
a+(b-c)*d              a,d,b,c,-,*,+
a=1+3                   a=1,3 +

http=(smtp+http+telnet)/1024 写成什么呢？
http=smtp,http,telnet,+,+,1024,/
代码运行结果如下：

折叠 C/C++ Code
  1. //V*C爱好者vc*lover.com   
  2. //www.vcLover.com   
  3. #include<stdio.h>   
  4. #include<math.h>   
  5. #include<conio.h>   
  6. #include<stdlib.h>   
  7. #define maxsize 80   
  8. #define datatype float   
  9.   
  10. typedef struct  
  11. {   
  12.     datatype a[maxsize];   
  13.     int top;   
  14. }stack;   
  15.   
  16. void initiate(stack * s)   
  17. {   
  18.     s->top=0;   
  19. }   
  20. /* 为便于调用时进行判断，将堆栈空设为0，不空设为1*/  
  21. int empty(stack s)    
  22. {   
  23.     if(s.top<=0)   
  24.     return 0;   
  25.     else  
  26.     return 1;   
  27. }   
  28.   
  29. int full(stack s) /* 满设为0 不满设为1 */  
  30. {   
  31.     if(s.top>=maxsize)   
  32.     return 0;   
  33.     else return 1;   
  34. }   
  35.   
  36. datatype top(stack s)   
  37. {   
  38.     if(empty(s))   
  39.     return s.a[s.top-1];   
  40.     else exit(1);   
  41. }   
  42.   
  43. void push(stack * s,datatype i)   
  44. {   
  45.     s->a[s->top]=i;   
  46.     s->top++;   
  47. }   
  48.   
  49. datatype pop(stack * s)   
  50. {   
  51.     datatype d;   
  52.     d=s->a[s->top-1];   
  53.     s->top--;   
  54.     return d;   
  55. }   
  56.   
  57. void disply(void)   
  58. {   
  59.     printf("Press any key to continue...\n");   
  60.     while(getchar()==NULL);   
  61. }   
  62.   
  63. void main(void)   
  64. {   
  65.     char c[80];   
  66.     int i,j,tag,c0;   
  67.     float c1,c2;   
  68.     stack s,num;   
  69.     initiate(&s);   
  70.     initiate(&num);   
  71.     printf("输入要转化的表达式:\n");   
  72.     gets(c);   
  73.     for(i=0;c[i]!='\0';i++)   
  74.     {   
  75.         if(c[i]>=48&&c[i]<=57)   
  76.         if(tag==1)   
  77.         (&num,c[i]);   
  78.         else  
  79.         {   
  80.             push(&num,' '); /* seperate two integers : xyz and abc */  
  81.             push(&num,c[i]);   
  82.             tag=1;   
  83.         }   
  84.         else if(c[i]=='(')   
  85.             push(&s,c[i]);   
  86.         else if(c[i]=='+')   
  87.         {   
  88.             while(empty(s)&&(top(s)=='*'||top(s)=='/'||top(s)=='^'||top(s)=='-'))   
  89.             {   
  90.                 push(&num,pop(&s));   
  91.             }   
  92.             push(&s,c[i]);   
  93.             tag=0;   
  94.         }   
  95.         else if(c[i]=='-')   
  96.         {   
  97.             while(empty(s)&&(top(s)=='*'||top(s)=='/'||top(s)=='^'||top(s)=='+'))   
  98.             {   
  99.             push(&num,pop(&s));   
  100.             }   
  101.             push(&s,c[i]);   
  102.             tag=0;   
  103.         }   
  104.         else if(c[i]=='*')   
  105.         {   
  106.             while(empty(s)&&(top(s)=='^'||top(s)=='/'))   
  107.             push(&num,pop(&s));   
  108.             push(&s,c[i]);   
  109.             tag=0;   
  110.         }   
  111.         else if(c[i]=='/')   
  112.         {   
  113.             while(empty(s)&&(top(s)=='^'||top(s)=='*'))   
  114.             push(&num,pop(&s));   
  115.             push(&s,c[i]);   
  116.             tag=0;   
  117.         }   
  118.         else if(c[i]=='^')   
  119.         {   
  120.             push(&s,c[i]);   
  121.             tag=0;   
  122.         }   
  123.         else if(c[i]==')')   
  124.         {   
  125.             while(top(s)!='(')   
  126.             push(&num,pop(&s));   
  127.             pop(&s); /* delete ( */  
  128.         }   
  129.     } /* for */  
  130.     while(empty(num))   
  131.     push(&s,pop(&num)); /* invert order to output the postfix */  
  132.     printf("波兰表达式: ");   
  133.     tag=0;   
  134.     while(empty(s))   
  135.     {   
  136.         c0=(int)pop(&s);   
  137.         printf("%c",c0);   
  138.         if(c0>='0'&&c0<='9')   
  139.         if(tag==1)   
  140.             push(&num,10*pop(&num)+(c0-48));   
  141.         else  
  142.         {   
  143.             push(&num,(c0-48));   
  144.             tag=1;   
  145.         }   
  146.         else  
  147.         {   
  148.             switch (c0)   
  149.             {   
  150.                 case ' ': break;   
  151.                 case '+': c1=pop(&num);c2=pop(&num);push(&num,c2+c1);break;   
  152.                 case '-': c1=pop(&num);c2=pop(&num);push(&num,c2-c1);break;   
  153.                 case '*': c1=pop(&num);c2=pop(&num);push(&num,c2*c1);break;   
  154.                 case '/': c1=pop(&num);c2=pop(&num);push(&num,c2/c1);break;   
  155.                 case '^': c1=pop(&num);c2=pop(&num);push(&num,pow(c2,c1));break;   
  156.                 default:break;   
  157.             }   
  158.         tag=0;   
  159.         }   
  160.     }   
  161.     printf("\n结果:%.0f\n",pop(&num));   
  162. }  

 

[关键词: 逆波兰表达式, 数据结构] [打印] [关闭]
上一篇：排序算法比较_冒泡,插入,快速,希尔排序算法   下一篇：单链表实现一元多项式相加
相关文章
查看全部评论相关评论
评论内容：
昵称： 验证码：验证码
What's New?
What's Hot?
Google Adsense!