stack.h
#ifndef _Stack_H #define _Stack_H #define symbolsize 10 struct Node; typedef char *ElementType; typedef struct Node *PtrToNode; typedef PtrToNode Stack; int IsEmpty(Stack S); Stack CreateStack(void); void MakeEmpty(Stack S); void Push(ElementType X,Stack S); ElementType Top(Stack S); void Pop(Stack S); #endifstack.c
#include <string.h> #include <stdio.h> #include <stdlib.h> #include "stack.h" struct Node { ElementType Element; PtrToNode Next; }; static void FatalError(char *S); static void Error(char *S); static void FatalError(char *S) { fputs(S,stderr); exit(EXIT_FAILURE); } static void Error(char *S) { fputs(S,stderr); } int IsEmpty(Stack S) { return S->Next==NULL; } Stack CreateStack(void) { Stack S; S=malloc(sizeof(struct Node)); if(S==NULL) FatalError("Out of space!"); S->Element=malloc(sizeof(char)*symbolsize); if(S->Element==NULL) FatalError("Out of space!"); S->Next=NULL; MakeEmpty(S); return S; } void MakeEmpty(Stack S) { if(S==NULL) Error("Must usr CreateStack first."); else while(!IsEmpty(S)) Pop(S); } void Push(ElementType X,Stack S) { PtrToNode Tmp; Tmp=malloc(sizeof(struct Node)); if(Tmp==NULL) FatalError("Out of space!"); Tmp->Element=malloc(sizeof(char)*symbolsize); if(Tmp->Element==NULL) FatalError("Out of space!"); strcpy(Tmp->Element,X); Tmp->Next=S->Next; S->Next=Tmp; } ElementType Top(Stack S) { if(!IsEmpty(S)) return S->Next->Element; Error("Empty stack!"); return 0; } void Pop(Stack S) { PtrToNode P; if(IsEmpty(S)) Error("Empty stack!"); else { P=S->Next; S->Next=S->Next->Next; free(P->Element); free(P); } }test.c
#include <stdio.h> #include <string.h> #include <stdlib.h> #include "stack.h" int main(void) { FILE *fp; Stack S; char string[symbolsize],string_tmp[symbolsize]; S=CreateStack(); fp=fopen("text","r"); while(fscanf(fp,"%s",string)!=EOF) { if(strcmp(string,"begin")==0||strcmp(string,"(")==0||strcmp(string,"[")==0||strcmp(string,"{")==0||strcmp(string,"/*")==0) Push(string,S); else if(strcmp(string,"end")==0||strcmp(string,"*/")==0||strcmp(string,")")==0||strcmp(string,"]")==0||strcmp(string,"}")==0) { if(IsEmpty(S)) { puts("Empty stack!Error symbol!"); exit(EXIT_FAILURE); } strcpy(string_tmp,Top(S)); if(strcmp(string_tmp,"begin")==0) strcpy(string_tmp,"end"); if(strcmp(string_tmp,"(")==0) strcpy(string_tmp,")"); if(strcmp(string_tmp,"/*")==0) strcpy(string_tmp,"*/"); if(strcmp(string_tmp,"[")==0) strcpy(string_tmp,"]"); if(strcmp(string_tmp,"{")==0) strcpy(string_tmp,"}"); if(strcmp(string,string_tmp)==0) Pop(S); else { puts("Symbol is not matched!Error!"); exit(EXIT_FAILURE); } } else break; } if(!IsEmpty(S)) { puts("File scan done!Symbol is not matched!"); exit(EXIT_FAILURE); } puts("Check over!Symbol matched!"); fclose(fp); return 0; }stack.h
#ifndef _Stack_H #define _Stack_H #define NumberLength 10 struct Node; typedef char *ElementType; typedef struct Node *PtrToNode; typedef PtrToNode Stack; int IsEmpty(Stack S); Stack CreateStack(void); void MakeEmpty(Stack S); void Push(ElementType X,Stack S); ElementType Top(Stack S); void Pop(Stack S); #endifstack.c
#include <string.h> #include <stdio.h> #include <stdlib.h> #include "stack.h" struct Node { ElementType Element; PtrToNode Next; }; static void FatalError(char *S); static void Error(char *S); static void FatalError(char *S) { fputs(S,stderr); exit(EXIT_FAILURE); } static void Error(char *S) { fputs(S,stderr); } int IsEmpty(Stack S) { return S->Next==NULL; } Stack CreateStack(void) { Stack S; S=malloc(sizeof(struct Node)); if(S==NULL) FatalError("Out of space!"); S->Element=malloc(sizeof(char)*NumberLength); if(S->Element==NULL) FatalError("Out of space!"); S->Next=NULL; MakeEmpty(S); return S; } void MakeEmpty(Stack S) { if(S==NULL) Error("Must usr CreateStack first."); else while(!IsEmpty(S)) Pop(S); } void Push(ElementType X,Stack S) { PtrToNode Tmp; Tmp=malloc(sizeof(struct Node)); if(Tmp==NULL) FatalError("Out of space!"); Tmp->Element=malloc(sizeof(char)*NumberLength); if(Tmp->Element==NULL) FatalError("Out of space!"); strcpy(Tmp->Element,X); Tmp->Next=S->Next; S->Next=Tmp; } ElementType Top(Stack S) { if(!IsEmpty(S)) return S->Next->Element; Error("Empty stack!"); return 0; } void Pop(Stack S) { PtrToNode P; if(IsEmpty(S)) Error("Empty stack!"); else { P=S->Next; S->Next=S->Next->Next; free(P->Element); free(P); } }calculate.c
#include <stdio.h> #include <string.h> #include <stdlib.h> #include "stack.h" /*assume between the two numbers is a blank*/ int main(void) { int result,factor1,factor2; char string[NumberLength],string_1[NumberLength],string_2[NumberLength]; Stack S; S=CreateStack(); while(fscanf(stdin,"%s",string)!=EOF) { if(strcmp(string,"+")==0||strcmp(string,"-")==0||strcmp(string,"*")==0||strcmp(string,"/")==0||strcmp(string,"%")==0) { strcpy(string_1,Top(S)); Pop(S); strcpy(string_2,Top(S)); Pop(S); factor1=atoi(string_1); factor2=atoi(string_2); if(strcmp(string,"+")==0) result=factor2+factor1; if(strcmp(string,"-")==0) result=factor2-factor1; if(strcmp(string,"*")==0) result=factor2*factor1; if(strcmp(string,"/")==0) result=factor2/factor1; if(strcmp(string,"%")==0) result=factor2%factor1; sprintf(string,"%d",result); Push(string,S); } else { Push(string,S); } } strcpy(string,Top(S)); printf("%s\n",string); return 0; }a. stack.h
#ifndef _Stack_H #define _Stack_H struct Node; typedef char ElementType; typedef struct Node *PtrToNode; typedef PtrToNode Stack; int IsEmpty(Stack S); Stack CreateStack(void); void MakeEmpty(Stack S); void Push(ElementType X,Stack S); ElementType Top(Stack S); void Pop(Stack S); #endifstack.c
#include <stdio.h> #include <stdlib.h> #include "stack.h" struct Node { ElementType Element; PtrToNode Next; }; static void FatalError(char *S); static void Error(char *S); static void FatalError(char *S) { fputs(S,stderr); exit(EXIT_FAILURE); } static void Error(char *S) { fputs(S,stderr); } int IsEmpty(Stack S) { return S->Next==NULL; } Stack CreateStack(void) { Stack S; S=malloc(sizeof(struct Node)); if(S==NULL) FatalError("Out of space!"); S->Next=NULL; MakeEmpty(S); return S; } void MakeEmpty(Stack S) { if(S==NULL) Error("Must usr CreateStack first."); else while(!IsEmpty(S)) Pop(S); } void Push(ElementType X,Stack S) { PtrToNode Tmp; Tmp=malloc(sizeof(struct Node)); if(Tmp==NULL) FatalError("Out of space!"); Tmp->Element=X; Tmp->Next=S->Next; S->Next=Tmp; } ElementType Top(Stack S) { if(!IsEmpty(S)) return S->Next->Element; Error("Empty stack!"); return 0; } void Pop(Stack S) { PtrToNode P; if(IsEmpty(S)) Error("Empty stack!"); else { P=S->Next; S->Next=S->Next->Next; free(P); } }trans.h
#ifndef _Trans_H #define _Trans_H int IsOperator(char ch); int Compare(char ch1,char ch2); void Warn(char *S); int Equal(char ch1,char ch2); #endiftrans.c
#include <stdlib.h> #include <stdio.h> #include "trans.h" int IsOperator(char ch) { return ch=='+'?1:ch=='-'?1:ch=='*'?1:ch=='/'?1:ch=='('?1:ch==')'?1:0; } int Compare(char ch1,char ch2) { ch1=ch1=='+'?1:ch1=='-'?1:ch1=='*'?2:ch1=='/'?2:ch1=='('?3:ch1==')'?3:0; ch2=ch2=='+'?1:ch2=='-'?1:ch2=='*'?2:ch2=='/'?2:ch2=='('?3:ch2==')'?3:0; if(ch1>=ch2) return 1; else return -1; } void Warn(char *S) { fputs(S,stderr); putchar('\n'); exit(EXIT_FAILURE); } int Equal(char ch1,char ch2) { if(ch1==ch2) return 1; else return 0; }test.c
#include <stdio.h> #include "stack.h" #include "trans.h" int main(void) { Stack S; char Ch,Tmp; S=CreateStack(); while((Ch=getchar())!=EOF&&Ch!='\n') { if(!IsOperator(Ch)) putchar(Ch); else { if(IsEmpty(S)) { if(Equal(Ch,')')==1) Warn("Expression wrong!"); else Push(Ch,S); } else { if(Equal(Ch,')')==1) { Tmp=Top(S); while(Equal(Tmp,'(')!=1) { printf("%c",Tmp); Pop(S); Tmp=Top(S); } Pop(S); } else { Tmp=Top(S); while(Compare(Tmp,Ch)==1&&Equal(Tmp,'(')!=1) { printf("%c",Tmp); Pop(S); if(IsEmpty(S)) break; else Tmp=Top(S); } Push(Ch,S); } } } } while(!IsEmpty(S)) { Tmp=Top(S); printf("%c",Tmp); Pop(S); } putchar('\n'); return 0; }c. stack.h
#ifndef _Stack_H #define _Stack_H #define NumberLength 50 struct Node; typedef char *ElementType; typedef struct Node *PtrToNode; typedef PtrToNode Stack; int IsEmpty(Stack S); Stack CreateStack(void); void MakeEmpty(Stack S); void Push(ElementType X,Stack S); ElementType Top(Stack S); void Pop(Stack S); #endifstack.c
#include <string.h> #include <stdio.h> #include <stdlib.h> #include "stack.h" struct Node { ElementType Element; PtrToNode Next; }; static void FatalError(char *S); static void Error(char *S); static void FatalError(char *S) { fputs(S,stderr); exit(EXIT_FAILURE); } static void Error(char *S) { fputs(S,stderr); } int IsEmpty(Stack S) { return S->Next==NULL; } Stack CreateStack(void) { Stack S; S=malloc(sizeof(struct Node)); if(S==NULL) FatalError("Out of space!"); S->Element=malloc(sizeof(char)*NumberLength); if(S->Element==NULL) FatalError("Out of space!"); S->Next=NULL; MakeEmpty(S); return S; } void MakeEmpty(Stack S) { if(S==NULL) Error("Must usr CreateStack first."); else while(!IsEmpty(S)) Pop(S); } void Push(ElementType X,Stack S) { PtrToNode Tmp; Tmp=malloc(sizeof(struct Node)); if(Tmp==NULL) FatalError("Out of space!"); Tmp->Element=malloc(sizeof(char)*NumberLength); if(Tmp->Element==NULL) FatalError("Out of space!"); strcpy(Tmp->Element,X); Tmp->Next=S->Next; S->Next=Tmp; } ElementType Top(Stack S) { if(!IsEmpty(S)) return S->Next->Element; Error("Empty stack!"); return 0; } void Pop(Stack S) { PtrToNode P; if(IsEmpty(S)) Error("Empty stack!"); else { P=S->Next; S->Next=S->Next->Next; free(P->Element); free(P); } }calculate.c
#include <stdio.h> #include <string.h> #include <stdlib.h> #include "stack.h" /*从3.19的答案复制过来修改的，懒得判断是否要加括号了*/ /*assume between the two numbers is a blank*/ int main(void) { int result,factor1,factor2; char string[NumberLength],string_1[NumberLength],string_2[NumberLength],symbolleft[NumberLength],symbolright[NumberLength]; Stack S; S=CreateStack(); while(fscanf(stdin,"%s",string)!=EOF) { strcpy(symbolleft,"("); strcpy(symbolright,")"); if(strcmp(string,"+")==0||strcmp(string,"-")==0||strcmp(string,"*")==0||strcmp(string,"/")==0||strcmp(string,"%")==0) { strcpy(string_1,Top(S)); Pop(S); strcpy(string_2,Top(S)); Pop(S); strcpy(string_2,strcat(symbolleft,string_2)); strcat(string_2,string); strcat(string_2,string_1); strcat(string_2,symbolright); Push(string_2,S); } else { Push(string,S); } } strcpy(string,Top(S)); printf("%s\n",string); return 0; }stack.h
#ifndef _Stack_H #define _Stack_H struct StackRecord; typedef struct StackRecord *Stack; typedef int ElementType; int IsEmpty(Stack S); int IsFull(Stack S1,Stack S2); void CreateStack(Stack *S1,Stack *S2); void MakeEmpty(Stack S); void Push(ElementType X,Stack S1,Stack S2); ElementType Top(Stack S); void Pop(Stack S); #endifstack.c
#include <stdio.h> #include <stdlib.h> #include "stack.h" #define ArraySize (5) #define EmptyToLeftS (-1) #define EmptyToRightS (ArraySize) static void Error(char *S); static void FatalError(char *S); static void Error(char *S) { fputs(S,stderr); putchar('\n'); } static void FatalError(char *S) { fputs(S,stderr); putchar('\n'); exit(EXIT_FAILURE); } struct StackRecord { int Which; int TopOfStack; ElementType *Array; }; int IsEmpty(Stack S) { if(S->Which==0) return S->TopOfStack==EmptyToLeftS; else return S->TopOfStack==EmptyToRightS; } int IsFull(Stack S1,Stack S2) { if(S1->Which==0) return S1->TopOfStack+1==S2->TopOfStack; else return S2->TopOfStack+1==S1->TopOfStack; } void CreateStack(Stack *S1,Stack *S2) { if(ArraySize<=0) Error("Stack is too small!"); *S1=(Stack)malloc(sizeof(struct StackRecord)); *S2=(Stack)malloc(sizeof(struct StackRecord)); if(*S1==NULL||*S2==NULL) FatalError("Out of space!"); (*S2)->Array=(*S1)->Array=malloc(sizeof(ElementType)*ArraySize); if((*S1)->Array==NULL||(*S2)->Array==NULL) FatalError("Out of space!"); (*S1)->Which=0; (*S2)->Which=1; MakeEmpty(*S1); MakeEmpty(*S2); } void MakeEmpty(Stack S) { if(S->Which==0) S->TopOfStack=EmptyToLeftS; else S->TopOfStack=EmptyToRightS; } void Push(ElementType X,Stack S1,Stack S2) //S2在这里仅用来判断栈满 { if(IsFull(S1,S2)) Error("Stack is full!"); else { if(S1->Which==0) S1->Array[++S1->TopOfStack]=X; else S1->Array[--S1->TopOfStack]=X; } } ElementType Top(Stack S) { if(!IsEmpty(S)) return S->Array[S->TopOfStack]; Error("Empty stack!"); return 0; } void Pop(Stack S) { if(IsEmpty(S)) Error("Empty stack!"); else { if(S->Which==0) S->TopOfStack--; else S->TopOfStack++; } }ceshi.c
#include <stdio.h> #include "stack.h" int main(void) { ElementType I; char ch; Stack St1,St2; CreateStack(&St1,&St2); puts("Enter integer to test stack(q to avoid):"); while(scanf("%d",&I)==1) { Push(I,St2,St1); puts("Continue(q to quit):"); } puts("Stack push done!"); while(getchar()!='\n') continue; fputs("Do you want to Pop(y/n)",stdout); while((ch=getchar())!='n') { if(ch=='y') { printf("Pop the element %d\n",Top(St2)); Pop(St2); fputs("Pop(y/n):",stdout); } else puts("Not effect operation(y/n)."); while(getchar()!='\n') continue; } return 0; }a. queue.h
#ifndef _Queue_H #define _Queue_H typedef int ElementType; struct QueueRecord; typedef struct QueueRecord *Queue; typedef struct QueueRecord *Position; int IsEmpty(Queue Q); Queue CreateQueue(void); void DisposeQueue(Queue Q); void MakeEmpty(Queue Q); void Enqueue(ElementType X,Queue Q); ElementType Front(Queue Q); void Dequeue(Queue Q); ElementType FrontAndDequeue(Queue Q); #endifqueue.c
#include <stdio.h> #include <stdlib.h> #include "queue.h" struct QueueRecord { int Size; Position Pre; Position Next; ElementType Element; }; static Position MakeNode(ElementType X); static void FatalError(char *str); static Position MakeNode(ElementType X) { Position Node; Node=malloc(sizeof(struct QueueRecord)); if(Node==NULL) FatalError("Not Enough Memory to create node!"); Node->Element=X; return Node; } static void FatalError(char *str) { fputs(str,stderr); putchar('\n'); exit(EXIT_FAILURE); } int IsEmpty(Queue Q) { return Q->Size==0; } Queue CreateQueue(void) { Queue Q; Q=malloc(sizeof(struct QueueRecord)); if(Q==NULL) FatalError("Not enough memory!"); Q->Size=0; Q->Pre=NULL; Q->Next=NULL; return Q; } void DisposeQueue(Queue Q) { while(!IsEmpty(Q)) Dequeue(Q); free(Q); } void MakeEmpty(Queue Q) { while(!IsEmpty(Q)) Dequeue(Q); } void Enqueue(ElementType X,Queue Q) { Position P; P=MakeNode(X); if(IsEmpty(Q)) { P->Pre=Q->Pre; P->Next=Q->Next; Q->Next=P; Q->Pre=P; Q->Size++; } else { Q->Next->Next=P; P->Pre=Q->Next; Q->Next=P; P->Next=NULL; Q->Size++; } } ElementType Front(Queue Q) { if(IsEmpty(Q)) puts("Queue is empty!"); else return Q->Pre->Element; } void Dequeue(Queue Q) { Position Temp; if(IsEmpty(Q)) puts("Queue is empty!"); else if(Q->Size==1) { Temp=Q->Pre; Q->Pre=NULL; Q->Next=NULL; Q->Size--; free(Temp); } else { Temp=Q->Pre; Q->Pre=Q->Pre->Next; Temp->Next->Pre=NULL; free(Temp); Q->Size--; } } ElementType FrontAndDequeue(Queue Q) { ElementType result; Position Temp; if(IsEmpty(Q)) puts("Queue is empty!"); else if(Q->Size==1) { Temp=Q->Pre; Q->Pre=NULL; Q->Next=NULL; Q->Size--; result=Temp->Element; free(Temp); return result; } else { Temp=Q->Pre; Q->Pre=Q->Pre->Next; Temp->Next->Pre=NULL; Q->Size--; result=Temp->Element; free(Temp); return result; } }b. queue.h
#ifndef _Queue_H #define _Queue_H struct QueueRecord; typedef struct QueueRecord *Queue; typedef int ElementType; int IsEmpty(Queue Q); int IsFull(Queue Q); Queue CreateQueue(int MaxElements); void DisposeQueue(Queue Q); void MakeEmpty(Queue Q); void Enqueue(ElementType X,Queue Q); ElementType Front(Queue Q); void Dequeue(Queue Q); ElementType FrontAndDequeue(Queue Q); #endifqueue.c
#include <stdio.h> #include <stdlib.h> #include "queue.h" struct QueueRecord { int Capacity; int Front; int Rear; int Size; ElementType *Array; }; static void FatalError(char *S); static void Error(char *S); static int Circle(int Value,Queue Q); static int Circle(int Value,Queue Q) { if(++Value==Q->Capacity) Value=0; return Value; } static void FatalError(char *S) { fputs(S,stderr); putchar('\n'); exit(EXIT_FAILURE); } static void Error(char *S) { fputs(S,stderr); putchar('\n'); } int IsEmpty(Queue Q) { return Q->Size==0; } int IsFull(Queue Q) { return Q->Size==Q->Capacity; } Queue CreateQueue(int MaxElements) { Queue Q; Q=malloc(sizeof(struct QueueRecord)); if(Q==NULL) FatalError("Out of space!"); Q->Array=malloc(sizeof(ElementType)*MaxElements); if(Q->Array==NULL) FatalError("Out of space!"); Q->Capacity=MaxElements; MakeEmpty(Q); return Q; } void DisposeQueue(Queue Q) { if(Q!=NULL) { free(Q->Array); free(Q); } } void MakeEmpty(Queue Q) { Q->Size=0; Q->Front=1; Q->Rear=0; } void Enqueue(ElementType X,Queue Q) { if(IsFull(Q)) Error("Full queue!"); else { Q->Size+=1; Q->Rear=Circle(Q->Rear,Q); Q->Array[Q->Rear]=X; } } ElementType Front(Queue Q) { return Q->Array[Q->Front]; } void Dequeue(Queue Q) { if(IsEmpty(Q)) Error("Empty queue!"); else { Q->Size--; Q->Front=Circle(Q->Front,Q); } } ElementType FrontAndDequeue(Queue Q) { ElementType Tmp; if(IsEmpty(Q)) Error("Empty queue!"); else { Tmp=Q->Array[Q->Front]; Q->Size--; Q->Front=Circle(Q->Front,Q); return Tmp; } }deque.h
#ifndef _Deque_H #define _Deque_H struct DequeNode; typedef struct DequeNode *Position; struct Header; typedef struct Header *Deque; typedef int ElementType; int IsEmpty(Deque Q); Deque CreateDeque(void); void Push(ElementType X,Deque Q); ElementType Top(Deque Q); void Pop(Deque Q); void Inject(ElementType X,Deque Q); ElementType Front(Deque Q); void Eject(Deque Q); #endifdeque.c
#include <stdio.h> #include <stdlib.h> #include "deque.h" struct DequeNode { ElementType Element; Position Pre; Position Next; }; struct Header { Position Front; Position End; }; static void FatalError(char *str); static Position MakeNode(ElementType X); static void FatalError(char *str) { fputs(str,stderr); putchar('\n'); exit(EXIT_FAILURE); } static Position MakeNode(ElementType X) { Position Node; Node=malloc(sizeof(struct DequeNode)); if(Node==NULL) FatalError("Not enough memory to create node!"); Node->Element=X; Node->Pre=NULL; Node->Next=NULL; return Node; } int IsEmpty(Deque Q) { return Q->Front==NULL||Q->End==NULL; } Deque CreateDeque(void) { Deque Q; Q=malloc(sizeof(struct Header)); if(Q==NULL) FatalError("Not enough memory!"); Q->Front=NULL; Q->End=NULL; } void Push(ElementType X,Deque Q) { Position P; P=MakeNode(X); if(IsEmpty(Q)) { Q->Front=P; Q->End=P; } else { P->Next=Q->Front; Q->Front->Pre=P; Q->Front=P; } } ElementType Top(Deque Q) { if(IsEmpty(Q)) puts("Deque is empty!"); else return Q->Front->Element; } void Pop(Deque Q) { Position Temp; if(IsEmpty(Q)) puts("Deque is empty!Can't Pop!"); else { Temp=Q->Front; Q->Front=Temp->Next; if(IsEmpty(Q)) Q->End=NULL; else Temp->Next->Pre=NULL; free(Temp); } } void Inject(ElementType X,Deque Q) { Position P; P=MakeNode(X); if(IsEmpty(Q)) { Q->Front=P; Q->End=P; } else { Q->End->Next=P; P->Pre=Q->End; Q->End=P; } } ElementType Front(Deque Q) { if(IsEmpty(Q)) puts("Deque is empty!"); else return Q->End->Element; } void Eject(Deque Q) { Position Temp; if(IsEmpty(Q)) puts("Deque is empty!Can't Ejetct!"); else { Temp=Q->End; Q->End=Temp->Pre; if(IsEmpty(Q)) Q->Front=NULL; else Temp->Pre->Next=NULL; free(Temp); } }