TOJ1092 More Beautiful

一时失言乱红尘 2022-05-30 10:22 165阅读 0赞

描述

当老师不容易，尤其是当小学的老师更难:现在的小朋友做作业喜欢滥用括号。  
虽然不影响计算结果，但不够美观，容易出错，而且可读性差。但又不能一棒子打死，也许他们就是将来的“陈景润”呢！  
为了减轻老师的工作，不至于他们工作到深夜，我们来写个程序把小朋友的作业做一下简单地处理，去掉那些多余的括号。  
为了简化问题，所有式子里只存在小括号，运算符号包括+(加)、-(减)、\*(乘)、/(除)、^(幂)。  
注意：去掉多余的小括号不是指运算结果一样就可以。  
比如：(1+2)^1 = 3。虽然把括号去掉1+2^1也等于3，但我们说这个括号不能去。  
但如：1+(2+3) = 1+2+3只要是允许的，因为加法是满足交换律和结合律的。

输入

输入包括多组测试数据。  
每组测试数据为一行算术表达式，只包括正整数和运算符号，长度小于16。  
输入以\#行结束，该行不做处理。

输出

对应每组数据输入都有一行输出。  
输出去掉多余的括号后的表达式。

样例输入

2\*(1\*(4\*3))  
3\*(2\*(4/1))  
((4\*2)/1)\*3  
(1)+(2)+(3)+(4)  
1-(2-(3-4))  
((3\*2)\*4)^1

样例输出

2\*1\*4\*3  
3\*2\*4/1  
4\*2/1\*3  
1+2+3+4  
1-(2-(3-4))

(3\*2\*4)^1

惨兮兮，这道题做了好几天，考虑四则运算到怀疑自己小学数学了...

参考了黄大佬的写了一次也GG了，后来发现变量要开在全局，放main里都不行，大概是因为放全局他会自动清空吧..

#include<stdio.h>
    #include<string.h>
    int i,j,b,f[50],yxj[500],p[50],y[50],o;
    //f标记是否删除 p标记括号位置 yxj优先级 y代表括号的优先级 
    char s[50];
    int main()
    {	
    	//yxj['+']=0,//默认的 
    	yxj['-']=1,yxj['*']=2,yxj['/']=3,yxj['^']=4;
    	while(scanf("%s",s))
    	{						
    		if(s[0]=='#')break;
    		memset(f,0,sizeof f);
    		memset(y,0,sizeof y);
    		b=strlen(s);
    		p[0]=0;o=1;
    		for(i=0;i<b;i++)
    		{
    			if(s[i]=='(')
    			p[o++]=i;
    			else if(s[i]==')')
    			{
    				o--;
    				if((y[o-1]<y[o]||y[o-1]==y[o]&&(y[o]==0||y[o]==2))&&(y[o]>=yxj[s[i+1]]||y[o]==2&&yxj[s[i+1]]==3))
    				{ 
    					f[i]=f[p[o]]=1;//去括号 
    					y[o]=0;
    				} 
    			}
    			else if(yxj[s[i]]>y[o-1])
    			y[o-1]=yxj[s[i]];
    		}
    		for(i=0;i<b;i++)
    		{
    			if(f[i]==0)
    			printf("%c",s[i]);
    		}
    		printf("\n");
    	}
    }

再贴一个姚学姐的.. 递归做的...

#include<stdio.h>
    #include<string.h>
    char s[100];
    int isdel(int left,int right)
    {
    	int leftct,index;
    	int f=0,f1=0,f2=0,a=0,b=0;
    	if(s[left-1]=='-')
    	a=1;
    	if(s[left-1]=='+')
    	a=2;
    	if(s[left-1]=='*')
    	a=3;
    	if(s[left-1]=='/')
    	a=4;
    	if(s[left-1]=='^')
    	a=5;
    	if(s[right+1]=='-')
    	b=1;
    	if(s[right+1]=='+')
    	b=2;
    	if(s[right+1]=='*')
    	b=3;
    	if(s[right+1]=='/')
    	b=4;
    	if(s[right+1]=='^')
    	b=5;
    	for(int i=left+1;i<right;i++)
    	{
    		if(s[i]=='[')
    		{
    			while(s[++i]!=']');
    		}
    		
    		if(s[i]=='-'||s[i]=='+')
    		f=1; 
    		if(s[i]=='*'||s[i]=='/')
    		f1=1;
    		if(s[i]=='^')
    		f2=1;
    	}
    	if(!f&&!f1&&!f2)return 1; 
    	if(f&&(a==0||a==2)&&(b<=2))return 1;
    	if(!f&&f1&&(a<=3)&&(b<=4))return 1;
    	if(!f&&!f1&&f2)return 1;
    	if(a==1&&f||(a==4&&(f||f1)))return 0;
    	return 0;
    }
    int del(int index)
    {
    	int left,right;
    	while(s[index]!='\0') 
    	{
    		if(s[index]==')')
    		return index;
    		if(s[index]=='(')
    		{
    			left=index;
    			index=right=del(index+1);
    			if(isdel(left,right))
    			{
    				s[left]=' ';
    				s[right]=' ';
    			}
    			else
    			{
    				s[left]='[';
    				s[right]=']';
    			}
    		}
    		index++;
    	}
    }
    int main()
    {
    	
    	while(scanf("%s",s),strcmp(s,"#")!=0)
    	{
    		del(0);
    		for(int i=0;s[i]!='\0';i++)
    		{
    			if(s[i]!=' ')
    			{
    				if(s[i]=='[')
    				printf("(");
    				else if(s[i]==']')
    				printf(")");
    				else
    				printf("%c",s[i]);
    			}
    		}
    		printf("\n");
    	}
    }