利用栈实现对逆波兰表达式的求解（C代码实现）

我们最熟悉的表达式：1+2，(1+2)3，3+42+4等等都是中缀表示法。对于人们来说，也是最直观的一种求值方式，先算括号里的，然后算乘除，最后算加减，但是，计算机处理中缀表达式却并不方便，因为没有一种简单的数据结构可以方便从一个表达式中间抽出一部分算完结果，再放进去，然后继续后面的计算。而逆波兰表达式则可以轻松解决这一问题。
　　逆波兰表达式：
　　逆波兰表达式又叫后缀表达式。它是由相应的语法树的后序遍历的结果得到的。
　　例：5 - 8*(6 + 7) + 9 / 4：
　　其中缀表达式为：5 - 8 * 6 + 7 + 9 / 4
　　其语法树如下：
　　

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

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

下面相关代码如下：

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<ctype.h>

#define ERROR  0
#define OK     1
#define INITSIZE  20
#define INCREMENT 10
#define MAXBUFFER 10

typedef int Status;
typedef double Elemtype;
typedef struct{
	Elemtype *base;
	Elemtype *top;
	int StackSize; 
}SqStack;

void InitStack(SqStack *S)
{
	S->base=(Elemtype*)malloc(sizeof(Elemtype)*INITSIZE);
	assert(S->base != NULL);
	S->top=S->base;
	S->StackSize=INITSIZE;
}

Status PushStack(SqStack *S,Elemtype e)
{
	if(S->top - S->base >= S->StackSize)
	{
		S->base=(Elemtype*)realloc(S->base,(S->StackSize+INCREMENT)*sizeof(Elemtype));
		if(!S->base)
		{
			return ERROR;
		}
		S->top=S->base+S->StackSize;
		S->StackSize+=INCREMENT;
	}
	*S->top =e;
	S->top++;
	return OK;
}

Status PopStack(SqStack *S,Elemtype *e)
{
	if(S->top == S->base)
	{
		return ERROR;
	}
	*e=*--S->top;
	return OK;
}

int main()
{
	SqStack S;
	char str[MAXBUFFER];
	char c;
	int i=0;
	double d,e;
	
	InitStack(&S);
	printf("请按逆波兰表达式输入数据,每个数据之间用空格隔开,以#号作为结束的标志：\n");
	scanf("%c",&c);
	while(c != '#')
	{
		while(isdigit(c) || c == '.')
		{
			str[i++] = c;
			str[i] = '\0';
			
			if(i >= 10)
			{
				printf("error!\n输入的单个数据过大!\n");
				return ERROR;
			}
			scanf("%c",&c);
			if( c == ' ')                //空格作为每个数数据间隔界限 
			{
				double num=atof(str);   //将数字字符串转换为浮点型数 
				PushStack(&S,num);      //把转换成的数压栈 
				i=0;                    //记录下一个字符数组，i重新初始化 
				break;
			}	
		}
			
		switch(c)
		{
			case '+':
				PopStack(&S,&d);
				PopStack(&S,&e);
				PushStack(&S,e+d);
				break;
			case '-':
				PopStack(&S,&d);
				PopStack(&S,&e);
				PushStack(&S,e-d);
				break;
			case '*':
				PopStack(&S,&d);
				PopStack(&S,&e);
				PushStack(&S,e*d);
				break;
			case '/':
				PopStack(&S,&d);
				PopStack(&S,&e);
				assert( d != 0);
				PushStack(&S,e/d);
				break;		
		}
		scanf("%c",&c);
	}
	
	PopStack(&S,&d);
	printf("最终结果为：%lf",d);
	return 0;
}


// 检测用例 5 - (6 + 7) * 8 + 9 / 4

// 输入：5 8 6 7 + * - 9 4 / + # 

// 输出： - 96.750000

运行效果截图如下：