写点什么

C 语言编程语法—利用栈实现对后缀表达式的求解

作者:向阳逐梦
  • 2023-06-20
    四川
  • 本文字数:1804 字

    阅读完需:约 6 分钟

C语言编程语法—利用栈实现对后缀表达式的求解

本文实例为大家分享了 C 语言实现对后缀表达式(逆波兰表达式)的求解代码,供大家参考,具体内容如下。

逆波兰表达式:

逆波兰表达式又叫后缀表达式。它是由相应的语法树的后序遍历的结果得到的。例:5 - 8*(6 + 7) + 9 / 4:

其中缀表达式为:5 - 8 * 6 + 7 + 9 / 4

其语法树如下:

因此根据语法树可以得出他后序遍历(后缀表达式)为:5 8 6 7 + * - 9 4 / +

这样就实现了中缀表达式到后缀表达式的转换。同样的也可以得出他的前序遍历(前缀表达式也称波兰表达式): + - 5 * 8 + 6 7 / 9 4

逆波兰表达式计算实现原理:1.首先当遇到运算操作数时将其进行 push 操作;

2.当遇到操作符是将此时的栈 pop 两次,先取出的栈顶为右操作数;

3.执行此方法到整个数组遍历完。

实现算法如下:

void CalFunction(SqStack *S,char str[]){/*实现浮点型数据后缀表达式的加减乘除*/ Elemtype number,e,d; char arr[MAXBUFFER]; int i=0,j=0;  InitStack(S);  while(str[i]!='\0') { while(isdigit(str[i])||str[i]=='.') //过滤数字 { arr[j++]=str[i++]; arr[j]='\0';  if( j >= MAXBUFFER ) { printf("输入单个数据过大!\n"); return ; } if(str[i]==' ') { number=atof(arr); //利用atof函数将数字字符串转化为double型数据 PushStack(S,number); //将转换的数进行压栈 j=0;   //这里不要忘记将j重新初始化进行下个数据的转化 break; } } /*如果遇到操作运算符则,弹出两个数据进行运算,然后将得出的结果重新入栈*/ switch(str[i]) { case '+': PopStack(S,&e); PopStack(S,&d); PushStack(S,d+e); break; case '-': PopStack(S,&e); PopStack(S,&d); PushStack(S,d-e); break; case '*': PopStack(S,&e); PopStack(S,&d); PushStack(S,d*e); break; case '/': PopStack(S,&e); PopStack(S,&d); if(e == 0) { printf("输入出错,分母为零!\n"); return ; } PushStack(S,d/e); break; } i++; //继续遍历直到遍历字符串结束 }  PopStack(S,&e); printf("计算结果为:%lf",e); }
复制代码

完整代码如下:

#include<stdio.h>#include<stdlib.h>#include<assert.h>#include<ctype.h>
#define INITSIZE 20#define INCREMENT 10#define MAXBUFFER 10#define LEN sizeof(Elemtype)
/*栈的动态分配顺序存储结构*/typedef double Elemtype;typedef struct{ Elemtype *base; Elemtype *top; int StackSize; }SqStack;
void InitStack(SqStack *S){ S->base=(Elemtype*)malloc(LEN*INITSIZE); assert(S->base != NULL); S->top=S->base; S->StackSize=INITSIZE;}
void PushStack(SqStack *S,Elemtype e){ if(S->top - S->base >= S->StackSize) { S->base=(Elemtype*)realloc(S->base,(S->StackSize+INCREMENT)*LEN); assert(S->base !=NULL); S->top=S->base+S->StackSize; S->StackSize+=INCREMENT; } *S->top =e; S->top++;}
void PopStack(SqStack *S,Elemtype *e){ *e=*--S->top;}
void CalFunction(SqStack *S,char str[]){ Elemtype number,e,d; char arr[MAXBUFFER]; int i=0,j=0; InitStack(S); while(str[i]!='\0') { while(isdigit(str[i])||str[i]=='.') //过滤数字 { arr[j++]=str[i++]; arr[j]='\0'; if( j >= MAXBUFFER ) { printf("输入单个数据过大!\n"); return ; } if(str[i]==' ') { number=atof(arr); //利用atof函数将数字字符转化为double型数据 PushStack(S,number); //将转换的数进行压栈 j=0; break; } } switch(str[i]) { case '+': PopStack(S,&e); PopStack(S,&d); PushStack(S,d+e); break; case '-': PopStack(S,&e); PopStack(S,&d); PushStack(S,d-e); break; case '*': PopStack(S,&e); PopStack(S,&d); PushStack(S,d*e); break; case '/': PopStack(S,&e); PopStack(S,&d); if(e == 0) { printf("输入出错,分母为零!\n"); return ; } PushStack(S,d/e); break; } i++; } PopStack(S,&e); printf("计算结果为:%lf",e); }
int main(){ char str[100]; SqStack S; printf("请按逆波兰表达式输入数据,每个数据之间用空格隔开:"); gets(str); CalFunction(&S,str); return 0;}

// 检测用例 5 - (6 + 7) * 8 + 9 / 4
// 输入:5 8 6 7 + * - 9 4 / + #
// 输出: - 96.750000
复制代码

运行效果截图如下:


发布于: 刚刚阅读数: 3
用户头像

向阳逐梦

关注

人生享受编程,编程造就人生! 2022-06-01 加入

某公司芯片测试工程师,嵌入式开发工程师,InfoQ签约作者,阿里云星级博主,华为云·云享专家。座右铭:向着太阳,追逐梦想!

评论

发布
暂无评论
C语言编程语法—利用栈实现对后缀表达式的求解_栈_向阳逐梦_InfoQ写作社区