中缀表达式转后缀表达式

梅祥

1. 
   
2. #include"stdio.h"
   
3. #include"stdlib.h"
   
4. 
   
5. #define STACK_INIT_SIZE 20
   
6. #define STACKINCREMENT 10
   
7. 
   
8. typedef char ElemType;
   
9. typedef struct
   
10. {
    
11.         ElemType *base;
    
12.         ElemType *top;
    
13.         int stacksize;
    
14. }sqstack;
    
15. 
    
16. int Initstack(sqstack *s)
    
17. {
    
18.         s->base=(ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
    
19.         if(!s->base)
    
20.         {
    
21.                 exit(0);
    
22.         }
    
23.         s->top=s->base;
    
24.         s->stacksize=STACK_INIT_SIZE;
    
25.         return 0;
    
26. }
    
27. 
    
28. int push(sqstack *s,ElemType e)
    
29. {
    
30.         if(s->top-s->base>=s->stacksize)
    
31.         {
    
32.                 s->base=(ElemType *)realloc(s->base,(s->stacksize + STACKINCREMENT) * sizeof(ElemType));
    
33.                 if(!s->base)
    
34.                 {
    
35.                         exit(0);
    
36.                 }
    
37.         }
    
38.     *(s->top)=e;
    
39.         s->top++;
    
40.         return 0;
    
41. }
    
42. 
    
43. int pop(sqstack *s,ElemType *e)
    
44. {
    
45.         if(s->top==s->base)
    
46.         {
    
47.                 return 0;
    
48.         }
    
49.         *e=*(--s->top);
    
50.         return 0;
    
51. }
    
52. 
    
53. int stackLen(sqstack s)
    
54. {
    
55.         return (s.top-s.base);  
    
56. }
    
57. 
    
58. int main()
    
59. {
    
60.     sqstack s;
    
61.     char c, e;
    
62. 
    
63.     Initstack( &s );
    
64. 
    
65.     printf("请输入中缀表达式，以#作为结束标志：");
    
66.     scanf("%c", &c);
    
67. 
    
68.     while( c != '#' )
    
69.     {
    
70.         while( c>='0' && c<='9' )
    
71.         {
    
72.             printf("%c", c);
    
73.             scanf("%c", &c);
    
74.             if( c<'0' || c>'9' )
    
75.             {
    
76.                 printf(" ");
    
77.             }
    
78.         }
    
79. 
    
80.         if( ')' == c )
    
81.         {
    
82.             pop(&s, &e);
    
83.             while( '(' != e )
    
84.             {
    
85.                 printf("%c ", e);
    
86.                 pop(&s, &e);
    
87.             }
    
88.         }
    
89.         else if( '+'==c || '-'==c )
    
90.         {
    
91.             if( !stackLen(s) )
    
92.             {
    
93.                 push(&s, c);
    
94.             }
    
95.             else
    
96.             {
    
97.                 do
    
98.                 {
    
99.                     pop(&s, &e);
    
100.                     if( '(' == e )
     
101.                     {
     
102.                         push(&s, e);
     
103.                     }
     
104.                     else
     
105.                     {
     
106.                         printf("%c ", e);
     
107.                     }
     
108.                 }while( stackLen(s) && '('!=e );
     
109.                 push(&s, c);
     
110.             }
     
111.         }
     
112.         else if( '*'==c || '/'==c || '('==c )
     
113.         {
     
114.             push(&s, c);
     
115.         }
     
116.         else if( '#'== c )
     
117.         {
     
118.             break;
     
119.         }
     
120.         else
     
121.         {
     
122.             printf("\n出错：输入格式错误！\n");
     
123.             return -1;
     
124.         }
     
125. 
     
126.         scanf("%c", &c);
     
127.     }
     
128. 
     
129.     while( stackLen(s) )
     
130.     {
     
131.         pop(&s, &e);
     
132.         printf("%c ", e);
     
133.     }
     
134.     printf("\n");
     
135.     return 0;
     
136. }
     

复制代码

zsszss