栈、队列：中缀表达式转后缀表达式

奥普瓯江

原理：


备注：


代码：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #define MAXSIZE 100
   
4. 
   
5. typedef char Elemtype;
   
6. 
   
7. typedef struct
   
8. {
   
9.     Elemtype *base;
   
10.     Elemtype *top;
    
11.     int stacksize;
    
12. 
    
13. }SqStack;
    
14. 
    
15. 
    
16. void InitStack(SqStack **E);                         //初始化栈
    
17. void PushStack(SqStack **E, Elemtype N);                //进栈
    
18. Elemtype PopStack(SqStack *E);                        //出栈
    
19. void DeleStack(SqStack **E);                            //释放被占用内存地址
    
20. int NeedStack(SqStack *E);                         //把字符转换成数字
    
21. void OvHappy(SqStack **E, Elemtype N);             //字符输出
    
22. 
    
23. void OvHappy(SqStack **E, Elemtype N)               //字符输出
    
24. {
    
25.     Elemtype temp;
    
26.      if((*E)->base == (*E)->top)
    
27.     {
    
28.         PushStack(&(*E), N);
    
29.     }
    
30.     else
    
31.     {
    
32.         while(1)
    
33.         {
    
34.             if((*E)->base == (*E)->top)
    
35.             {
    
36.                 PushStack(&(*E), N);
    
37.                 return ;
    
38.             }
    
39.             else
    
40.             {
    
41.                 temp = PopStack(*E);
    
42.             }
    
43. 
    
44. 
    
45.             switch(N)
    
46.             {
    
47.                 case '+' :{
    
48. 
    
49.                      if(temp == '+' || temp == '-' || temp == '*' || temp == '/')
    
50.                     {
    
51.                         printf("%c", temp);
    
52.                     }
    
53.                     else if(temp == '(')
    
54.                     {
    
55.                         PushStack(&(*E), temp);
    
56.                         PushStack(&(*E), N);
    
57.                         return;
    
58.                     }
    
59.                 }
    
60.                 break;
    
61.                 case '-' :{
    
62.                       if(temp == '+' || temp == '-' || temp == '*' || temp == '/')
    
63.                     {
    
64.                         printf("%c", temp);
    
65.                     }
    
66.                     else if(temp == '(')
    
67.                     {
    
68.                         PushStack(&(*E), temp);
    
69.                         PushStack(&(*E), N);
    
70.                         return;
    
71.                     }
    
72.                 }
    
73.                 break;
    
74.                 case '*' :{
    
75.                      if(temp == '*' || temp == '/' )
    
76.                     {
    
77.                         printf("%c", temp);
    
78.                     }
    
79.                     else  if(temp == '+' || temp == '-' )
    
80.                     {
    
81.                         PushStack(&(*E), temp);
    
82.                         PushStack(&(*E), N);
    
83.                         return;
    
84.                     }
    
85.                     else if(temp == '(')
    
86.                     {
    
87.                         PushStack(&(*E), temp);
    
88.                         PushStack(&(*E), N);
    
89.                         return;
    
90.                     }
    
91.                 }
    
92.                 break;
    
93.                 case '/' :{
    
94.                      if(temp == '*' || temp == '/' )
    
95.                     {
    
96.                         printf("%c", temp);
    
97.                     }
    
98.                     else  if(temp == '+' || temp == '-' )
    
99.                     {
    
100.                         PushStack(&(*E), temp);
     
101.                         PushStack(&(*E), N);
     
102.                         return;
     
103.                     }
     
104.                     else if(temp == '(')
     
105.                     {
     
106.                         PushStack(&(*E), temp);
     
107.                         PushStack(&(*E), N);
     
108.                         return;
     
109.                     }
     
110.                 }
     
111.                 break;
     
112.                 case '(' :{
     
113.                        PushStack(&(*E), temp);
     
114.                        PushStack(&(*E), N);
     
115.                        return;
     
116.                 }
     
117.                 break;
     
118.                 case ')' :{
     
119.                     while(temp != '(')
     
120.                     {
     
121.                         printf("%c", temp);
     
122.                         temp = PopStack(*E);
     
123.                     }
     
124.                     return;
     
125.                 }
     
126.                 break;
     
127.             }
     
128. 
     
129.         }
     
130.     }
     
131. }
     
