栈的运用(6)逆波兰式求值

问题描述

对以逆波兰式的表达式求值。

问题分析

上一题是把中缀表达式编程逆波兰式，要对逆波兰的表达式的求解就更简单些了。

代码

View Code

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 #define STACK_INIT_SIZE 100
  4 #define STACKINCREMENT 10
  5 typedef int  ElemType;
  6 typedef struct{
  7     ElemType  *base;
  8     ElemType  *top;
  9     int stacksize;
 10 }stack;
 11 
 12 int Initstack(stack &s)
 13 {
 14     
 15     s.base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
 16     if(!s.base) exit(0);
 17     s.top=s.base;
 18     s.stacksize=STACK_INIT_SIZE;
 19     return 1;
 20 }
 21 int Push(stack &s,ElemType e)
 22 {
 23     if(s.top-s.base>=s.stacksize){
 24         s.base=(ElemType *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(ElemType));
 25         if(!s.base) exit(0);
 26         s.top=s.base+s.stacksize;
 27         s.stacksize+=STACKINCREMENT;
 28     }
 29     *s.top++=e;//先赋值给s.top然后再将指针加一
 30     return 1;
 31 }
 32 int Pop(stack &s,ElemType  &e){
 33     if(s.top==s.base) return 0;
 34     e=*--s.top;
 35     return 1;
 36 }
 37 bool IsOperator(char c);
 38 int main()
 39 {
 40   stack s;
 41   Initstack(s);
 42   ElemType e1,e2;
 43   char  a[40];
 44   printf("请输入表达式：");
 45   scanf("%s",a);
 46   int i=0,j=0,temp;
 47   while(a[i]){
 48       if(!IsOperator(a[i])){//是操作数,要把它转换为整数
 49           a[j]=a[i]-'0';
 50           Push(s,a[j]);
 51           i++;
 52           j++;
 53       }
 54      else
 55      {//是运算符
 56       if(j>1)//里面有两个操作数
 57       {
 58           switch(a[i]){
 59           case'+':
 60               Pop(s,e1);
 61               Pop(s,e2);
 62               a[j]=e2+e1;
 63               Push(s,a[j]);
 64               //a[j]=a[j-2]+a[j-1];
 65               i++;
 66               j++;
 67               break;
 68           case'-':
 69               Pop(s,e1);
 70               Pop(s,e2);
 71               a[j]=e2-e1;
 72               Push(s,a[j]);
 73             // a[j]=a[j-2]-a[j-1];
 74              i++;
 75              j++;
 76              break;
 77           case'*':
 78               Pop(s,e1);
 79               Pop(s,e2);
 80               a[j]=e2*e1;
 81               Push(s,a[j]);
 82              //a[j]=a[j-2]*a[j-1];
 83              i++;
 84              j++;
 85              break;
 86           case'/':
 87               Pop(s,e1);
 88               Pop(s,e2);
 89               a[j]=e2/e1;
 90               Push(s,a[j]);
 91              //a[j]=a[j-2]/a[j-1];
 92              i++;
 93              j++;
 94              break;
 95           default:
 96               printf("你输入的不是正确的逆波兰式\n");
 97               break;
 98           }
 99       }
100      else
101      {
102        printf("你输入的不是正确的逆波兰式\n");
103        break;
104      }
105        
106      }
107   }
108   printf("%d\n",a[j-1]);      
109  return 1;          
110 }
111 bool IsOperator(char c){
112     switch (c){
113     case '+':return true;break;
114     case'-':return true;break;
115     case'*':return true;break;
116     case'/':return true;break;
117     default:
118         return false;
119         break;
120     }
121 }

总结

这道题开始想的时候只用到数组的变换，a[j]=a[j-2]+a[j-1]可以看到代码中的注释，就是自己开始的想法，刚开始用简单的数据测试的时候没有出现问题，但是数据变复杂了就出现问题了，比如 123*+这个计算的结果应该是7，但是输出的结果是9，后来发现问题了，这里计算的步骤是2*3+3=9，所以这就出现问题了，这也是为什么要用栈的原因吧，先将两个数出栈，将结果计算出来后再入栈，就不会出现这样的问题了，开始，还有个小问题，没有把字符转换成整型，计算出来的结果是比较大的数据。