中缀表达式转后缀表达式(PN-->RPN)

pwnmelife

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <ctype.h>
   
4. 
   
5. #define STACK_INIT_SIZE 20
   
6. #define STACKINCREAMENT 10
   
7. #define MAXBUFFER 10
   
8. 
   
9. typedef char ElementType;
   
10. 
    
11. typedef struct {
    
12.         ElementType* base;
    
13.         ElementType* top;
    
14.         int stackSize;
    
15. }sqStack;
    
16. 
    
17. void InitStack(sqStack* s);
    
18. bool StackEmpty(sqStack* s);
    
19. void Push(sqStack* s, ElementType e);
    
20. void Pop(sqStack* s, ElementType* e);
    
21. bool Priority(char operator1, char operator2);
    
22. void Output(sqStack* s);
    
23. int main()
    
24. {
    
25.         sqStack* s = (sqStack*)malloc(sizeof(sqStack*));
    
26.         InitStack(s);
    
27.         char buf[MAXBUFFER];
    
28.         char c, operator_stack;
    
29.         c = operator_stack = '0';
    
30.         double value;
    
31.         while (true) {
    
32.                 int i = 0;
    
33.                 while (true) {
    
34.                         scanf("%c", &c);
    
35.                         if (isdigit(c) || c == '.') {
    
36.                                 buf[i++] = c;
    
37.                         }
    
38.                         else if (c == ' ' && i != 0) {
    
39.                                 buf[i] = '\0';
    
40.                                 value = atof(buf);
    
41.                                 printf("%.2lf ", value);
    
42.                                 break;
    
43.                         }
    
44.                         else {
    
45.                                 break;
    
46.                         }
    
47.                 }
    
48.                 switch (c) {
    
49.                 case '+':
    
50.                 case '-':
    
51.                 case '*':
    
52.                 case '/':
    
53.                         while (true) {
    
54.                                 if (StackEmpty(s)) {
    
55.                                         Push(s, c);
    
56.                                         break;
    
57.                                 }
    
58.                                 else {
    
59.                                         Pop(s, &operator_stack);
    
60.                                         if (Priority(c, operator_stack)) {
    
61.                                                 Push(s, operator_stack);
    
62.                                                 Push(s, c);
    
63.                                                 break;
    
64.                                         }
    
65.                                         else {
    
66.                                                 printf("%c ", operator_stack);
    
67.                                         }
    
68.                                 }
    
69.                         }
    
70.                         break;
    
71.                 case '(':
    
72.                         Push(s, c);
    
73.                         break;
    
74.                 case')':
    
75.                         Pop(s, &c);
    
76.                         while (c != '(') {
    
77.                                 printf("%c ", c);
    
78.                                 Pop(s, &c);
    
79.                         }
    
80.                         break;
    
81.                 default:
    
82.                         break;
    
83.                 }
    
84.                 if (c == '#') {
    
85.                         break;
    
86.                 }
    
87.         }
    
88.         Output(s);
    
89. }
    
90. void InitStack(sqStack* s) {
    
91.         s->top = s->base = (ElementType*)malloc(STACK_INIT_SIZE * sizeof(double));
    
92.         if (!s->top) {
    
93.                 exit(0);
    
94.         }
    
95.         s->stackSize = STACK_INIT_SIZE;
    
96. }
    
97. bool StackEmpty(sqStack* s) {
    
98.         if (s->top == s->base) {
    
99.                 return true;
    
100.         }
     
101.         else {
     
102.                 return false;
     
103.         }
     
104. }
     
105. void Push(sqStack* s, ElementType e) {
     
106.         if (s->top - s->base >= s->stackSize) {
     
107.                 s->base = (ElementType*)realloc(s->base, s->stackSize + STACKINCREAMENT);
     
108.                 if (!s->base) {
     
109.                         exit(0);
     
110.                 }
     
111.                 s->stackSize = s->stackSize + STACKINCREAMENT;
     
112.         }
     
113.         *(s->top) = e;
     
114.         s->top++;
     
115. 
     
116. }
     
117. void Pop(sqStack* s, ElementType * e) {
     
118.         if (StackEmpty(s)) {
     
119.                 return;
     
120.         }
     
121.         *e = *--(s->top);
     
122. }
     
123. bool Priority(char operator_stackTop, char operator_ch) {
     
124.         if (((operator_stackTop == '*') || (operator_stackTop == '/') || (operator_stackTop == '+') || (operator_stackTop == '-'))
     
125.                 && (operator_ch == '(')) {
     
126.                 return true;
     
127.         }
     
128.         if (((operator_stackTop == '*') || (operator_stackTop == '/')) && ((operator_ch == '+') || (operator_ch == '-'))) {
     
129.                 return true;
     
130.         }
     
131.         else {
     
132.                 return false;
     
133.         }
     
134. }
     
135. void Output(sqStack* s) {
     
136.         char c;
     
137.         while (s->top != s->base) {
     
138.                 Pop(s, &c);
     
139.                 printf("%c ", c);
     
140.         }
     
141. }
     
142. /*
     
143. * 样例输入: 1 + 2 - 1 * ( ( 3 + 4 ) / 5 - 6 ) + 7 #
     
144. * 输出: 1 2 + 1 3 4 + 5 / 6 - * - 7 +
     
145. */
     
146. 
     

复制代码