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

左手的ㄟ右手 2022-03-25 10:56 253阅读 0赞

**逆波兰表达式：**  
　　逆波兰表达式又叫后缀表达式。它是由相应的语法树的后序遍历的结果得到的。  
例：5 - 8\*(6 + 7) + 9 / 4：  
**其中缀表达式为：5 - 8 \* 6 + 7 + 9 / 4**  
其语法树如下：  
　　![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyNTMz_size_16_color_FFFFFF_t_70]  
**因此根据语法树可以得出他后序遍历（后缀表达式）为：  
5 8 6 7 + \* - 9 4 / +**

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

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

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

3.执行此方法到整个数组遍历完。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyNTMz_size_16_color_FFFFFF_t_70 1]  
**实现算法如下：**

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

**运行效果截图如下：**  
![在这里插入图片描述][20190122160927464.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyNTMz_size_16_color_FFFFFF_t_70]: /images/20220325/a8d81579409b4f6499a69f9f1c1e1139.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyNTMz_size_16_color_FFFFFF_t_70 1]: /images/20220325/6310477c343c450dbfaac5548a3ced58.png
[20190122160927464.png]: /images/20220325/d54a0bf9335b411eba6831d35ab1e11a.png