下推栈中缀-后缀表达式转换后缀表达式求值数组与链表实现-白红宇

下推栈中缀-后缀表达式转换后缀表达式求值数组与链表实现

阅读量：4963 次

发布时间：2019-06-12

本文共 4539 字，大约阅读时间需要 15 分钟。

Item.h (自定义类型) :

1 typedef double Item;

STACK.h (下推栈接口) :

1 #include "Item.h"2 3 bool STACKerror(int i);4 void STACKinit(int);5 int STACKempty(void);6 void STACKpush(Item);7 Item STACKpop(void);

STACK.c (接口源代码_数组实现) :

1 #include "STACK.h" 2 #include 
     
       3  4 static Item *s; 5 static int N,N1; 6  7 bool STACKerror(int i) 8 { 9     if(i)10         return N
      
       0 ?true:false;14 }15 void STACKinit(int maxN)16 {17     s=malloc(maxN*sizeof(Item));18     N=0;19     N1=maxN;20 }21 int STACKempty(void)22 {23     return N;24 }25 void STACKpush(Item item)26 {27     if(STACKerror(1))28         s[N++]=item;29     else30         printf("\nSTACKpush false");31 }32 Item STACKpop(void)33 {34     if(STACKerror(0))35         return s[--N];36     else37         printf("\nSTACKpop false");38     return -1;39 }

STACK.c (接口源代码_链表实现) :

1 #include "STACK.h" 2 #include 
     
       3  4 typedef struct STACKnode *link; 5 struct STACKnode 6 { 7     Item item; 8     link next; 9 };10 11 static link head;12 static int N=0,N1;13 14 bool STACKerror(int i)15 {16     if(i)17         return N
      
       0 ?true:false;21 }22 link NEW(Item item, link next)23 {24     link x = malloc(sizeof *x);25     x->item=item; x->next=next;26     return x;27 }28 void STACKinit(int maxN)29 {30     N1=maxN;31     head=NULL;32 }33 int STACKempty(void)34 {35     return N;36 }37 void STACKpush(Item item)38 {39     if(STACKerror(1))40     {41         head=NEW(item, head);42         N++;43     }44     else45         printf("\nSTACKpush false");46 }47 Item STACKpop(void)48 {49     if(STACKerror(0))50     {51         Item item=head->item;52         link t=head->next;53         free(head);head=t;54         N--;55         return item;56     }57     else58         printf("\nSTACKpop false");59     return -1;60 }

STACK.c (接口源代码_双向链表实现) :

1 #include
     
       2 #include "STACK.h" 3  4 typedef struct node * link; 5 struct node 6 { 7     Item item; 8     link next,last;  9 };10 11 static link head,last;12 static int N=0,N1=0;13 14 link NEW(Item item, link last)15 {16     link x=malloc(sizeof (link));17     x->item=item;18     //x->next=head;19     x->next=NULL;20     x->last=last;21     return x;22 }23 static short STACKerror(short i)24 {25     if(i)26     {27         if(N
      
       0)35             return 1;36         printf("\nSTACKpop false !\n");37         exit(1);38     }39 }40 void STACKinit(int maxN)41 {42     last=head=NULL;43     N1=maxN;44 }45 void STACKpush(Item item)46 {47     if(STACKerror(1))48     {49         head=NEW(item, last);50         last=head;51         N++;52     }53 }54 Item STACKpop(void)55 {56     if(STACKerror(0))57     {58         Item i=head->item;59         link x=head;60         head=head->last;61         last=head;62         free(x);63         N--;64         return i;65     }66 }67 int STACKempty(void)68 {69     return N;70 }

main.c (主程序_打印中缀-后缀表达式) :

1 #include 
     
       2 #include 
      
        3 #include "STACK.h" 4  5 int main(void) 6 { 7     char a[20]; 8     double temp; 9     10     scanf("%s",a);11     getchar();12     13     int N=strlen(a);14     STACKinit(N);15     16     for(int i=0; i
       
        ='0')&&(a[i]<='9'))27         {28             printf("%c ",a[i]);29         }30     }31     putchar('\n');32     33     return 0;34 }

测试结果：

main.c (主程序_后缀表达式求值) :

1 #include 
     
       2 #include 
      
        3 #include "STACK.h" 4  5 int main(void) 6 { 7     char a[20]; 8     double temp; 9     10     scanf("%s",a);11     getchar();12     13     int N=strlen(a);14     STACKinit(N);15     for(int i=0; i
       
        ='0')&&(a[i]<='9'))18             STACKpush(a[i]-'0');19         else if(a[i]=='+')20         {21             //STACKpush(STACKpop()+STACKpop());22             temp=STACKpop();23             STACKpush(STACKpop()+temp); 24         }25         else if(a[i]=='*')26         {27             //STACKpush(STACKpop()*STACKpop());28             temp=STACKpop();29             STACKpush(STACKpop()*temp);30         }31         else if(a[i]=='/')32         {33             temp=STACKpop();34             STACKpush(STACKpop()/temp);35         }36         else if(a[i]=='-')37         {38             temp=STACKpop();39             STACKpush(STACKpop()-temp);40         }41         //while((a[i]>='0')&&(a[i]<='9'))42             //STACKpush(10*STACKpop()+(a[i++]-'0'));43     }44     printf("%f \n", STACKpop());45     return 0;46 }

测试结果：