逆波兰表达式：
逆波兰表达式又叫后缀表达式。它是由相应的语法树的后序遍历的结果得到的。
例：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
运行效果截图如下：
