접미사 표현식 - 접미사 표현식 M

  1 #include<stdio.h>

  2 #include<stdlib.h>

  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(" 
");

 92                exit(Overflow);}

 93                break;

 94      case ')':if(t2!='(')

 95               f=1;

 96               else

 97               {

 98                       printf(" 
");

 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         else

114         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         else

129         {

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 }