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,&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("The Value of the Expression is %g\n",o1); return OK; } int main(){ Queue q; QueueInit(&q); Infix2Postfix(&q); ShowQueue(q); ValueExpression(q); //Stack //Queue return 0; }

以上就是C语言数据结构中栈和队列的应用，如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！