栈和队列的应用---表达式求值，递归（C语言知识）

表达式求值

枚举

将变量的值一一列举出来，变量的值只限于列举出来的值的范围内

在枚举中列出的每一个值，成为枚举元素

每一个枚举元素由系统定义了一个用序号表示的数值，从0开始，分别为0，1，2，······

语法：

enum枚举名{枚举元素....};

#include<stdio.h>typedefenum{mon=1,tue,wed,thu,fri,sat,sum}weekday;enumbool{false,ture};intmain(){enumweekdaya;a=mon;enumweekdayb;b=tue;printf("%d\n",a);//1printf("%d\n",b);//2return0;}

后缀表达式求值

1. 从左到右遍历后缀表达式的每个元素：
   • 若元素是操作数，直接压入栈中。
   • 若元素是运算符，弹出栈顶的2 个操作数（注意顺序：后弹出的是左操作数，先弹出的是右操作数），用运算符计算后，将结果压回栈中。
2. 遍历结束后，栈中剩余的唯一元素就是表达式的计算结果。

#include<stdio.h>#include<stdlib.h>#defineMAXSIZE100typedefintElemType;typedefstruct{ElemType*data;inttop;}Stack;typedefenum{LEFT_PARE,RIGHT_PARE,//左括号，右括号ADD,SUB,MUL,DIV,MOD,// 加，减，乘，除，取余EOS,NUM// \0,数字}contentType;charexpr[]="82/2+56*-";//初始化Stack*initStack(){Stack*s=(Stack*)malloc(sizeof(Stack));s->data=(ElemType*)malloc(sizeof(ElemType));s->top=-1;returns;}// 判断栈是否为空intisEmpty(Stack*s){if(s->top==-1){printf("空的\n");return1;}else{return0;}}//进栈intpush(Stack*s,ElemType e){if(s->top>=MAXSIZE-1){printf("满了\n");return0;}s->top++;s->data[s->top]=e;return1;}//出栈ElemTypepop(Stack*s,ElemType*e){if(s->top==-1){printf("空的\n");return0;}*e=s->data[s->top];s->top--;return1;}// 获取栈顶元素intgetTop(Stack*s,ElemType*e){if(s->top==-1){printf("空的\n");return0;}*e=s->data[s->top];return1;}contentTypegetToken(char*symbol,int*index){*symbol=expr[*index];*index=*index+1;switch(*symbol){case'(':returnLEFT_PARE;case')':returnRIGHT_PARE;case'+':returnADD;case'-':returnSUB;case'*':returnMUL;case'/':returnDIV;case'%':returnMOD;case'\0':returnEOS;default:returnNUM;}}inteval(Stack*s){charsymbol;intop1,op2;intindex=0;contentType token;token=getToken(&symbol,&index);ElemType result;while(token!=EOS){if(token==NUM){push(s,symbol-'0');// symbol - '0'得到数值}else{//op2是栈顶，op1是次顶pop(s,&op2);pop(s,&op1);switch(token){caseADD:push(s,op1+op2);break;caseSUB:push(s,op1-op2);break;caseMUL:push(s,op1*op2);break;caseDIV:if(op2==0){printf("错误：除数不能为0！\n");return0;}push(s,op1/op2);break;caseMOD:if(op2==0){printf("错误：模运算除数不能为0！\n");return0;}push(s,op1%op2);break;default:printf("未知运算符！\n");break;}}// 获取下一个tokentoken=getToken(&symbol,&index);}pop(s,&result);printf("%d\n",result);//结果：-24return1;}intmain(){Stack*s=initStack();eval(s);return0;}

中缀表达式转后缀表达式

x/(i-j)*y———>xij-/y*

1. 优先级定义（从高到低）

2. 转换步骤

1. 初始化：空栈（存储运算符） + 空输出队列（存储后缀表达式）；

