PKU 2252-Equation Solver

問題概要

一次方程式を解け!

解法

パーサーを書いて，xの値について二分探索．

実装(Java)

import java.util.*;
import java.math.*;
import java.io.*;
import java.util.regex.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.lang.System.*;

public class Main {
	Matcher matcher;
	Boolean parse_exit;
	double Parse(String input,double y){
		Pattern p=Pattern.compile("[0-9]+|[\\+\\-\\*/\\(\\)x]");
		matcher=p.matcher(input);
		matcher.find();
		parse_exit=false;
		return Expr(y);
	}

	double Expr(double y){
		double left=Fact(y);
		while(parse_exit==false&&(matcher.group().equals("+")||matcher.group().equals("-"))){
			String op=matcher.group();
			parse_exit=!matcher.find();
			double right=Fact(y);
			if(op.equals("+")){
				left+=right;
			}else{
				left-=right;
			}
		}
		return left;
	}
	double Fact(double y){
		double left=Term(y);
		while(parse_exit==false&&matcher.group().equals("*")){
			parse_exit=!matcher.find();
			double right=Term(y);
			left*=right;
		}
		return left;
	}
	double Term(double y){
		if(matcher.group().equals("(")){
			parse_exit=!matcher.find();
			double res=Expr(y);
			parse_exit=!matcher.find();
			return res;
		}else if(matcher.group().equals("x")){
			double res=y;
			parse_exit=!matcher.find();
			return res;
		}
		double res=Double.parseDouble(matcher.group());
		parse_exit=!matcher.find();
		return res;
	}
	Scanner input;
	public static final double  EPS=1e-9;
	final double INF=1e9;
	void run(){
		int TestCase=1;
		input=new Scanner(System.in);
		while(input.hasNext()){
			String equals[]=input.next().split("=");
			printf("Equation #%d\n",TestCase++);
			double r1=Parse(equals[0],0)-Parse(equals[1],0),r2=Parse(equals[0],1)-Parse(equals[1],1);
			if(r1==r2){
				if(abs(r1)<EPS){
					printf("Infinitely many solutions.\n");
				}else{
					printf("No solution.\n");
				}
			}else{
				double low=-INF,high=INF,mid;
				for(int i=0;i<128;i++){
					mid=(low+high)/2.0;
					double tr=Parse(equals[0],mid)-Parse(equals[1],mid);
					if(r1<r2){
						if(tr<0){
							low=mid;
						}else{
							high=mid;
						}
					}else{
						if(tr>=0){
							low=mid;
						}else{
							high=mid;
						}
					}
				}
				printf("x = %.6f\n",low);
			}
			printf("\n");
		}
	}

	void printf(String format,Object... args){
		System.out.printf(format, args);
	}

	public static void main(String[] args) {
		new Main().run();
	}

}