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] = { ‘\0‘ }; 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\n", symnum); 24         error_exp += scan_Infix_to_Suffix(symnum, fp_out); 25         fprintf(fp_out, "\n"); 26     } 27     fprintf(fp_out, "\nSum of error expression: %d\n", 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]!=‘\0‘;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 == 0100                 || 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->top107                 || sym_man->top->sym == ‘*‘ || sym_man->top->sym == ‘/‘108                 || sym_man->top->sym == ‘(‘)//符号为‘(‘的情况合并到这里了109             {110                 for (;sym_man->top != NULL111                     && 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//其他情况均为不合法的情况，out143         {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         else183             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         else224             fprintf(fp, "%d ", list[i]->num);225     }226     fprintf(fp,"\n");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\n", 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! >\n");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 _stack11 {12     char sym;13     int num, type;14     struct _stack *prev;15 }Stack;16 17 typedef struct _stack_manager18 {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 = ‘\0‘;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         else67             printf("%d ", tmp->num);68     }69     printf("\n");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