栈的运用（5）转换逆波兰式

---恢复内容开始----

养成良好的习惯，看了下别人写的博客，条理清晰，美观，整洁。借鉴下。

问题描述

设表达式有单字母变量和双目四则运算构成，试写一算法，将书写正确的表达式转换为逆波兰表达式。

问题分析

要准确地理解逆波兰式，比如表达式a+b*c-a+b/e的逆波兰式是abc*+a-be/+，根据这一点可以理清算法的思路。输入一个表达式，保存到一个数组中，第一个肯定是操作数，依然在数组中，数组下标为0，然后再遍历下一个，当它为运算符是压入栈中，下一个操作数放在数组下标为1的位置，再判断下一个，为运算符，则与栈中已有的运算符进行比较，如果此运算符级别较大，则将此运算符压入栈，反之，将栈中的运算符先弹出来，让此运算符先入栈，然后再将弹出来的运算符入栈，

---恢复内容结束---

代码

View Code

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 #define STACK_INIT_SIZE 100
  4 #define STACKINCREMENT 10
  5 typedef char  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 
 22 int GetTop(stack &s,ElemType &e)//ElemType &e又代表什么意思呢？代表指针，取地址
 23 {
 24     if(s.top==s.base)
 25         return 0;
 26     e=*(s.top-1);//明白为什么要先减一
 27     return 1;
 28 }
 29 
 30 int Push(stack &s,ElemType e)
 31 {
 32     if(s.top-s.base>=s.stacksize){
 33         s.base=(ElemType *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(ElemType));
 34         if(!s.base) exit(0);
 35         s.top=s.base+s.stacksize;
 36         s.stacksize+=STACKINCREMENT;
 37     }
 38     *s.top++=e;//先赋值给s.top然后再将指针加一
 39     return 1;
 40 }
 41 
 42 int Pop(stack &s,ElemType  &e){
 43     if(s.top==s.base) return 0;
 44     e=*--s.top;
 45     return 1;
 46 }
 47 bool emptystack(stack &s);
 48 bool IsOperator(char c);
 49 bool Compare(char c1,char c2);
 50 int main()
 51 {
 52   stack s;
 53   Initstack(s);
 54   ElemType e;
 55   char temp;
 56   char a[40];
 57   printf("请输入表达式：");
 58   scanf("%s",a);
 59   int i=0,j=0;
 60   while(a[i]){
 61       if(!IsOperator(a[i])){//是操作数
 62           a[j]=a[i];
 63           i++;
 64           j++;
 65       }
 66      else{//是运算符
 67         if(!emptystack(s))
 68         {
 69           GetTop(s,e);//得到栈中顶端的运算符
 70           if(Compare(e,a[i])){//当下一个运算符的级别高于栈中的运算符时
 71                Push(s,a[i]);//直接入栈即可     
 72                i++;
 73           }
 74           else//若下一个运算符的级别低于栈中的元素时，将运算符出栈
 75           {
 76               while(!emptystack(s))
 77               {
 78                   Pop(s,e);
 79                   a[j]=e;
 80                   j++;
 81               }
 82           }
 83         }
 84         else{//是第一个运算符，第一个肯定是先入栈的
 85            Push(s,a[i]);
 86           i++;
 87        }
 88       }
 89   }
 90   while(!emptystack(s))
 91               {
 92                   Pop(s,e);
 93                   a[j]=e;
 94                   j++;
 95               }
 96   printf("%s",a);
 97       
 98  return 1;
 99           
100 }
101 bool emptystack(stack &s){
102     if(s.top==s.base)
103         return true;
104     else 
105         return false;
106 }
107 bool IsOperator(char c){
108     switch (c){
109 
110     case '+':return true;break;
111     case'-':return true;break;
112     case'*':return true;break;
113     case'/':return true;break;
114         
115     default:
116         return false;
117         break;
118     }
119 }
120 bool Compare(char c1,char c2){
121     if((c1=='+'||c1=='-')&&(c2=='*'||c2=='/'))
122         return true;
123     else
124         return false;
125 }

总结

说实话，可能这才算真正意义上的编程了，昨晚这代码还没调试成功，朋友就来叫我回去，看到自己思路属于混乱状态，也就没有继续做下去，回去的时候在想，有些基本的知识我并不懂，思路也不是很清晰，想问题会卡在某个地方。这是最重要的问题，学会思考，条理清晰，善于分析。我不得不说，自己以前的学习都是在“伪学习”，没有这些思考，也就尝不到学习的乐趣，相应地也就会把学习作为一种负担，我希望这是一个开始，现在意识到这些问题还不迟，我的学习态度，学习方法应该要有个大的转变。

我得承认写这个代码，让我对栈的基本操作有了更深的认识，并学会运用，刚开始只是知道这么个概念，学以致用，继续加油！