关于中缀转后缀表达式的树型算法

小鱼儿 2022-09-07 15:58 148阅读 0赞

将近两个月没刷题，编程真是一点手感都没了。昨天晚上找了这个题，虽然原来用栈做过计算器，但是这次还是花了大概3个小时来做。编程还是得多练啊。

此题是NYOJ第257题。

一开始拿到题目。我首先就是想按照栈来做。但是自己试着写了一下，但是貌似不能用计算器的那种算完式子然后入栈的方法写。本来准备网上搜解法的，但是一想到大二那种学习方法。还是犟着自己思考，然后就想到了严蔚敏书上的树型表达式，后缀表达式就是树的后序遍历。于是将两个测试画了一下，一开始还没发现什么具体的规律，但是画了两三个之后发现树根一直都是+或者-。似乎优先级越高的操作符越接近叶子，而所有叶子结点都是数字。在+ -两个运算的两边都可以是数字或者是一个表达式。但是右边的表达式优先级一定比根结点高。然后估计是不是可以用分治的方法，将左右两棵子树递归的来写。就报着这个想法开始写了。

刚开始我还没怎么考虑括号的情况，但后来边写边想就想明白了。我的算法是：

**1.如果开始的字符是单个数字，并且后面不存在操作符。那么直接生成结点并赋值。否则跳到步骤3。  
2.如果开始遇到左括号，且最后一个字符是右括号。除去括号，继续递归生成二叉树。否则那么继续步骤3。  
3.找到最右边优先级最低的操作符。生成一个结点，并且将符号放入数据区。括号内的整体当作一个数来看暂时不管。  
4.然后分别将左右两边的串，分别递归的计算。**  
  
这是很典型的分治算法了。其要点就两点：  
 **1.找到优先级最低且在最右的操作符。**

**2.将左右两边式子看作子树，递归运算得出结果。**

开始的时候没有考虑到多重括号的情况RE了几次。然后自己是试着写了个嵌套很多个的式子，问题就暴露出来了。以后还是得多想想可能的陷阱数据后再写代码吧。

代码如下：

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    typedef struct asd
    {	int a;
    	int flag;
    	struct asd * left;
    	struct asd *right;
    }node;
    
    
    void translate(char s[],int length,node **head)
    {	
    	int i;
    	int flag=0;
    	int max;
    	int kuohao;
    
    	if(s[0]>='0'&&s[0]<='9')
    	{
    		
    		for(i=0;i<length;i++)//如果需要递归计算子式
    			if(!(s[i]>='0'&&s[i]<='9'))
    				break;
    
    		if(i==length)//如果只是一个数字
    		{	*head=(node*)malloc(sizeof(node));
    			(*head)->a=atoi(s);
    			(*head)->flag=1;
    			(*head)->left=NULL;
    			(*head)->right=NULL;
    			return ;
    		}
    	}
    	if(s[0]=='('&&s[length-1]==')')//当式子只有一个整体的括号的时候
    	{
    			translate(&s[1],length-2,head);
    			return;
    	}
    
    	for(i=length-1,flag=0;i>=0;i--)//找符号位置
    	{	
    		if(s[i]=='+'||s[i]=='-')//找到最合适的符号。
    		{
    			max=i;		
    			break;
    		}
    		else if(flag==0&&(s[i]=='/'||s[i]=='*'||s[i]=='('))//
    		{		max=i;
    				flag=1;//用于标识只存在*/的式子
    		}
    		else if(s[i]=='/'||s[i]=='*'||s[i]=='(')
    			continue;		
    
    		else if(s[i]==')')
    		{	kuohao=1;
    			i--;
    			while(kuohao!=0)//为了保证多重括号嵌套的情况，简单的模拟了一个括号匹配的过程
    			{	if(s[i]==')')
    					kuohao++;
    				if(s[i]=='(')
    					kuohao--;
    				i--;
    			}
    			i++;
    		}
    	}
    
    		*head=(node *)malloc(sizeof(node));//写入符号
    		(*head)->a=s[max];
    		(*head)->flag=0;
    		translate(s,max,&((*head)->left));//递归计算左子树	
    		translate(&s[max+1],length-max-1,&((*head)->right));//递归计算右子树
    	
    }
    
    void houxu(node *head)//后序遍历整棵树
    {	if(head==NULL)
    		return;
    	houxu(head->left);
    	houxu(head->right);
    	if(head->flag==1)
    		printf("%d",head->a);
    	else
    		printf("%c",head->a);
    }
    
    int main()
    {
    	int t;
    	char get[1010];
    	node *head;
    	freopen("test.txt","r",stdin);
    	scanf("%d",&t);
    	while(t--)
    	{	scanf("%s",get);
    		translate(get,strlen(get),&head);
    		houxu(head);
    		printf("\n");
    	}
    }