有趣的数据结构算法11——实现中缀表达式到后缀表达式的转换

怼烎@ 2021-11-22 10:08 281阅读 0赞

### 有趣的数据结构算法11——实现中缀表达式到后缀表达式的转换 ###

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

这是学习栈的最后一篇blog了，在上一篇博客里，讲述了如何利用栈计算后缀表达式的结果，但是谁会无缘无故用后缀表达式写一个式子在那里计算呢？这么仔细一想，岂不是……  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center]  
其实也不是完蛋，只要在写个程序完成中缀表达式到后缀表达式的转换即可。

# 解题思路 #

在上一篇博客里我已经简要介绍了什么是后缀表达式。还不了解的朋友可以看看我的上一篇博客。  
[https://blog.csdn.net/weixin\_44791964/article/details/97143790][https_blog.csdn.net_weixin_44791964_article_details_97143790]  
中缀表达式向后缀表达式的转换公式如下：

![中缀表达式转换到后缀表达式公式][20190724174125600.png_pic_center]  
转换规则是这样的，转换时也需要利用到栈。  
1、如果遇到的是数字，直接将其输出。  
2、如果遇到操作符’(’、’\*’、’/’，由于其优先级较高，直接进行入栈。  
3、如果遇到操作符’)’，则取出其与’(‘之间的所有操作符，同时取出’(’。  
4、如果遇到操作符’+’、’-’，如果之前曾经将’(‘压入栈，则取出其与’(‘之间的所有操作符，不取出’(’；如果之前未将’(‘压入栈，则取出所有操作符，因为在栈中的所有操作符的优先级都比最后一个’+’、’-'高。  
5、如果输入到达末尾，弹出所有操作符。

假定待求后缀表达式的中缀表达式为：1+2+5\*(3+6)-7。其转换结果为1 2 + 5 3 6 + \* + 7 - ，其转换过程如下：  
1、遍历表达式，遇到1，直接输出，此时输出为：1  
2、接着读到‘+’号，压入栈。

![示例1][1]  
3、接着读到2，直接输出，此时输出为：1 2  
4、接着读到‘+’号，由于栈中的操作符优先级较高，所以首先元素出栈并输出，此时输出为1 2 +，再将新的‘+’号入栈。

![示例2][1]  
5、接着读到5，直接输出，此时输出为：1 2 + 5  
6、接着读到‘\*’号和‘(’左括号，以此入栈。

![示例3][3]  
7、接着读到3，直接输出，此时输出为：1 2 + 5 3  
8、接着读到‘+’号，由于栈顶元素为’(’，无需读出任何元素，直接入栈。

![示例4][4]  
9、接着读到6，直接输出，此时输出为：1 2 + 5 3 6  
10、接着读到‘)’右括号，取出其与’(‘之间的所有操作符，同时取出’(’，此时输出为1 2 + 5 3 6 +

![示例5][5]  
11、接着读到‘-’号，由于栈内已经没有’(’，读出所有栈内元素，此时输出为1 2 + 5 3 6 + \* +，再将’-'号压入栈。

![示例6][6]  
12、接着读到7，直接输出，此时输出为：1 2 + 5 3 6 + \* + 7  
13、由于输入完成，所有元素出栈，得到输出：1 2 + 5 3 6 + \* + 7 -

# 实现代码 #

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define Initsize 30
    #define Newsize 30
    
    typedef char Ele;
    
    struct Stack{
        
    	Ele* Top;
    	Ele* Base;
    	int Stacksize;
    };
    typedef struct Stack* stk;
    
    
    void init(stk);				//函数声明
    void push(stk p, Ele e);	
    Ele pop(stk p);
    
    void init(stk p){
        			//初始化函数
    	p->Base = (Ele*)malloc(Initsize*sizeof(Ele));
    	if (p->Base == NULL){
        
    		printf("内存分配失败。");
    		exit(1);
    	}
    	p->Top = p->Base;
    	p->Stacksize = Initsize;
    }
    
    void push(stk p, Ele e){
        	//入栈
    	int len;
    	len	= p->Top - p->Base;
    	if ( len >= p->Stacksize)
    	{
        	//动态分配空间
    		p->Base = (Ele*)realloc(p->Base, (p->Stacksize + Newsize)*sizeof(Ele));
    		if (p->Base == NULL){
        
    			printf("内存分配失败。");
    			exit(1);
    		}
    		p->Stacksize = p->Stacksize + Newsize;
    		p->Top = p->Base + len;
    	}
    	*(p->Top) = e;
    	p->Top++;
    }
    
    Ele pop(stk p){
        		//出栈
    	Ele e;
    	if (p->Top == p->Base){
        
    		printf("已经到达底端");
    		exit(0);
    	}
    	(p->Top)--;
    	e = *(p->Top);
    	return e;
    }
    
    int main(){
        
    	struct Stack p;		//定义栈
    	Ele c,e[3]="0 ";		//c用于接收键盘字符
    	//定义e[]是因为使用strcat函数要求两个输入量都是字符串，需要以\0结尾，不可以直接加入一个字符
    	Ele str[10],all[200]="";	//str用于保存输入小鼠，all用于存储得到的输出后缀表达式。
    	int i = 0;					//temp量
    
    	init(&p);					//初始化
    
    	printf("请输入一个算式：");
    	scanf("%c", &c);
    	while (c != '#')
    	{
        
    		while ((c <= '9' && c >= '0') || c == '.'){
        		//输入一个小数
    			str[i++] = c;
    			if (i >= 10){
        
    				printf("输入数据过大");
    				exit(1);
    			}
    			scanf("%c", &c);
    			if (!(c <= '9' && c >= '0') && c != '.'){
        
    				str[i++] = ' ';
    				str[i] = '\0';
    				strcat(all, str);
    				i = 0;
    				break;
    			}
    		}
    		if (c == '#')
    			break;
    		switch (c)								//操作符判断
    		{
        
    		case '(':
    		case '*':
    		case '/':
    			//如果遇到操作符'('、'*'、'/'，由于其优先级较高，直接进行入栈。
    			push(&p, c);
    			break;
    		case '+':
    		case '-':
    			//如果是+号或者-号，如果之前曾经将'('压入栈，则取出其与'('之间的所有操作符，不取出'('；
    			//如果之前未将'('压入栈，则取出所有操作符，因为在栈中的所有操作符的优先级都比最后一个'+'、'-'高。
    			while (p.Base != p.Top){
        		
    				e[0] = pop(&p);
    				if (e[0] == '*' || e[0] == '/' || e[0] == '+' || e[0] == '-'){
        
    					strcat(all, e);
    				}
    				else{
        
    					push(&p, e[0]);
    					break;
    				}
    			}
    			push(&p, c);
    			break;
    		case')':
    			//如果遇到操作符')'，则取出其与'('之间的所有操作符，同时取出'('。
    			while ((e[0] = pop(&p)) != '('){
        
    				strcat(all, e);
    			}
    		default:
    			break;
    		}
    		scanf("%c", &c);
    	}
    	//如果输入到达末尾，弹出所有操作符。
    	while (p.Base != p.Top){
        
    		e[0] = pop(&p);
    		strcat(all, e);
    	}
    	printf("%s", all);
    	return 0;
    }

# GITHUB下载连接 #

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

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center]: /images/20211122/a3ed696ae68c49aebf80afae827f46c5.png
[https_blog.csdn.net_weixin_44791964_article_details_97143790]: https://blog.csdn.net/weixin_44791964/article/details/97143790
[20190724174125600.png_pic_center]: /images/20211122/704531aa069244e38c209f45de213c8b.png
[1]: /images/20211122/156f939865b04e79a074c7717dc6b2e2.png
[3]: /images/20211122/d6aceeccb088457482bce1c5fa9c218c.png
[4]: /images/20211122/8df7d0acd28741c4b407e6035ef3a71c.png
[5]: /images/20211122/9750f179de12423cbf4d49bfb2790d13.png
[6]: /images/20211122/9956fb6cdf194866ae0545120cdc8a8e.png
[https_github.com_bubbliiiing_Data-Structure-and-Algorithm]: https://github.com/bubbliiiing/Data-Structure-and-Algorithm