中缀表达式转后缀表达式

  1 //中缀表达式转换为后缀表达式(逆波兰表达式)
  2 #include <stdio.h>
  3 #include <stdlib.h>
  4 #include <math.h>
  5 #include <ctype.h>
  6 
  7 #define STACK_INIT_SIZE        20    //初始栈大小
  8 #define STACK_INCREMENT        10  //扩充栈时每次增加的内存
  9 #define MAXBUFFER            10  //缓冲区
 10 
 11 typedef char ElemType;            //栈中的数据类型
 12 typedef struct {
 13     ElemType *base;
 14     ElemType *top;
 15     int stackSize;
 16 }sqStack;
 17 
 18 //初始化栈
 19 void init_stack(sqStack *s){
 20     s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
 21     if(!s->base)
 22         exit(-1);
 23     s->top = s->base;
 24     s->stackSize = STACK_INIT_SIZE;
 25 }
 26 //入栈
 27 void push(sqStack *s,ElemType e){
 28     if(s->top - s->base >= s->stackSize){    //检测栈是否已满
 29         //若是已满，则自动扩大栈空间
 30         s->base = (ElemType *)realloc(s->base, (s->stackSize + STACK_INCREMENT)*sizeof(ElemType));
 31         if(!s->base)
 32             exit(-1);
 33     }
 34     *(s->top) = e;
 35     s->top++;
 36 }
 37 //出栈
 38 void pop(sqStack *s, ElemType *e){
 39     if(s->top == s->base){
 40         return ;
 41     }
 42     *e = *(--(s->top));
 43 }
 44 //求栈数据的个数,由于我们不会对其修改，故此处不需传指针
 45 int  stack_len(sqStack s){
 46     return (s.top - s.base); //返回数据的个数    
 47 }
 48 
 49 int main(void){
 50     sqStack s;
 51     char c;
 52     char d,e;
 53     int i = 0;
 54     
 55     init_stack(&s);
 56 
 57     printf("请按输入中缀表达式，以#作为结束标志：

");
 58     scanf("%c",&c);
 59     while(c != '#'){
 60         while(c >= '0' && c <= '9'){
 61             printf("%c",c);
 62             scanf("%c",&c);
 63             if(c<'0' || c>'9'){
 64                 printf(" ");
 65             }
 66         }
 67         if(')' == c){
 68             pop(&s,&e);
 69             while('(' != e){
 70                 printf("%c ",e);
 71                 pop(&s,&e);
 72             }
 73         }else if( '+' == c|| '-'==c){
 74             if(!stack_len(s)){
 75                 push(&s,c);
 76             }else{
 77                 do{
 78                     pop(&s,&e);
 79                     if('(' == e){
 80                         push(&s,e);
 81                     }else{
 82                         printf("%c ",e);
 83                     }
 84                 }while(stack_len(s) && '(' != e);
 85                 push(&s, c);
 86             }
 87         }else if('*' == c || '/'==c || '('==c){
 88             push(&s,c);
 89         }else if('#' == c){
 90             break;
 91         }else{
 92             printf("请输入正确的中缀表达式!!!
");
 93             return -1;
 94         }
 95         scanf("%c",&c);
 96     }
 97     while(stack_len(s)) {
 98         pop(&s,&d);        //将最终的计算结果弹出
 99         printf("%c ",d);
100     }
101     printf("

");
102     return 0;
103 }