大佬教程收集整理的这篇文章主要介绍了C语言中栈和队列实现表达式求值的实例,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
C语言中栈和队列实现表达式求值的实例
实现代码:
#include<stdio.h> #include<stdlib.h> #define OK 1 #define ERROR 0 #define STACK_SIZE 20 #define STACK_INCREMENT 10 #define QUEUE_SIZE 20 typedef int Status; typedef char StackElemtype; typedef struct Stack{ StackElemtype* base; StackElemtype* top; int stackSize; }Stack; Status StackInit(Stack* s){ s->base = (StackElemtype*)malloc(sizeof(StackElemtypE) * STACK_SIZE); if( !s->base ) return ERROR; s->top = s->base; s->stackSize = STACK_SIZE; return OK; } Status Pop(Stack* s,StackElemtype* value){ if( s->base == s->top ){ printf("\nstack empty\n"); return ERROR; } *value = *(--(s->top)); return OK; } Status Push(Stack* s,StackElemtype value){ if( s->top - s->base == s->stackSizE){ s->base = (StackElemtype*)realloc(s->base,sizeof(StackElemtypE) * (STACK_INCREMENT + STACK_SIZE)); if( !s->base ) return ERROR; s->top = s->base + STACK_SIZE; s->stackSize = STACK_SIZE + STACK_INCREMENT; } *(s->top) = value; s->top++; return OK; } int StackLength(Stack s){ return s.top - s.base; } typedef double StackElemtype_ForValueExpeRSSion; typedef struct Stack_2{ StackElemtype_ForValueExpeRSSion* base; StackElemtype_ForValueExpeRSSion* top; int stackSize; }Stack_2; Status StackInit_2(Stack_2* s){ s->base = (StackElemtype_ForValueExpeRSSion*)malloc(sizeof(StackElemtype_ForValueExpeRSSion) * STACK_SIZE); if( !s->base ) return ERROR; s->top = s->base; s->stackSize = STACK_SIZE; return OK; } Status Pop_2(Stack_2* s,StackElemtype_ForValueExpeRSSion* value){ if( s->base == s->top ){ printf("\nstack empty\n"); return ERROR; } *value = *(--(s->top)); return OK; } Status Push_2(Stack_2* s,StackElemtype_ForValueExpeRSSion value){ if( s->top - s->base == s->stackSizE){ s->base = (StackElemtype_ForValueExpeRSSion*)realloc(s->base,sizeof(StackElemtype_ForValueExpeRSSion) * (STACK_INCREMENT + STACK_SIZE)); if( !s->base ) return ERROR; s->top = s->base + STACK_SIZE; s->stackSize = STACK_SIZE + STACK_INCREMENT; } *(s->top) = value; s->top++; return OK; } typedef double QueueElemtype; typedef char QueueOperatorValue; typedef struct QueueNode{ QueueElemtype data; QueueOperatorValue operator; struct QueueNode* next; int flag; }QueueNode,*QueueNodePtr; typedef struct Queue{ QueueNodePtr front; QueueNodePtr rear; }Queue; Status QueueInit(Queue* q){ q->front = (QueueNodePtr)malloc(sizeof(QueueNodE)); if( !q->front ) return ERROR; q->rear = q->front; q->rear->next = NulL; return OK; } Status QueueInsert(Queue* q,QueueElemtype value){ QueueNodePtr new; new = (QueueNodePtr)malloc(sizeof(QueueNodE)); if( !new ) return ERROR; new->data = value; new->flag = 1; new->next = NulL; q->rear->next = new; q->rear = new; return OK; } Status QueueInsert_operatorValue(Queue* q,QueueOperatorValue value){ QueueNodePtr new; new = (QueueNodePtr)malloc(sizeof(QueueNodE)); if( !new ) return ERROR; new->operator = value; new->flag = 0; new->next = NulL; q->rear->next = new; q->rear = new; return OK; } Status Queuedelete(Queue* q,QueueElemtype* value,QueueOperatorValue *operator,int* symbol){ QueueNodePtr first; if( q->front == q->rear ) return ERROR; 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; } return OK; } /* 利用栈将中缀表达式转化为后缀表达式: * ―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――― * | 用户的输入 | 进行的处理 | * | 0~9: | 直接输出到控制台 | * | /,*,( | 直接Push | * | +,- | 将栈中的元素Pop直到1.栈空或者是2.遇到( | * | ) | 在遇到(之前将栈中的元素全部Pop | * ―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――― * */ Status Infix2Postfix(Queue* q){ //Queue q; //QueueInit(&q); Stack s; StackInit(&s); char c,e; char bufferDigit[10]; int i = 0; double longDigit; printf(" Please Enter Infix Expression\n"); printf("------------NOTE: end of '#'--------------\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); } else if( '+' == 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); } }else if( ')' == c ){ Pop(&s,&E); while( '(' != e ){ QueueInsert_operatorValue(q,E); Pop(&s,&E); } }else if( '#' == C){ break; }else{ printf("input ERROR!\n"); return ERROR; } scanf("%c",&c); } while(StackLength(s)){ Pop(&s,&E); QueueInsert_operatorValue(q,E); } QueueInsert_operatorValue(q,'#'); return OK; } Status ShowQueue(Queue q){ printf("The Reverse Polish Notation is:"); if(q.front == q.rear){ printf("Queue Empty"); return ERROR; } QueueNodePtr p = q.front->next; while(p != q.rear){ if(p->flag) printf("%g ",p->data); else printf("%c ",p->operator); p = p->next; } printf("\n"); return OK; } /* 利用栈求解后缀表达式(逆波兰表达式)的值。 * ―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――― * | +,-,*,/, | 将栈顶的两个元素弹出进行计算,将结果压入栈顶 | * | 数字 | 将其压入栈顶 | * ――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――― * */ Status ValueExpression(Queue q){ Stack_2 s; StackInit_2(&s); double o1; double o2; QueueElemtype number; QueueOperatorValue operator; int symbol; Queuedelete(&q,&number,&operator,&symbol); while( symbol == 1 || ( symbol == 0 && '#' != operator)){ if(symbol == 1){ Push_2(&s,number); } else if(symbol == 0){ switch(operator){ case '+': Pop_2(&s,&o1); Pop_2(&s,&o2); Push_2(&s,o2 + o1); break; case '-': Pop_2(&s,o2 - o1); break; case '*': Pop_2(&s,o2 * o1); break; case '/': Pop_2(&s,o2 / o1); break; } } Queuedelete(&q,&symbol); } Pop_2(&s,&o1); printf("The Value of the Expression is %g\n",o1); return OK; } int main(){ Queue q; QueueInit(&q); Infix2Postfix(&q); ShowQueue(q); /* QueueElemtype number; QueueOperatorValue operator; int symbol; Queuedelete(&q,&symbol); printf("%f,%c,%d\n",number,operator,symbol); */ ValueExpression(q); //Stack /* Stack s; StackInit(&s); StackElemtype c; Push(&s,'1'); Push(&s,'2'); Push(&s,'3'); Push(&s,'4'); Pop(&s,&c); printf("%c ",c); Pop(&s,c); */ //Queue /* Queue q; QueueElemtype c; QueueInit(&q); QueueInsert(&q,1); QueueInsert(&q,2); QueueInsert(&q,3); QueueInsert(&q,4); Queuedelete(&q,&c); printf("%d ",c); Queuedelete(&q,c); if(Queuedelete(&q,&C)){ printf("%d ",c); } */ /* Queue q; QueueInit(&q); QueueInsert(&q,2.1); QueueInsert_operatorValue(&q,'+'); QueueInsert(&q,43.1); QueueInsert_operatorValue(&q,'a'); QueueInsert_operatorValue(&q,'('); int iswho; double d; char c; Queuedelete(&q,&d,&c,&iswho); if(iswho == 1) printf("%f ",d); else printf("%c ",c); */ return 0; }
以上就是C语言数据结构中栈和队列的应用,如有疑问请留言或者到本站社区交流讨论,感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
以上是大佬教程为你收集整理的C语言中栈和队列实现表达式求值的实例全部内容,希望文章能够帮你解决C语言中栈和队列实现表达式求值的实例所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。