NYOJ 305-表达式求值【模拟】

叁歲伎倆 2022-07-26 05:18 207阅读 0赞

## 表达式求值 ##

时间限制： 3000 ms | 内存限制： 65535 KB

难度： 3

描述

Dr.Kong设计的机器人卡多掌握了加减法运算以后，最近又学会了一些简单的函数求值，比如，它知道函数min(20,23)的值是20 ，add(10,98) 的值是108等等。经过训练，Dr.Kong设计的机器人卡多甚至会计算一种嵌套的更复杂的表达式。

假设表达式可以简单定义为:

1. 一个正的十进制数 x是一个表达式。

2. 如果 x 和 y 是表达式，则 函数min(x,y )也是表达式,其值为x,y 中的最小数。

3. 如果 x 和 y 是表达式，则 函数max(x,y )也是表达式,其值为x,y 中的最大数。

4．如果 x 和 y 是表达式，则 函数add(x,y )也是表达式,其值为x,y 之和。

例如，表达式 max(add(1,2),7) 的值为 7。

请你编写程序，对于给定的一组表达式，帮助 Dr.Kong 算出正确答案，以便校对卡多计算的正误。

输入

第一行： N 表示要计算的表达式个数 （1≤ N ≤ 10）  
接下来有N行， 每行是一个字符串，表示待求值的表达式  
（表达式中不会有多余的空格，每行不超过300个字符，表达式中出现的十进制数都不  
超过1000。）

输出

输出有N行，每一行对应一个表达式的值。

样例输入

3
    add(1,2) 
    max(1,999) 
    add(min(1,1000),add(100,99))

样例输出

3
    999
    200

来源

[第四届河南省程序设计大赛][Link 1]

上传者

[张云聪][Link 2]

<pre name="code" class="cpp">#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    #include<vector>
    using namespace std;
    char map[3000];
    int nn[3000];
    struct node
    {
    	int ji;//操作符的级别 
    	int c;//操作符 0+ 1小 2大 
    };
    struct node1
    {
    	int jii;
    	int numm;
    };
    int main()
    {
    	int T;
    	scanf("%d",&T);
    	while(T--)
    	{
    		vector<node >cc;
    		vector<node1 >shu;
    		vector<node1 >fu;
    		vector<node >fu1;
    		scanf("%s",map);
    		int wc=0;
    		int len=strlen(map);
    		int i,j;
    		int num1;
    		node aa;
    		int maxji=-1;
    		int con=0;
    		for(i=0;i<len;i++)
    		{
    			if(map[i]=='(')
    			{
    				wc++;
    				if(map[i-1]=='d')
    				{
    					aa.ji=wc;
    					aa.c=0;	
    				}
    				if(map[i-1]=='n')
    				{
    					aa.ji=wc;
    					aa.c=1;
    				}
    				if(map[i-1]=='x')
    				{
    					aa.ji=wc;
    					aa.c=2;
    				}
    				if(wc>maxji)
    				{
    					maxji=wc;
    				}
    				cc.push_back(aa);
    			}
    			if(map[i]==')')
    			{
    				wc--;
    			}
    			if(map[i]==',')
    			{
    				con=0;
    			}
    			if(map[i]>='0'&&map[i]<='9'&&con==0)
    			{
    				node1 u2;
    				int k=i;
    				num1=0;
    				con=1;
    				while(map[k]>='0'&&map[k]<='9')
    				{
    					num1=num1*10+(map[k]-'0');
    					k++;
    				}
    				u2.jii=wc;
    				u2.numm=num1;
    				shu.push_back(u2);
    			}
    			
    		}
    		if(cc.size()==0)
    		{
    			node1 kl;
    			kl=shu.front();
    			printf("%d\n",kl.numm);
    		}
    		else
    		{
    			node bb; 
    			int uu;
    			while(cc.size()!=0)
    			{
    				uu=cc.size();
    				for(i=uu-1;i>=0;i--)
    				{
    					if(cc[i].ji==maxji)
    					{
    						for(j=shu.size()-1;j>=0;j--)
    						{
    							node1 zx=shu.back();
    							if(zx.jii==maxji)
    							{
    								shu.pop_back();
    								node1 zc;
    								zc=shu.back();
    								shu.pop_back();
    								if(cc[i].c==0)
    								{
    									zx.numm=zx.numm+zc.numm;
    								}	
    								if(cc[i].c==1)
    								{
    									zx.numm=min(zx.numm,zc.numm);
    								}	
    								if(cc[i].c==2)
    								{
    									zx.numm=max(zx.numm,zc.numm);
    								}	
    								zx.jii=zx.jii-1;
    								fu.push_back(zx);
    								break;
    							}
    							else
    							{
    								shu.pop_back();
    								fu.push_back(zx);
    							}
    						}
    					}
    					else
    					{
    						node pp;
    						pp=cc[i];
    						fu1.push_back(pp);
    					}
    				}
    				shu.clear();
    				cc.clear();
    				while(fu.size()!=0)
    				{
    					node1 hh=fu.back();
    					fu.pop_back();
    					shu.push_back(hh);
    				}
    				while(fu1.size()!=0)
    				{
    					node h1;
    					h1=fu1.back();
    					fu1.pop_back();
    					cc.push_back(h1);
    				}
    				maxji--;
    			}
    			node1 jio;
    			jio=shu.front();
    			printf("%d\n",jio.numm);
    		}
    	}
    	return 0;
    }

[Link 1]: http://acm.nyist.net/JudgeOnline/search_result.php?source=%E7%AC%AC%E5%9B%9B%E5%B1%8A%E6%B2%B3%E5%8D%97%E7%9C%81%E7%A8%8B%E5%BA%8F%E8%AE%BE%E8%AE%A1%E5%A4%A7%E8%B5%9B
[Link 2]: http://acm.nyist.net/JudgeOnline/profile.php?userid=%E5%BC%A0%E4%BA%91%E8%81%AA