AOJ1233 Equals are Equals

問題リンク Equals are Equals

• 概要

多項式Pが与えられる。更に多項式のリストLが与えられるので、これらがPと同値かを判定せよ。
多項式の変数には'a'-'z'が使われる。そのほかは'0'-'9', '(',')', '^', ' ', '+', '-' の文字のみが登場する。
'+', '-'は2項演算子であり、単項演算子として登場することはない。
多項式中に登場する空白は、読みやすさのための空白と、隣り合う整数を区分するためにある。
変数シンボルの後ろに'^'と1桁の0でない整数が続くことがある。
係数はどんなときでも10^9に収まる。また変数の指数部は10に収まる。

• 解法

まず、多項式をクラスとしました。
変数はx, x^2, ab^2c^3など複雑になりうるので辞書順でソートした文字列として表現します。(他に方法があるのかは分かりません)
ex) x^2→"xx", ab^2c^3→"abbccc", ac^3b^2→"abbccc"
この文字列を変数Xとし、Mapで管理します。x^2の係数が欲しければmap.get("xx")という具合です。
それと、定数項c0を持ちます。
2つの多項式クラスp1, p2に対して、和と差と積とべき乗の計算をメソッドとして作ります。
更に、多項式同士を比較するeq()も作っておきます。mapが返す値はIntegerオブジェクトなので係数の比較にはequals()を使いましょう。
次に構文解析の部分についてです。例によってBFSを作ってみます。正確な表記ではないのでノリを感じてください。
Exp = Term '+' Exp | Term '-' Exp | Term
Term = Fact + {0個以上の空白 + Fact}
Fact = 'a'-'z' ('^' + '1'-'9') | 整数 | '(' Exp ')'
あとはこれをメソッドの形で実装します。空白を飛ばして次の文字トークンを取得するメソッドと、直後の文字トークンを取得するメソッドの2つを使い分ける必要があると思います。

• ソース

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

//Equals are Equals
public class AOJ1233 {

	char[] s;
	int id;
	
	class P{
		Map<String, Integer> c;
		int c0;
		public P() {
			c = new HashMap<String, Integer>();
			c0 = 0;
		}
		boolean eq(P p){
			if(c.size()!=p.c.size()||c0!=p.c0)return false;
			for(String t:c.keySet())if(!p.c.containsKey(t)||!c.get(t).equals(p.c.get(t)))return false;
			return true;
		}
		P add(P p){
			P r = new P();
			for(String t:c.keySet()){
				if(p.c.containsKey(t))r.c.put(t, c.get(t)+p.c.get(t));
				else r.c.put(t, c.get(t));
			}
			for(String t:p.c.keySet()){
				if(!c.containsKey(t))r.c.put(t, p.c.get(t));
			}
			r.c0 = c0+p.c0;
			Set<String> set = new HashSet<String>();
			for(String t:r.c.keySet())if(r.c.get(t)==0)set.add(t);
			for(String t:set)r.c.remove(t);
			return r;
		}
		P sub(P p){
			P r = new P();
			for(String t:c.keySet()){
				if(p.c.containsKey(t))r.c.put(t, c.get(t)-p.c.get(t));
				else r.c.put(t, c.get(t));
			}
			for(String t:p.c.keySet()){
				if(!c.containsKey(t))r.c.put(t, -p.c.get(t));
			}
			r.c0 = c0-p.c0;
			Set<String> set = new HashSet<String>();
			for(String t:r.c.keySet())if(r.c.get(t)==0)set.add(t);
			for(String t:set)r.c.remove(t);
			return r;
		}
		P mul(P p){
			P r = new P();
			for(String s:c.keySet())for(String t:p.c.keySet()){
				char[] x = (s+t).toCharArray();
				Arrays.sort(x);
				String v = new String(x);
				if(r.c.containsKey(v))r.c.put(v, r.c.get(v)+c.get(s)*p.c.get(t));
				else r.c.put(v, c.get(s)*p.c.get(t));
			}
			for(String s:c.keySet()){
				if(r.c.containsKey(s))r.c.put(s, r.c.get(s)+p.c0*c.get(s));
				else r.c.put(s, p.c0*c.get(s));
			}
			for(String s:p.c.keySet()){
				if(r.c.containsKey(s))r.c.put(s, r.c.get(s)+c0*p.c.get(s));
				else r.c.put(s, c0*p.c.get(s));
			}
			r.c0 += c0*p.c0;
			Set<String> set = new HashSet<String>();
			for(String t:r.c.keySet())if(r.c.get(t)==0)set.add(t);
			for(String t:set)r.c.remove(t);
			return r;
		}
		P pow(int k){
			P r = new P();
			r.c0 = 1;
			while(k--!=0)r = r.mul(this);
			return r;
		}
		@Override
		public String toString() {
			String r = "";
			for(String t:c.keySet())r+=" "+c.get(t)+t;
			r+=" "+c0;
			return r;
		}
	}
	
	char get(){
		return s[id++];
	}
	char next(){
		while(s[id]==' ')id++;
		return s[id++];
	}
	
	P exp(){
		P r = term();
		char ch = next(); 
		while(ch=='+'||ch=='-'){
			P f = term();
			if(ch=='+')r = r.add(f);
			else r = r.sub(f);
			ch = next();
		}
		id--;
		return r;
	}
	
	P term(){
		P r = fact();
		char ch = next();
		while(Character.isDigit(ch)||Character.isLowerCase(ch)||ch=='('){
			id--;
			P f = fact();
			r = r.mul(f);
			ch = next();
		}
		id--;
		return r;
	}
	
	P fact(){
		char ch = next();
		P r = new P();
		if(ch=='('){
			r = exp();
			next();
		}
		else if(Character.isLowerCase(ch))r.c.put(ch+"", 1);
		else if(Character.isDigit(ch)){
			int x = ch-'0';
			for(;;){
				ch = get();
				if(!Character.isDigit(ch)){
					id--;break;
				}
				x = x*10 + ch-'0';
			}
			r.c0 = x;
		}
		ch = next();
		while(ch=='^'){
			int x = next()-'0';
			r = r.pow(x);
			ch = next();
		}
		id--;
		return r;
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			s = (sc.nextLine()+"$").toCharArray();
			if(s[0]=='.')break;
			id = 0;
			P ans = exp();
			for(;;){
				s = (sc.nextLine()+"$").toCharArray();
				if(s[0]=='.')break;
				id = 0;
				P p = exp();
				System.out.println(ans.eq(p)?"yes":"no");
			}
			System.out.println(".");
		}
	}
	
	public static void main(String[] args) {
		new AOJ1233().run();
	}
}