百度的科学计算器（解题报告）

ゞ浴缸里的玫瑰 2022-06-15 02:58 211阅读 0赞

题目来自计蒜客

今年，百度的科学计算器进行了重大更新，可以计算更为复杂的表达式了。

定义表达式中存在加减运算、括号、函数调用、强制类型转换这几种运算。其中数值的类型有整型与浮点型两种。并且，

*  整型与整型加减运算的结果为整型；
 *  整型与浮点型加减运算结果为浮点型；
 *  浮点型与浮点型加减运算结果为浮点型。

**强制类型转换符** 包括`int(x)`与`float(x)`，其中`float(x)`运算符可以将数值`x`的类型强制转为浮点型，`int(x)`运算符可以将数值`x`的类型强制转为整型。对于浮点型转整型，采用截尾法，例如：`int(1.6)=1`，`int(-1.6)=-1`等等。

例如，

*  `int(10.9999)=10`；
 *  `float(10)=10.000000`；
 *  `int(10.9999)+float(1)=11.000000`；
 *  `int(1.0)+(100-40)=61`。

除此以外，还可以定义一系列函数，形如：

*  `fun(x,y)=x+y+fun2(y)`
 *  `fun2(x)=fun3()+int(x)`
 *  `fun3()=61`

函数的变量名和函数名均由一个或多个大小写字母以及数字组成，并且由大小写字母开头。保证：变量名与函数名不为`int`或`float`；同一函数的不同参数的参数名互不相同；函数名互不相同。函数参数不超过两个，函数之间可能存在相互调用关系，相互调用传参时，各个参数保证均为单一变量（既不是表达式也不是数字常量）。例如`f1(x,y)=f2(y,x)+f3(x)+f4()`是合法的，而`f(x)=f2(x+x)+f3(61)`是不合法的（因为函数相互调用时参数不为表达式或数字常量）。

对于给定表达式，百度的科学计算器需要算出该表达式的结果。

### 输入格式 ###

第一行输入一个整数 n(0≤n≤1000)n (0 \\le n \\le 1000)n(0≤n≤1000)，表示有 nnn 个函数。

接下来一共输入 n+1n+1n\+1 行，对于前 nnn 行，每行一个字符串，分别代表 nnn 个函数，每个函数长度均不超过 505050 个字符，字符串中只包含加号`+`、减号`-`、括号`()`、数字常量、强制类型转换以及函数调用。输入数据保证所有表达式合法，**表达式中没有空格**。

最后一行为一个表达式，表示需要求解的表达式，表达式长度不超过 100010001000，并且这一表达式中出现函数调用的次数不超过 333 次。

输入数据保证数字常量以及计算过程中数值绝对值均不超过 101210^\{12\}1012，对于浮点型数值常量，保证小数点后不超过 666 位。

输入数据保证求解表达式及函数表达式出现的数字常量均为非负数，但计算中间结果不一定非负。

对于简单版本：n=0n=0n=0，在满足题意前提下，求解表达式中不存在强制类型转换`int()`、`float()`及函数调用；

对于中等版本：n≤3n \\le 3n≤3，在满足题意前提下，函数之间不存在相互调用的情况。函数的参数数量均为 111；

对于困难版本：满足上述题意中的条件，没有额外的限制。

### 输出格式 ###

输出为一行，即表达式结果，对于浮点型结果，保留到小数点后 666 位。对于表达式无法求解的情况（例如循环调用），给出`No Answer`。

#### 样例输入1 ####

0
    5.0-(4-5.1)

#### 样例输出1 ####

6.100000

#### 样例输入2 ####

3
    func1(x)=x+1
    func2(y)=y+1
    func3(z)=z+int(1.9)
    func1(1)+func2(1)+func3(1)

#### 样例输出2 ####

#### 样例输入3 ####

2
    Haha(x)=Haha1(x)
    Haha1(a)=Haha(a)
    Haha(61)

#### 样例输出3 ####

No Answer

简单版本代码：中缀转后缀，计算逆波兰式的表达式的值。读取的时候注意用Long存储整数，输出时注意格式。

tip:读入串的时候可以手动添加分隔符用于分隔数字和运算符。

