本文实例为大家分享了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
运行效果截图如下:
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。
原文链接:https://blog.csdn.net/qq_42552533/article/details/86562791