2. 遍历中缀表达式的每个 token

   （数字 / 运算符 / 括号）：

   • 若为数字：直接加入输出队列；
   • 若为左括号(：压入栈；
   • 若为右括号)：持续弹出栈顶运算符到输出队列，直到遇到左括号(，并弹出左括号（不加入输出）；
   • 若为运算符：
     • 栈非空时，持续弹出栈顶优先级 ≥ 当前运算符的运算符到输出队列；
     • 将当前运算符压入栈；

3. 遍历结束后：将栈中剩余的所有运算符依次弹出到输出队列；

4. 输出队列即为后缀表达式。

#include<stdio.h>#include<stdlib.h>#include<string.h>#include<ctype.h>#defineMAXSIZE100typedefintElemType;typedefstruct{ElemType*data;inttop;}Stack;typedefenum{LEFT_PARE,// 0RIGHT_PARE,// 1ADD,// 2SUB,// 3MUL,// 4DIV,// 5MOD,// 6EOS,// 7NUM// 8}contentType;charexpr[]="x/(i-j)*y";//char expr[] = "8/(5-3)*4"; // 中缀表达式charpostfix_expr[MAXSIZE]={0};// 存储后缀表达式（字符形式，如'+'而非枚举值）intpostfix_idx=0;// 修正后的优先级数组intin_stack[]={0,19,12,12,13,13,13,0,0};intout_stack[]={19,0,12,12,13,13,13,0,0};// 枚举值转运算符字符chartoken_to_char(contentType token){switch(token){caseADD:return'+';caseSUB:return'-';caseMUL:return'*';caseDIV:return'/';caseMOD:return'%';default:return'\0';}}// 字符转枚举值contentTypechar_to_token(charc){switch(c){case'+':returnADD;case'-':returnSUB;case'*':returnMUL;case'/':returnDIV;case'%':returnMOD;case'(':returnLEFT_PARE;case')':returnRIGHT_PARE;case'\0':returnEOS;default:returnNUM;}}//初始化栈Stack*initStack(){Stack*s=(Stack*)malloc(sizeof(Stack));s->data=(ElemType*)malloc(MAXSIZE*sizeof(ElemType));s->top=-1;returns;}// 判断栈是否为空intisEmpty(Stack*s){returns->top==-1;}//进栈intpush(Stack*s,ElemType e){if(s->top>=MAXSIZE-1)return0;s->top++;s->data[s->top]=e;return1;}//出栈intpop(Stack*s,ElemType*e){if(isEmpty(s))return0;*e=s->data[s->top];s->top--;return1;}// 获取栈顶元素intgetTop(Stack*s,ElemType*e){if(isEmpty(s))return0;*e=s->data[s->top];return1;}// 释放栈内存voidfreeStack(Stack*s){if(s){free(s->data);free(s);}}// 获取TokencontentTypegetToken(char*symbol,int*index){*symbol=expr[*index];if(*symbol=='\0')returnEOS;*index=*index+1;returnchar_to_token(*symbol);}// 打印Tokenvoidprint_token(contentType token,charsymbol){switch(token){caseADD:printf("+");break;caseSUB:printf("-");break;caseMUL:printf("*");break;caseDIV:printf("/");break;caseMOD:printf("%%");break;caseNUM:printf("%c",symbol);break;default:break;}}// 中缀转后缀voidpostfix(Stack*s){contentType token;intindex=0;charsymbol;ElemType e;postfix_idx=0;memset(postfix_expr,0,sizeof(postfix_expr));push(s,EOS);token=getToken(&symbol,&index);while(token!=EOS){if(token==NUM){print_token(token,symbol);postfix_expr[postfix_idx++]=symbol;// 存储数字字符}elseif(token==RIGHT_PARE){getTop(s,&e);while(e!=LEFT_PARE){if(!pop(s,&e))break;if(e==LEFT_PARE)break;charop=token_to_char((contentType)e);print_token((contentType)e,op);postfix_expr[postfix_idx++]=op;// 存储运算符字符getTop(s,&e);}pop(s,&e);}elseif(token==LEFT_PARE){push(s,token);}else{getTop(s,&e);while(in_stack[e]>=out_stack[token]){if(!pop(s,&e))break;charop=token_to_char((contentType)e);print_token((contentType)e,op);postfix_expr[postfix_idx++]=op;// 存储运算符字符getTop(s,&e);}push(s,token);}token=getToken(&symbol,&index);}// 弹出剩余运算符getTop(s,&e);while(e!=EOS){pop(s,&e);charop=token_to_char((contentType)e);if(op!='\0'){// 过滤无效字符print_token((contentType)e,op);postfix_expr[postfix_idx++]=op;}getTop(s,&e);}printf("\n");}// 后缀表达式求值inteval(Stack*s,char*post_expr){intindex=0;ElemType result,op1,op2;s->top=-1;// 重置栈while(post_expr[index]!='\0'){charc=post_expr[index];index++;if(isdigit(c)){// 数字入栈push(s,c-'0');}elseif(c=='+'||c=='-'||c=='*'||c=='/'||c=='%'){// 运算符计算if(!pop(s,&op2)||!pop(s,&op1)){printf("操作数不足！\n");return0;}switch(c){case'+':push(s,op1+op2);break;case'-':push(s,op1-op2);break;case'*':push(s,op1*op2);break;case'/':if(op2==0){printf("除数不能为0！\n");return0;}push(s,op1/op2);break;case'%':if(op2==0){printf("模运算除数不能为0！\n");return0;}push(s,op1%op2);break;}}}// 弹出最终结果if(pop(s,&result)&&isEmpty(s)){printf("求值结果：%d\n",result);return1;}else{printf("表达式格式错误！\n");return0;}}intmain(){Stack*s=initStack();// 1. 中缀转后缀printf("中缀表达式：%s\n",expr);printf("后缀表达式：");postfix(s);// 2. 后缀表达式求值if(strspn(expr,"0123456789+-*/%()")==strlen(expr)){eval(s,postfix_expr);}else{printf("表达式含字母，跳过求值！\n");}freeStack(s);return0;}

中缀表达式：x/(i-j)*y
后缀表达式：xij-/y *
表达式含字母，跳过求值！

递归

在函数调用过程中，调用自己本身

计算1~n的和

非递归方式

intfun(intn){intsum=0;for(inti=0;i<n;i++){sum=sum+i;}returnsum;}

递归方式

intfun(intn){if(n==1){return1;}else{returnfun(n-1)+n;}}

斐波那契数列

斐波那契数列，又称黄金分割数列，其数值为：1、1、2、3、5、8、13、21、34······

非递归

intfib(intn){inta=1;intb=1;intresult=1;while(n>2){result=a+b;a=b;b=result;n--;}returnresult;}intmain(){intn;scanf("%d",&n);intret=fib(n);printf("%d\n",ret);reurn0;}

递归

intfib(intn){if(n<=2){return1;}else{returnfib(n-1)+fib(n-2);}}intmain(){intn;scanf("%d",&n);intret=fib(n);printf("%d",ret);return0;}