第四届河南省程序设计大赛 ——表达式求值

深藏阁楼爱情的钟 2022-02-13 10:43 239阅读 0赞

**题目描述**

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行，每一行对应一个表达式的值。

**样例输入 Copy**

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

**样例输出 Copy**

3
 999
 200

### 这算是一个表达式求值，不过其中的运算符并不是加减乘除，而是add，min，max，也非常简单，转化一下就行 ###

### ac代码：  ###

#include<iostream>
 #include<cstdio>
 #include<cstring>
 #include<algorithm>
 #include<stack>
 using namespace std;
 int main(){
 	int n;
 	cin>>n;
 	while(n--){
 		string s;
 		stack<char> bds; //只有三种运算符，a代表add，x代表max，n代表min 
 		stack<int> num;
 		cin>>s;
 		s=s+'#'; //在尾部加上一个其他字符是为了让最后一步操作正常进行 
 		int sn=0,bj=0; //sn代表整数，bj代表当前sn是否为零 
 		for(int i=0;i<s.size();i++){
 			if(s[i]>='0'&&s[i]<='9'){
 				sn=sn*10+s[i]-'0';
 				bj=1;
 			}
 			else {
 				if(bj){ //若此时字符不为数字且sn不为零，代表上一个整数输入完毕，将其加入到num栈中 
 					bj=0;
 					num.push(sn);
 					sn=0;
 				}
 			 if(s[i]=='a'){ //这几步是判断是三种运算函数中的哪一个，并加入到字符栈中 
 			 bds.push(s[i]);
 			 i+=2;
 			 }
 			 if(s[i]=='m'){
 				 if(s[i+1]=='a'){
 				 	bds.push('x');
 					 i+=2;
 				 }else{
 					 bds.push('n');
 					 i+=2;
 				 }
 			 }
 			 if(s[i]==')'){ //若此时字符为右括号 
 			 	int t1=num.top();
 			 	num.pop();
 			 	int t2=num.top();
 			 	num.pop();
 			 	if(bds.top()=='a'){ //进行相应运算 
 			 		t1=t1+t2;				
 			 	}else if(bds.top()=='x'){
 
 			 		t1=max(t1,t2);
 			 	}else if(bds.top()=='n'){
 			 		t1=min(t1,t2);
 			 	}
 			 	num.push(t1); //将运算结果加入到num栈中 
 			 	bds.pop(); //将此运算符抛弃 
 			 }
 		 }
 		}
 		cout<<num.top()<<endl;//输出栈顶 
 	}
 	return 0;
 }