C语言中如何通过栈和队列实现表达式求值的实例代码？

本文共计1866个文字，预计阅读时间需要8分钟。

C语言中栈和队列实现表达式求值的示例及代码：

示例：计算表达式 3 + 5 * (2 - 1) 的值。

代码：c#include #include

#define MAX_SIZE 100

// 栈结构体typedef struct { int data[MAX_SIZE]; int top;} Stack;

// 队列结构体typedef struct { int data[MAX_SIZE]; int front; int rear;} Queue;

// 初始化栈void initStack(Stack *s) { s->top=-1;}

// 判断栈是否为空int isEmptyStack(Stack *s) { return s->top==-1;}

// 判断栈是否已满int isFullStack(Stack *s) { return s->top==MAX_SIZE - 1;}

// 入栈void push(Stack *s, int value) { if (isFullStack(s)) { printf(栈已满\n); return; } s->data[++s->top]=value;}

// 出栈int pop(Stack *s) { if (isEmptyStack(s)) { printf(栈为空\n); return 0; } return s->data[s->top--];}

// 初始化队列void initQueue(Queue *q) { q->front=q->rear=0;}

// 判断队列是否为空int isEmptyQueue(Queue *q) { return q->front==q->rear;}

// 判断队列是否已满int isFullQueue(Queue *q) { return (q->rear + 1) % MAX_SIZE==q->front;}

// 入队void enqueue(Queue *q, int value) { if (isFullQueue(q)) { printf(队列已满\n); return; } q->data[q->rear]=value; q->rear=(q->rear + 1) % MAX_SIZE;}

// 出队int dequeue(Queue *q) { if (isEmptyQueue(q)) { printf(队列已空\n); return 0; } return q->data[q->front++];}

// 计算表达式值int calculate(char *expr) { Stack numStack, opStack; initStack(&numStack); initStack(&opStack); int num1, num2, value; char op;

for (int i=0; expr[i] !='\0'; i++) { if (expr[i] >='0' && expr[i] ='0' && expr[i] <='9') { value=value * 10 + (expr[i] - '0'); i++; } i--; push(&numStack, value); } else if (expr[i]=='(') { push(&opStack, expr[i]); } else if (expr[i]==')') { while (!isEmptyStack(&opStack) && opStack.data[opStack.top] !='(') { num2=pop(&numStack); num1=pop(&numStack); op=pop(&opStack); switch (op) { case '+': push(&numStack, num1 + num2); break; case '-': push(&numStack, num1 - num2); break; case '*': push(&numStack, num1 * num2); break; case '/': push(&numStack, num1 / num2); break; } } pop(&opStack); // 弹出 '(' } else if (expr[i]=='+' || expr[i]=='-' || expr[i]=='*' || expr[i]=='/') { while (!isEmptyStack(&opStack) && opStack.data[opStack.top] !='(' && (expr[i]=='+' || expr[i]=='-' || expr[i]=='*' || expr[i]=='/') && (opStack.data[opStack.top]=='+' || opStack.data[opStack.top]=='-' || opStack.data[opStack.top]=='*' || opStack.data[opStack.top]=='/')) { num2=pop(&numStack); num1=pop(&numStack); op=pop(&opStack); switch (op) { case '+': push(&numStack, num1 + num2); break; case '-': push(&numStack, num1 - num2); break; case '*': push(&numStack, num1 * num2); break; case '/': push(&numStack, num1 / num2); break; } } push(&opStack, expr[i]); } }

while (!isEmptyStack(&opStack)) { num2=pop(&numStack); num1=pop(&numStack); op=pop(&opStack); switch (op) { case '+': push(&numStack, num1 + num2); break; case '-': push(&numStack, num1 - num2); break; case '*': push(&numStack, num1 * num2); break; case '/': push(&numStack, num1 / num2); break; } }

return pop(&numStack);}

int main() { char expr[]=3 + 5 * (2 - 1); int result=calculate(expr); printf(表达式 %s 的值为：%d\n, expr, result); return 0;}

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); /* QueueElemtype number; QueueOperatorValue operator; int symbol; QueueDelete(&q,&number,&operator,&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); printf("%c ", c); Pop(&s,&c); printf("%c ", c); Pop(&s,&c); printf("%c ", 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); printf("%d ", c); QueueDelete(&q,&c); printf("%d ", c); QueueDelete(&q,&c); printf("%d ", 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); 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); */ return 0; }

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