有趣的数据结构算法10——后缀表达式（PRN）介绍及利用栈计算后缀表达式的结果

冷不防 2021-11-22 14:08 376阅读 0赞

### 有趣的数据结构算法10——后缀表达式（PRN）介绍及利用栈计算后缀表达式的结果 ###

*  解题思路
 *  实现代码
 *  GITHUB下载连接

在前一天已经利用栈完成2进制到8进制的转换。但是栈的应用方面还有很多，本次我将讲解如何计算后缀表达式的结果。  
![在这里插入图片描述][20190723170158884.jpg_pic_center]

# 解题思路 #

后缀表达式（PRN）也叫逆波兰表达式，是在计算机中用于求值的一种方式，其求值过程可以用到栈来辅助存储。  
在通常的表达式中，二元运算符总是置于与之相关的两个运算对象之间，这种表示法也称为中缀表示，如1+2。波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法，按此方法，每一运算符都置于其运算对象之后，故称为后缀表示，如12+。  
它的优势在于只用两种简单操作，入栈和出栈就可以搞定任何普通表达式的运算。其运算方式如下：  
如果当前字符为变量或者为数字，则压栈，如果是运算符，则将栈顶两个元素弹出作相应运算，结果再入栈，最后当表达式扫描完后，栈里的就是结果。  
![中缀表达式转换到后缀表达式公式][20190724174125600.png_pic_center]  
假定待求值的后缀表达式为：1 2 + 5 3 6 + \* + 7 - ，其实际上为1+2+5\*(3+6)-7。其求值过程如下：  
1、遍历表达式，遇到1和2，压入栈中。此时栈如图所示：

![示例1][1]  
2、接着读到+号，弹出2与1，执行加法运算，得到3，再次入栈。此时栈如图所示：

![示例2][2]  
3、遇到5、3和6，压入栈中。此时栈如图所示：

![示例3][3]  
4、接着读到+号，弹出6与3，执行加法运算，得到9，再次入栈。此时栈如图所示：

![示例4][4]  
5、接着读到\*号，弹出9与5，执行加法运算，得到45，再次入栈。此时栈如图所示：

![示例5][5]  
6、接着读到+号，弹出45与3，执行加法运算，得到48，再次入栈。此时栈如图所示：

![示例6][6]  
7、遇到7，压入栈中。此时栈如图所示：

![示例7][7]  
8、接着读到-号，弹出7与48，执行加法运算，得到41，再次入栈。  
9、由于表达式已结束，读出栈内的最后一个元素，就是结果41。

# 实现代码 #

#include <stdio.h>
    #include <stdlib.h>
    #define Maxsize 10
    typedef double Ele;
    
    struct stack
    {
        
    	Ele* top;
    	Ele* bottom;
    	int stacksize;
    };
    
    typedef struct stack* Stack;
    
    void init(Stack s){
        			//初始化栈
    	Ele *p;
    	p = (Ele*)malloc(Maxsize * sizeof(Ele));
    	if (p == NULL){
        
    		printf("error");
    		exit(1);
    	}
    	s->top = s->bottom = p;
    	s->stacksize = Maxsize;
    }
    
    void PUSH(Stack s, Ele data){
        		//入栈
    	int length;
    	length = s->top - s->bottom;
    	if (length >= s->stacksize){
        
    		s->bottom = (Ele*)realloc(s->bottom,(s->stacksize + Maxsize) * sizeof(Ele));
    		if (s->bottom == NULL){
        
    			printf("内存分配失败\n");
    			exit(1);
    		}
    		s->stacksize = s->stacksize + Maxsize;//更新stacksize的值
    		s->top = s->bottom + length; //更新top的值
    	}
    	*(s->top) = data;
    	s->top++;
    }
    Ele POP(Stack s){
        					//出栈
    	Ele num;
    	if (s->top == s->bottom){
        
    		printf("栈内没有元素了！\n");
    		exit(1);
    	}
    	s->top--;
    	num = *(s->top);
    	return num;
    }
    
    int main(){
        
    	struct stack s;			//定义栈
    	char c = 0,str[10];		//c用于从键盘获取字符，str用于存储每一轮输入的数字，之后会转化成double类型
    	Ele a1, a2, num;		//a1，a2用于栈的运算
    	int i = 0;				//temp量
    
    
    	init(&s);				//初始化栈
    	printf("请输入一个算式：");		
    
    	scanf("%c", &c);		//输入一个字符
    	while (c != '#')
    	{
        
    		while ((c <= '9' && c >= '0') || c == '.'){
        	//该部分用于获取一个double类型的数字
    			str[i++] = c;
    			str[i] = '\0';
    			if (i >= 10){
        
    				printf("输入数据过大");
    				exit(1);
    			}
    			scanf("%c", &c);
    			if (!(c <= '9' && c >= '0') && !(c == '.')){
        
    				a1 = atof(str);						//该函数用于将字符串转化位double
    				PUSH(&s, a1);
    				i = 0;
    				break;
    			}
    		}
    		switch (c)								//判断是否属于加减乘除
    		{
        
    		case '+': 
    			a1 = POP(&s);
    			a2 = POP(&s); 
    			PUSH(&s, a2 + a1);
    			break;
    		case '-': 
    			a1 = POP(&s);
    			a2 = POP(&s); 
    			PUSH(&s, a2 - a1);
    			break;
    		case '*': 
    			a1 = POP(&s);
    			a2 = POP(&s); 
    			PUSH(&s, a2 * a1);
    			break;
    		case '/': 
    			a1 = POP(&s);
    			a2 = POP(&s); 
    			PUSH(&s, a2 / a1);
    			break;
    		case ' ':
    			break;
    		case '#':
    			break;
    		default:
    			printf("输入符号错误！\n");
    			break;
    		}
    		scanf("%c", &c);
    	}
    	num = POP(&s);
    	printf("%.3f\n", num);
    
    	return 0;
    }

# GITHUB下载连接 #

[https://github.com/bubbliiiing/Data-Structure-and-Algorithm][https_github.com_bubbliiiing_Data-Structure-and-Algorithm]

希望得到朋友们的喜欢。  
有问题的朋友可以提问噢。

[20190723170158884.jpg_pic_center]: /images/20211122/9f957abb3a7149e08c74f220ebee47f8.png
[20190724174125600.png_pic_center]: /images/20211122/be098282cdd34d7f917200f2cf42fcef.png
[1]: /images/20211122/f642e6bb8ebe4f07b0578478938089ff.png
[2]: /images/20211122/0b6d5388e14c42778818db3a074e8bde.png
[3]: /images/20211122/c74cee1c812e4bb58971e95838d30f5d.png
[4]: /images/20211122/56aad6842a7f43998b9552d8fb6bff47.png
[5]: /images/20211122/7f64b1167dc74cb8b9dd5b9b9d12f907.png
[6]: /images/20211122/1e70c4e649524a5d9e37a6fbe00f4b58.png
[7]: /images/20211122/27223e9ea04d4737aad0a7dae869ded7.png
[https_github.com_bubbliiiing_Data-Structure-and-Algorithm]: https://github.com/bubbliiiing/Data-Structure-and-Algorithm