1 #include
     
        2 #include
      
         3 #define Stack_Size 100  4 #define StackIncrement 10  5 #define Ok 1  6 #define Error 0  7 #define True 1  8 #define False 0  9 #define Overflow -2 10 typedef int status; 11 //字符栈的操作 12 typedef struct 13 { 14   char *base; 15   char *top; 16   int stacksize; 17 }SqStack; 18 status InitStack(SqStack &S) 19 { 20   S.base=(char *)malloc(Stack_Size*sizeof(char)); 21   if(!S.base)  exit(Overflow); 22   S.top=S.base; 23   S.stacksize=Stack_Size; 24   return Ok; 25 } 26 status StackEmpty(SqStack &S) 27 { 28   if(S.top==S.base) 29   return True; 30   return False; 31 } 32 status GetTop(SqStack S,char &e) 33 { 34     if(S.top==S.base)  return Error; 35     e=*(S.top-1); 36     return Ok; 37 } 38 status Push(SqStack &S,char e) 39 { 40   if((S.top-S.base)==S.stacksize) 41   { 42     S.base=(char *)realloc(S.base,(S.stacksize+StackIncrement)*sizeof(char)); 43     if(!S.base)  exit(Overflow); 44     S.top=S.base+S.stacksize; 45     S.stacksize+=StackIncrement; 46   } 47   *S.top++=e; 48   return Ok; 49 } 50 status Pop(SqStack &S,char &e) 51 { 52   if(S.top==S.base)  return Error; 53   e=*--S.top; 54   return Ok; 55 } 56 //转化的操作过程 57 static int i=0; 58 status Pass(char *s,char c) 59 { 60     s[i]=c; 61     i++; 62     return Ok; 63 } 64 status In(char c) 65 { 66   switch(c) 67   { 68     case '+': 69     case '-': 70     case '*': 71     case '/': 72     case '(': 73     case ')': 74     case '#':return True; 75     default :return False; 76   } 77 } 78 int Precede(char t1,char t2) 79  {  80    int f=0; 81    switch(t1) 82    { case '+': 83      case '-':if(!(t2=='('||t2=='*'||t2=='/')) 84                 f=1;  85               break; 86      case '*': 87      case '/':if(t2!='(') 88                 f=1;  89               break; 90      case '(':if(t2=='#') 91               {printf("缺乏左括号\n"); 92                exit(Overflow);} 93                break; 94      case ')':if(t2!='(') 95               f=1; 96               else 97               { 98                       printf("括号不匹配\n"); 99                     exit(Overflow);100               }101    }102    return f;103  }104 status Converse(char *s)105 {106     SqStack OPTR;107     char ch,x,c=getchar();108     InitStack(OPTR); Push(OPTR,'#');109     while(!StackEmpty(OPTR))110     {111         if(!In(c))112             Pass(s,c);113         else114         switch(c)115         {116             case '(': Push(OPTR,c);break;117             case ')': Pop(OPTR,ch);while(ch!='('){Pass(s,ch);Pop(OPTR,ch);}break;118             default :119                       while(GetTop(OPTR,ch)&&Precede(ch,c))120                       {121                           Pass(s,ch);Pop(OPTR,ch);122                       }123                       if(c!='#')124                       Push(OPTR,c);                 125         }126         if(c!='#')127             c=getchar();128         else129         {130             Pop(OPTR,ch);131             Pass(s,ch);132         }133     }134     s[i]='\0';135     return Ok;136 }137 //主函数138 status main()139 {140     char s[100];141     puts("请输入算术表达式：");142     Converse(s);143     puts("转化后的后缀表达式为：");144     puts(s);145     return Ok;146 }