132. 
     
133. int NeedStack(SqStack *E)                         //把字符转换成数字
     
134. {
     
135.     int a = 0, b = 0;
     
136.     int i;
     
137.     for(i = 1; E->top != E->base; i *= 10)
     
138.     {
     
139.         a = (int)PopStack(E) - '0';
     
140.         b += a * i;
     
141.     }
     
142.     return b;
     
143. }
     
144. 
     
145. void DeleStack(SqStack **E)                            //释放被占用内存地址
     
146. {
     
147.     free((*E)->base);
     
148.     free(*E);
     
149. }
     
150. 
     
151. Elemtype PopStack(SqStack *E)                         //出栈
     
152. {
     
153.     E->top--;
     
154.     E->stacksize++;
     
155.     return *(E->top);
     
156. }
     
157. void InitStack(SqStack **E)                    //初始化栈
     
158. {
     
159.     *E = (SqStack *)malloc(sizeof(Elemtype ));
     
160.     if(!(*E))
     
161.     {
     
162.         printf("初始化*E内存分配错误\n");
     
163.         exit(0);
     
164.     }
     
165.     (*E)->base = (Elemtype *)malloc(MAXSIZE * sizeof(Elemtype ));
     
166.     if(!(*E)->base)
     
167.     {
     
168.         printf("初始化(*E)->base内存分配错误\n");
     
169.         exit(0);
     
170.     }
     
171.     (*E)->top = (*E)->base;
     
172.     (*E)->stacksize = MAXSIZE;
     
173. }
     
174. 
     
175. void PushStack(SqStack **E, Elemtype N)         //进栈
     
176. {
     
177.     if((*E)->top - (*E)->base >= (*E)->stacksize)       //检查栈是否不够了如果不够了就要增加栈的大小
     
178.     {
     
179.         (*E)->base = (Elemtype *)realloc((*E)->base, ((*E)->stacksize + MAXSIZE) * sizeof(Elemtype ));      //从新
     
180.         if(!(*E)->base)
     
181.         {
     
182.             printf("扩容内存分配错误\n");
     
183.             exit(0);
     
184.         }
     
185.         (*E)->top = (*E)->base + (*E)->stacksize;
     
186.         (*E)->stacksize = (*E)->stacksize + MAXSIZE;
     
187.     }
     
188.     *((*E)->top) = N;
     
189.     (*E)->top++;
     
190.     (*E)->stacksize--;
     
191. }
     
192. 
     
193. int main()
     
194. {
     
195.     char C;
     
196.     char N[100];
     
197.     int i;
     
198.     SqStack *L, *G;
     
199.     InitStack(&L);          //数字转换栈
     
200.     InitStack(&G);          //符号储存
     
201. 
     
202.     for(i = 0; (C = getchar()) != '#'; i++)     //输入
     
203.     {
     
204.         N[i] = C;
     
205.         N[i + 1] = '\0';
     
206.     }
     
207. 
     
208. 
     
209.     for(i = 0; N[i] != '\0'; i++)
     
210.     {
     
211.         if(N[i] >= '0' && N[i] <= '9')
     
212.         {
     
213.             while(N[i] >= '0' && N[i] <= '9')
     
214.             {
     
215.                 PushStack(&L, N[i]);
     
216.                 i++;
     
217.             }
     
218.             printf("%d", NeedStack(L));
     
219.         }
     
220. 
     
221.         //从新建立一个函数
     
222. 
     
223.         if(N[i] == '+'|| N[i] == '-' || N[i] == '*' || N[i] == '/' || N[i] == '(' || N[i] == ')')
     
224.         {
     
225.              OvHappy(&G, N[i]);
     
226.         }
     
227.         if(N[i+1] == '\0' && G->top != G->base)
     
228.         {
     
229.             printf("%c", PopStack(G));
     
230.         }
     
231.     }
     
232.     //输出
     
233.     return 0;
     
234. }
     

复制代码