C语言中栈和队列实现表达式求值的实例
C语言中栈和队列实现表达式求值的实例
实现代码：
#include#include #defineOK1 #defineERROR0 #defineSTACK_SIZE20 #defineSTACK_INCREMENT10 #defineQUEUE_SIZE20 typedefintStatus; typedefcharStackElemtype; typedefstructStack{ StackElemtype*base; StackElemtype*top; intstackSize; }Stack; StatusStackInit(Stack*s){ s->base=(StackElemtype*)malloc(sizeof(StackElemtype)*STACK_SIZE); if(!s->base) returnERROR; s->top=s->base; s->stackSize=STACK_SIZE; returnOK; } StatusPop(Stack*s,StackElemtype*value){ if(s->base==s->top){ printf("\nstackempty\n"); returnERROR; } *value=*(--(s->top)); returnOK; } StatusPush(Stack*s,StackElemtypevalue){ if(s->top-s->base==s->stackSize){ s->base=(StackElemtype*)realloc(s->base,sizeof(StackElemtype)*(STACK_INCREMENT+STACK_SIZE)); if(!s->base) returnERROR; s->top=s->base+STACK_SIZE; s->stackSize=STACK_SIZE+STACK_INCREMENT; } *(s->top)=value; s->top++; returnOK; } intStackLength(Stacks){ returns.top-s.base; } typedefdoubleStackElemtype_ForValueExperssion; typedefstructStack_2{ StackElemtype_ForValueExperssion*base; StackElemtype_ForValueExperssion*top; intstackSize; }Stack_2; StatusStackInit_2(Stack_2*s){ s->base=(StackElemtype_ForValueExperssion*)malloc(sizeof(StackElemtype_ForValueExperssion)*STACK_SIZE); if(!s->base) returnERROR; s->top=s->base; s->stackSize=STACK_SIZE; returnOK; } StatusPop_2(Stack_2*s,StackElemtype_ForValueExperssion*value){ if(s->base==s->top){ printf("\nstackempty\n"); returnERROR; } *value=*(--(s->top)); returnOK; } StatusPush_2(Stack_2*s,StackElemtype_ForValueExperssionvalue){ if(s->top-s->base==s->stackSize){ s->base=(StackElemtype_ForValueExperssion*)realloc(s->base,sizeof(StackElemtype_ForValueExperssion)*(STACK_INCREMENT+STACK_SIZE)); if(!s->base) returnERROR; s->top=s->base+STACK_SIZE; s->stackSize=STACK_SIZE+STACK_INCREMENT; } *(s->top)=value; s->top++; returnOK; } typedefdoubleQueueElemtype; typedefcharQueueOperatorValue; typedefstructQueueNode{ QueueElemtypedata; QueueOperatorValueoperator; structQueueNode*next; intflag; }QueueNode,*QueueNodePtr; typedefstructQueue{ QueueNodePtrfront; QueueNodePtrrear; }Queue; StatusQueueInit(Queue*q){ q->front=(QueueNodePtr)malloc(sizeof(QueueNode)); if(!q->front) returnERROR; q->rear=q->front; q->rear->next=NULL; returnOK; } StatusQueueInsert(Queue*q,QueueElemtypevalue){ QueueNodePtrnew; new=(QueueNodePtr)malloc(sizeof(QueueNode)); if(!new) returnERROR; new->data=value; new->flag=1; new->next=NULL; q->rear->next=new; q->rear=new; returnOK; } StatusQueueInsert_operatorValue(Queue*q,QueueOperatorValuevalue){ QueueNodePtrnew; new=(QueueNodePtr)malloc(sizeof(QueueNode)); if(!new) returnERROR; new->operator=value; new->flag=0; new->next=NULL; q->rear->next=new; q->rear=new; returnOK; } StatusQueueDelete(Queue*q,QueueElemtype*value,QueueOperatorValue*operator,int*symbol){ QueueNodePtrfirst; if(q->front==q->rear) returnERROR; first=q->front->next; if(first->flag==1){ *value=first->data; *symbol=1; } else{ *operator=first->operator; *symbol=0; } q->front->next=first->next; if(first==q->rear){ q->rear=q->front; } returnOK; } /*利用栈将中缀表达式转化为后缀表达式： *—————————————————————————————————————————————————————————————— *|用户的输入|进行的处理| *|0~9：|直接输出到控制台| *|/，*，(|直接Push| *|+，-|将栈中的元素Pop直到1.栈空或者是2.遇到(| *|)|在遇到(之前将栈中的元素全部Pop| *—————————————————————————————————————————————————————————————— **/ StatusInfix2Postfix(Queue*q){ //Queueq; //QueueInit(&q); Stacks; StackInit(&s); charc,e; charbufferDigit[10]; inti=0; doublelongDigit; printf("PleaseEnterInfixExpression\n"); printf("------------NOTE:endof'#'--------------\n"); scanf("%c",&c); while('#'!=c){ while(c<='9'&&c>='0'||'.'==c){ bufferDigit[i++]=c; bufferDigit[i]='\0'; scanf("%c",&c); if(!((c<='9'&&c>='0')||'.'==c)){ longDigit=atof(bufferDigit); QueueInsert(q,longDigit); i=0; } } if('('==c||'*'==c||'/'==c){ Push(&s,c); } elseif('+'==c||'-'==c){ if(!StackLength(s)) Push(&s,c); else{ Pop(&s,&e); while('('!=e){ QueueInsert_operatorValue(q,e); if(StackLength(s)==0){ break; }else Pop(&s,&e); } if('('==e) Push(&s,e); Push(&s,c); } }elseif(')'==c){ Pop(&s,&e); while('('!=e){ QueueInsert_operatorValue(q,e); Pop(&s,&e); } }elseif('#'==c){ break; }else{ printf("inputERROR!\n"); returnERROR; } scanf("%c",&c); } while(StackLength(s)){ Pop(&s,&e); QueueInsert_operatorValue(q,e); } QueueInsert_operatorValue(q,'#'); returnOK; } StatusShowQueue(Queueq){ printf("TheReversePolishNotationis:"); if(q.front==q.rear){ printf("QueueEmpty"); returnERROR; } QueueNodePtrp=q.front->next; while(p!=q.rear){ if(p->flag) printf("%g",p->data); else printf("%c",p->operator); p=p->next; } printf("\n"); returnOK; } /*利用栈求解后缀表达式(逆波兰表达式)的值。 *—————————————————————————————————————————————————————————————————————— *|+，-，*，/，|将栈顶的两个元素弹出进行计算，将结果压入栈顶| *|数字|将其压入栈顶| *——————————————————————————————————————————————————————————————————————— **/ StatusValueExpression(Queueq){ Stack_2s; StackInit_2(&s); doubleo1; doubleo2; QueueElemtypenumber; QueueOperatorValueoperator; intsymbol; QueueDelete(&q,&number,&operator,&symbol); while(symbol==1||(symbol==0&&'#'!=operator)){ if(symbol==1){ Push_2(&s,number); } elseif(symbol==0){ switch(operator){ case'+': Pop_2(&s,&o1); Pop_2(&s,&o2); Push_2(&s,o2+o1); break; case'-': Pop_2(&s,&o1); Pop_2(&s,&o2); Push_2(&s,o2-o1); break; case'*': Pop_2(&s,&o1); Pop_2(&s,&o2); Push_2(&s,o2*o1); break; case'/': Pop_2(&s,&o1); Pop_2(&s,&o2); Push_2(&s,o2/o1); break; } } QueueDelete(&q,&number,&operator,&symbol); } Pop_2(&s,&o1); printf("TheValueoftheExpressionis%g\n",o1); returnOK; } intmain(){ Queueq; QueueInit(&q); Infix2Postfix(&q); ShowQueue(q); /* QueueElemtypenumber; QueueOperatorValueoperator; intsymbol; QueueDelete(&q,&number,&operator,&symbol); printf("%f,%c,%d\n",number,operator,symbol); */ ValueExpression(q); //Stack /* Stacks; StackInit(&s); StackElemtypec; Push(&s,'1'); Push(&s,'2'); Push(&s,'3'); Push(&s,'4'); Pop(&s,&c); printf("%c",c); Pop(&s,&c); printf("%c",c); Pop(&s,&c); printf("%c",c); Pop(&s,&c); printf("%c",c); */ //Queue /* Queueq; QueueElemtypec; QueueInit(&q); QueueInsert(&q,1); QueueInsert(&q,2); QueueInsert(&q,3); QueueInsert(&q,4); QueueDelete(&q,&c); printf("%d",c); QueueDelete(&q,&c); printf("%d",c); QueueDelete(&q,&c); printf("%d",c); QueueDelete(&q,&c); printf("%d",c); if(QueueDelete(&q,&c)){ printf("%d",c); } */ /* Queueq; QueueInit(&q); QueueInsert(&q,2.1); QueueInsert_operatorValue(&q,'+'); QueueInsert(&q,43.1); QueueInsert_operatorValue(&q,'a'); QueueInsert_operatorValue(&q,'('); intiswho; doubled; charc; QueueDelete(&q,&d,&c,&iswho); if(iswho==1) printf("%f",d); else printf("%c",c); QueueDelete(&q,&d,&c,&iswho); if(iswho==1) printf("%f",d); else printf("%c",c); QueueDelete(&q,&d,&c,&iswho); if(iswho==1) printf("%f",d); else printf("%c",c); QueueDelete(&q,&d,&c,&iswho); if(iswho==1) printf("%f",d); else printf("%c",c); */ return0; }
以上就是C语言数据结构中栈和队列的应用，如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！