package jisuanzhidao.chusai2;
    
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.Stack;
    
    public class Two {
    
    	public static void main(String[] args) throws IOException{
    		// TODO Auto-generated method stub
    		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    		String line=null;
    		line=br.readLine();
    		int n=Integer.parseInt(line);
    		if(n!=0){
    			String [] fs=new String[n];
    			for(int i=0;i<n;++i){
    				fs[i]=br.readLine();
    			}
    		}
    		
    		String expression=br.readLine();
    		if(expression.charAt(0)=='-'){
    			expression="0"+expression;
    		}
    		else{
    			boolean flag=false;
    			for(int i=0;i<expression.length();++i){
    				if(flag){
    					if(expression.charAt(i)=='-'){
    						String s1=expression.substring(0, i);
    						String s2=expression.substring(i);
    						expression=s1+"0"+s2;
    					}
    				}
    				if(expression.charAt(i)=='('){
    					flag=true;
    				}
    				else{
    					break;
    				}
    				
    			}
    		}
    		
    		String s1=inToLast(expression);
    		
    		System.out.println(calLast(s1));
    		
    	}
    	
    	public static String calLast(String s){
    		String [] strs=s.split("#");
    		Stack<String> stack=new Stack<String>();
    		for(int i=0;i<strs.length;++i){
    			if(strs[i].equals("+")){
    				boolean f1=false,f2=false;
    				Long la=0l;
    				Long lb=0l;
    				Double da=0.0;
    				Double db=0.0;
    				try {
    					la=Long.parseLong(stack.peek());
    				} catch (NumberFormatException e) {
    					// TODO Auto-generated catch block
    					da=Double.parseDouble(stack.peek());
    					f1=true;
    				}
    				stack.pop();
    				try {
    					lb=Long.parseLong(stack.peek());
    				} catch (NumberFormatException e) {
    					// TODO Auto-generated catch block
    					db=Double.parseDouble(stack.peek());
    					f2=true;
    				}
    				stack.pop();
    				if(f1==false&&f2==false){
    					stack.push((la+lb)+"");
    				}
    				else if(f1==true&&f2==false){
    					Double ans=(da+lb);
    					stack.push(String.format("%1$.6f",ans));
    				}
    				else if(f1==false&&f2==true){
    					Double ans=(la+db);
    					stack.push(String.format("%1$.6f",ans));
    				}
    				else{
    					Double ans=(da+db);
    					stack.push(String.format("%1$.6f",ans));
    				}
    			}
    			else if(strs[i].equals("-")){
    				boolean f1=false,f2=false;
    				Long la=0l;
    				Long lb=0l;
    				Double da=0.0;
    				Double db=0.0;
    				try {
    					lb=Long.parseLong(stack.peek());
    				} catch (NumberFormatException e) {
    					// TODO Auto-generated catch block
    					db=Double.parseDouble(stack.peek());
    					f2=true;
    				}
    				stack.pop();
    				try {
    					la=Long.parseLong(stack.peek());
    				} catch (NumberFormatException e) {
    					// TODO Auto-generated catch block
    					da=Double.parseDouble(stack.peek());
    					f1=true;
    				}
    				stack.pop();
    				if(f1==false&&f2==false){
    					stack.push((la-lb)+"");
    				}
    				else if(f1==true&&f2==false){
    					Double ans=(da-lb);
    					stack.push(String.format("%1$.6f",ans));
    				}
    				else if(f1==false&&f2==true){
    					Double ans=(la-db);
    					stack.push(String.format("%1$.6f",ans));
    				}
    				else{
    					Double ans=(da-db);
    					stack.push(String.format("%1$.6f",ans));
    				}
    			}
    			else{
    				stack.push(strs[i]);
    			}
    		}
    		return stack.pop();
    		
    	}
    	
    	public static String inToLast(String s){
    		char [] chs=s.toCharArray();
    		Stack<Character> stack=new Stack<Character>();
    		StringBuilder sb=new StringBuilder();
    		for(int i=0;i<chs.length;++i){
    			if(chs[i]=='('){
    				stack.push('(');
    			}
    			else if(chs[i]==')'){
    				while(!stack.isEmpty()&&(stack.peek()!='(')){
    					sb.append('#');
    					sb.append(stack.pop());
    				}
    				if(!stack.isEmpty()){
    					stack.pop();
    				}
    			}
    			else if(chs[i]=='+'){
    				sb.append('#');
    				while(!stack.isEmpty()&&stack.peek()!='('){
    					sb.append('#');
    					sb.append(stack.pop());
    				}
    				sb.append('#');
    				stack.push('+');
    			}
    			else if(chs[i]=='-'){
    				sb.append('#');
    				while(!stack.isEmpty()&&stack.peek()!='('){
    					sb.append('#');
    					sb.append(stack.pop());
    				}
    				sb.append('#');
    				stack.push('-');
    				
    			}
    			else{
    				sb.append(chs[i]);
    			}
    		}
    		while(!stack.isEmpty()){
    			sb.append('#');
    			sb.append(stack.pop());
    		}
    		return sb.toString().replaceAll("#+", "#");
    	}
    
    }