逆波兰表达式模型

　　其实这个东西早在7月开始的时候我就写好了，本来想等小师妹写好了她的版本再放到网上的。。。无奈她写的实在是太慢了。这个东西还是有改进的空间的，比如升级成浮点模型啥的。

　　逆波兰表达式的可以以O（N）时间复杂度处理任意表达式，其实也叫后缀表达式，中缀表达式（就是我们一般看到的表达式（1+1=2）），处理的时候分两个栈，一个符号栈，一个表达式栈：

　　（注意我只选二元运算符为例，只处理+-*/和括号）

　　1. 如果遇到数字，压入表达式栈

　　2. 如果遇到符号

　　　　a. 如果符号是左括号，则直接压入符号栈

　　　　b. 如果是*/符号，且符号栈顶符号为+-或者( ，那么直接压入当前符号即可；如果符号栈顶为*/，弹出符号栈顶符号到表达式栈，压入当前符号。

　　　　c. 如果是+-号，如果符号栈栈顶是*/，则pop符号栈顶到最近的+-号或者（；如果是+-或者（，那就直接弹出上一个+/-号然后压入当前+/-号。

　　　　d. 遇到）就pop符号栈到（

　　　　e. 如果把中缀表达式扫完了符号栈还有东西，那么将符号栈的东西全部pop到表达式栈。

　　后缀转中缀是上面的逆过程，看代码就知道了。

　　之前有想过改成C++的，但是那段时间忙着出Qt，就没写了，这以后可能每三天就写个算法或者复习下以前的数据结构，备战下下一年的面试，就酱~

　　以后博客的名字就不分类型拉~感觉直接分类更快。

  1 //main.c
  2 
  3 #include <stdio.h>
  4 #include "plug.h"
  5 #include "stack.h"
  6 #include <stdlib.h>
  7 #include <string.h>
  8 #include <math.h>
  9 #include <assert.h>
 10 
 11 int main(int argc, char *argv[])
 12 {
 13     int error_exp = 0;
 14     char symnum[81] = { '' };
 15     FILE *fp_in = fopen("D:\input.txt", "r");
 16     FILE *fp_out = fopen("D:\output.txt", "w");
 17     if (fp_in == NULL)
 18         exit(1);
 19 
 20     while (!feof(fp_in))
 21     {
 22         fscanf(fp_in, "%s", symnum);
 23         fprintf(fp_out, " Infix expression:  %s
", symnum);
 24         error_exp += scan_Infix_to_Suffix(symnum, fp_out);
 25         fprintf(fp_out, "
");
 26     }
 27     fprintf(fp_out, "
Sum of error expression: %d
", error_exp);
 28 
 29     return EXIT_SUCCESS;
 30 }
 31 
 32 int scan_Infix_to_Suffix(char *input, FILE *fp)
 33 {
 34     int i = 0;
 35     Stack_manager *num_stack = allcoate_stack_man(),
 36                   *stack_man = allcoate_stack_man(),
 37                   *sym_man = allcoate_stack_man();
 38     Stack **list = (Stack **)malloc(sizeof(Stack)*MAX);//存指向栈的指针的表
 39 
 40     for (;input[i]!='';i++)
 41     {
 42         if (input[i] >= '0' && input[i] <= '9')
 43             //把所有连续的数字先结合起来形成一个数，如果遇到符号，则把num栈转化为数字存入主栈中
 44             push_in_int(num_stack, input[i] - '0');
 45         //遇到'('，优先级最高，直接压栈
 46         else if (input[i] == '(')
 47             push_in_char(sym_man, input[i]);
 48         else if (input[i] == '*' || input[i] == '/')
 49         {
 50             //遇到乘除号，如果栈中含有（'+'或者'-'），压入符号栈
 51             if (input[i - 1] != ')')
 52                 push_in_int(stack_man, combine_Stack_to_Num(num_stack));
 53 
 54             //错误处理
 55             if ((stack_man->top->type == is_int && input[i] == '/')//除数不能为0
 56                 || i == 0                                           //开头出现单独乘除号
 57                 || input[i - 1] == '+' || input[i - 1] == '-'       //两个符号连续
 58                 || input[i - 1] == '*' || input[i - 1] == '/'
 59                 )
 60             {
 61                 error(sym_man, stack_man, num_stack, list, fp);
 62                 return 1;
 63             }
 64 
 65             if (sym_man->top == NULL
 66                 || (sym_man->top->sym == '+' || sym_man->top->sym == '-')
 67                 && sym_man->top->sym == '(')
 68                 //除非处理闭括号，否则看到'('什么符号都压栈
 69                 push_in_char(sym_man, input[i]);
 70 
 71             //否则弹出上一个乘除号
 72             else if (sym_man->top->sym == '*' || sym_man->top->sym == '/')
 73             {
 74                 push_in_char(stack_man, sym_man->top->sym);
 75                 pop_out(sym_man);
 76                 push_in_char(sym_man, input[i]);
 77             }
 78         }
 79         else if (input[i] == '+' || input[i] == '-')
 80         {
 81             if (input[i - 1] != '(' && input[i - 1] != ')' && i != 0)
 82                 push_in_int(stack_man, combine_Stack_to_Num(num_stack));
 83 
 84             //错误处理（开头连续两个加减号或者连续三个符号）
 85             if (i == 1 && (input[i - 1] == '+' || input[i - 1] == '-'))
 86             {
 87                 error(sym_man, stack_man, num_stack, list, fp);
 88                 return 1;
 89             }
 90             if (i >= 2 && (input[i - 1] == '+' || input[i - 1] == '-')
 91                 && (input[i - 2] == '+' || input[i - 1] == '-' || input[i - 1] == '*' || input[i - 1] == '/'
 92                 || input[i - 1] == '(' || input[i - 1] == ')'))
 93             {
 94                 error(sym_man, stack_man, num_stack, list, fp);
 95                 return 1;
 96             }
 97 
 98             //如果前一个为符号或者左括号或者没有符号，则为数的正负，压入数栈
 99             if (i == 0
100                 || input[i - 1] == '+' || input[i - 1] == '-'
101                 || input[i - 1] == '*' || input[i - 1] == '/'
102                 || input[i - 1] == '(')
103                 push_in_char(num_stack, input[i]);
104 
105             //如果有比+-优先级更高的运算符（'*','/'），则把符号弹出直到上一次的加减号或者'('为止
106             else if (!sym_man->top
107                 || sym_man->top->sym == '*' || sym_man->top->sym == '/'
108                 || sym_man->top->sym == '(')//符号为'('的情况合并到这里了
109             {
110                 for (;sym_man->top != NULL
111                     && sym_man->top->sym != '(';)
112                 {
113                     push_in_char(stack_man, sym_man->top->sym);
114                     pop_out(sym_man);
115                 }
116                 push_in_char(sym_man, input[i]);
117             }
118             //如果上一个符号是+-号，那么直接弹出上一个加减号到主栈，并且把当前符号压入符号栈
119             else if (sym_man->top->sym == '+' || sym_man->top->sym == '-')
120             {
121                 push_in_char(stack_man, sym_man->top->sym);
122                 pop_out(sym_man);
123                 push_in_char(sym_man, input[i]);
124             }
125         }
126         else if (input[i] == ')')
127         {
128             push_in_int(stack_man, combine_Stack_to_Num(num_stack));
129 
130             for (;sym_man->top != NULL && sym_man->top->sym != '(';)
131             {
132                 push_in_char(stack_man, sym_man->top->sym);
133                 pop_out(sym_man);
134             }
135             if (sym_man->top->sym != '(')//只有右括号括号，出错
136             {
137                 error(sym_man, stack_man, num_stack, list, fp);
138                 return 1;
139             }
140             pop_out(sym_man);//弹掉'('
141         }
142         else//其他情况均为不合法的情况，out
143         {
144             error(sym_man, stack_man, num_stack, list, fp);
145             return 1;
146         }
147     }
148     //最后应该还有一个数字的
149     if (input[i - 1] != ')')
150         push_in_int(stack_man, combine_Stack_to_Num(num_stack));
151 
152     //把剩下的符号弹入栈中
153     for (;sym_man->top!=NULL;)
154     {
155         if (sym_man->top->sym == '(')//只有左括号，出错
156         {
157             error(sym_man, stack_man, num_stack, list, fp);
158             return 1;
159         }
160         push_in_char(stack_man, sym_man->top->sym);
161         pop_out(sym_man);
162     }
163     copy_Stack_to_List(list, stack_man);
164     print_list(list, stack_man->node_sum, fp);
165     caculate_Infix(list, stack_man->node_sum,fp);
166 
167     //正常退出
168     delete_stack(&sym_man);
169     delete_stack(&stack_man);
170     delete_stack(&num_stack);
171     free(list);
172     return 0;
173 }
174 
175 int combine_Stack_to_Num(Stack_manager *const num_stack)
176 {
177     int sum = 0, num_pow = 0;
178     for (;num_stack->top != NULL;)
179     {
180         if (num_stack->top->type == is_int)
181             sum += (int)(num_stack->top->num*pow(10.0, (double)num_pow++));
182         else
183             sum = num_stack->top->sym == '+' ? sum : -sum;
184         pop_out(num_stack);
185     }
186     return sum;
187 }
188 
189 void copy_Stack_to_List(Stack **const list, Stack_manager *const stack_man)
190 {
191     int j = stack_man->node_sum - 1;
192     Stack *tmp = stack_man->top;
193     for (;j != -1;j--, tmp = tmp->prev)
194         list[j] = tmp;
195 }
196 
197 void get_Ans(Stack_manager *const s, char operation)
198 {
199     assert(s->top != NULL || s->top->prev != NULL);
200     int tmp1 = s->top->num, tmp2 = s->top->prev->num, ans;
201     if (operation == '+')
202         ans = tmp1 + tmp2;
203     else if (operation == '-')
204         ans = tmp2 - tmp1;
205     else if (operation == '*')
206         ans = tmp1*tmp2;
207     else if (operation == '/')
208         ans = tmp2 / tmp1;
209     //连续pop两次，把tmp1和tmp2弹出去
210     pop_out(s); pop_out(s);
211     //把答案压栈
212     push_in_int(s, ans);
213 }
214 
215 void print_list(Stack **const list, int const node_sum, FILE *fp)
216 {
217     int i;
218     fprintf(fp,"Suffix expression: ");
219     for (i = 0;i < node_sum;i++)
220     {
221         if (list[i]->type == is_sym)
222             fprintf(fp, "%c ", list[i]->sym);
223         else
224             fprintf(fp, "%d ", list[i]->num);
225     }
226     fprintf(fp,"
");
227 }
228 
229 void caculate_Infix(Stack **const suffix_list, int const node_sum, FILE *fp)
230 {
231     int i;
232     Stack_manager *stack_man = allcoate_stack_man();
233     for (i = 0;i < node_sum;i++)
234     {
235         if (suffix_list[i]->type == is_int)
236             push_in_int(stack_man, suffix_list[i]->num);
237         else if (suffix_list[i]->type == is_sym)
238             get_Ans(stack_man, suffix_list[i]->sym);
239     }
240     fprintf(fp, "           Answer: %d
", stack_man->top->num);
241     
242     delete_stack(&stack_man);
243 }
244 
245 void error(Stack_manager *s1, Stack_manager *s2, Stack_manager *s3, Stack**L,FILE *fp)
246 {
247     fprintf(fp, "< illegal expression! >
");
248     delete_stack(&s1);
249     delete_stack(&s2);
250     delete_stack(&s3);
251     free(L);
252 }

 1 //plug.h
 2 
 3 #ifndef Suffix_to_Infix
 4 #define Suffix_to_Infix
 5 #define MAX 256
 6 #include <stdio.h>
 7 
 8 enum symbol_or_interget { is_sym, is_int };
 9 
10 typedef struct _stack
11 {
12     char sym;
13     int num, type;
14     struct _stack *prev;
15 }Stack;
16 
17 typedef struct _stack_manager
18 {
19     int node_sum;
20     struct _stack *top;
21 }Stack_manager;
22 
23 void push_in_int(Stack_manager *const, const int);
24 void push_in_char(Stack_manager *const, const char);
25 void pop_out(Stack_manager *const);
26 int scan_Infix_to_Suffix(char *,FILE *);
27 int combine_Stack_to_Num(Stack_manager *const);
28 void copy_Stack_to_List(Stack **const, Stack_manager *const);
29 void caculate_Infix(Stack **const, int const, FILE *);
30 void get_Ans(Stack_manager *const, char);
31 void print_list(Stack **const,int const, FILE *);
32 void error(Stack_manager *, Stack_manager *, Stack_manager *, Stack**, FILE *fp);
33 
34 #endif // !Suffix_to_Infix

 1 //stack.cpp
 2 
 3 #include "plug.h"
 4 #include "stack.h"
 5 #include <stdio.h>
 6 #include <stdlib.h>
 7 
 8 Stack_manager *allcoate_stack_man(void)
 9 {
10     Stack_manager *stack_man = (Stack_manager *)malloc(sizeof(Stack_manager));
11     stack_man->top = NULL, stack_man->node_sum = 0;
12     return stack_man;
13 }
14 
15 void push_in_int(Stack_manager *const s_head, const int item)
16 {
17     Stack *tmp = NULL;
18     
19     tmp = (Stack *)malloc(sizeof(Stack));
20     
21     tmp->prev = s_head->top;
22     tmp->num = item, tmp->sym = '';
23     tmp->type = is_int;
24 
25     s_head->node_sum++;
26     s_head->top = tmp;
27 }
28 
29 void push_in_char(Stack_manager *const s_head, const char item)
30 {
31     Stack *tmp = NULL;
32 
33     tmp = (Stack *)malloc(sizeof(Stack));
34 
35     tmp->prev = s_head->top;
36     tmp->sym = item, tmp->num = 0;
37     tmp->type = is_sym;
38 
39     s_head->node_sum++;
40     s_head->top = tmp;
41 }
42 
43 void pop_out(Stack_manager *const s)
44 {
45     Stack *tmp = s->top->prev;
46     s->node_sum--;
47     free(s->top);
48     s->top = tmp;
49 }
50 
51 void delete_stack(Stack_manager **stack_man)
52 {
53     for (;(*stack_man)->top != NULL;)
54         pop_out(*stack_man);
55     free(*stack_man);
56     *stack_man = NULL;
57 }
58 
59 void print_stack(Stack_manager *const s)
60 {
61     Stack *tmp = s->top;
62     for (;tmp != NULL;tmp = tmp->prev)
63     {
64         if (tmp->type == is_sym)
65             printf("%c ", tmp->sym);
66         else
67             printf("%d ", tmp->num);
68     }
69     printf("
");
70 }

 1 //stack.h
 2 
 3 #ifndef STACK
 4 #define STACK
 5 
 6 void push_in_int(Stack_manager *const, const int);
 7 void push_in_char(Stack_manager *const, const char);
 8 void pop_out(Stack_manager *const);
 9 Stack_manager *allcoate_stack_man(void);
10 void delete_stack(Stack_manager **);
11 void print_stack(Stack_manager *const);
12 
13 #endif // !STACK