1412 Equals are Equals

「1412 Equals are Equals」の編集履歴（バックアップ）一覧はこちら

「1412 Equals are Equals」(2006/04/16 (日) 23:10:01) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

**1412 Equals are Equals
**問題
http://acm.pku.edu.cn/JudgeOnline/problem?id=1412
**解答方針
構文解析については[[1460 Firefighters]]と基本的には同じ．
**解答例
 import java.util.*;
 
 public class Main {
     public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
         while(true){
             String ans = sc.nextLine();
             if(ans.equals(".")) break;
             Polynomial anspoly = (new Evaluator(ans)).evaluate();
             while(true){
                 String sample = sc.nextLine();
                 if(sample.equals(".")) break;
                 Polynomial samplepoly = (new Evaluator(sample)).evaluate();
                 if(anspoly.equivalent(samplepoly)) System.out.println("yes");
                 else System.out.println("no");
             }
             System.out.println(".");
         }
     }
 }
 
 class Evaluator{
     String str;
     int size;
     int c;
     Evaluator(String s){
         str = s.concat("$");
         size = s.length();
         c = 0;
     }
     public Polynomial evaluate(){
         return expr();
     }
     private Polynomial expr(){
         Polynomial ret = term();
         while(true){
             while(str.charAt(c)==' ') c++;
             if(str.charAt(c)=='+'){
                 c++;
                 ret = ret.plus(term());
             }
             else if(str.charAt(c)=='-'){
                 c++;
                 ret = ret.minus(term());
             }
             else if(str.charAt(c)==')'||str.charAt(c)=='$'){
                 break;
             }
             else{
                 //
             }
         }
         return ret;
     }
     private Polynomial term(){
         Polynomial ret = factor();
         while(true){
             while(str.charAt(c)==' ') c++;
             if(str.charAt(c)=='+'||str.charAt(c)=='-'||
                     str.charAt(c)==')'||str.charAt(c)=='$'){
                 break;
             }
             else{
                 ret = ret.mul(factor());
             }
         }
         return ret;
     }
     private Polynomial factor(){
         while(str.charAt(c)==' ') c++;
         if(str.charAt(c)=='('){
             c++;
             Polynomial ret = expr();
             c++;
             return ret;
         }
         else{
             if('0'<=str.charAt(c)&&str.charAt(c)<='9'){
                 int retnum = num();
                 Polynomial ret = new Polynomial(retnum);
                 return ret;
             }
             else{
                 Polynomial ret = atom();
                 return ret;
             }
         }
     }
     private int num(){
         int retnum = 0;
         while('0'<=str.charAt(c)&&str.charAt(c)<='9'){
             retnum = retnum*10 + (str.charAt(c)-'0');
             c++;
         }
         return retnum;
     }
     private Polynomial atom(){
         char v = str.charAt(c);
         c++;
         while(str.charAt(c)==' ') c++;
         if(str.charAt(c)=='^'){
             c++;
             while(str.charAt(c)==' ') c++;
             int k = num();
             return new Polynomial(v,k);
         }
         else{
             return new Polynomial(v,1);
         }
     }
 }
 
 class Polynomial{
     TreeSet<Term> terms;
     public Polynomial(){
         terms = new TreeSet<Term>();
     }
     public Polynomial(int x){
         terms = new TreeSet<Term>();
         if(x!=0) terms.add(new Term(x));
     }
     public Polynomial(char v,int k){
         terms = new TreeSet<Term>();
         terms.add(new Term(v,k));
     }
     public Polynomial(Polynomial p){
         terms = new TreeSet<Term>(p.terms);
     }
     public boolean equivalent(Polynomial p){
         Polynomial p1 = new Polynomial(this);
         Polynomial p2 = new Polynomial(p);
         Polynomial sub = p1.minus(p2);
         return sub.terms.isEmpty();
     }
     public void add(Term t){
         if(terms.contains(t)){
             Term s = terms.tailSet(t).first();
             Term c = s.contract(t);
             terms.remove(s);
             if(c.coefficient!=0)terms.add(c);
         }
         else terms.add(t);
     }
     public Polynomial mul(Polynomial p){
         Polynomial ret = new Polynomial();
         for(Term t:this.terms){
             for(Term s:p.terms){
                 ret.add(t.mul(s));
             }
         }
 
         return ret;
     }
     public Polynomial plus(Polynomial p){
         Polynomial ret = new Polynomial();
         for(Term t:this.terms) ret.add(t);
         for(Term t:p.terms) ret.add(t);
         
         return ret;
     }
     public Polynomial minus(Polynomial p){
         Polynomial ret = new Polynomial();
         for(Term t:this.terms) ret.add(t);
         for(Term t:p.terms) ret.add(t.neg());
         
         return ret;
     }
 }
 
 class Term implements Comparable<Term>{
     int coefficient;
     int pow[] = new int[26];
     
     public boolean equals(Object o){
         Term t = (Term)o;
         for(int i=0;i<26;i++){
             if(this.pow[i]!=t.pow[i]) return false;
         }
         return true;
     }
     
     public int compareTo(Term t){
         for(int i=0;i<26;i++){
             if(this.pow[i]!=t.pow[i]) return this.pow[i]-t.pow[i];
         }
         return 0;
     }
     
     //integer x
     public Term(int x){
         coefficient = x;
         for(int i=0;i<26;i++) pow[i] = 0;
     }
     
     //term a^k
     public Term(char v,int k){
         coefficient = 1;
         for(int i=0;i<26;i++) pow[i] = 0;
         pow[v-'a'] = k;
     }
     
     public Term mul(Term t){
         Term ret = new Term(0);
         for(int i=0;i<26;i++) ret.pow[i] = this.pow[i]+t.pow[i];
         ret.coefficient = this.coefficient*t.coefficient;
         return ret;
     }
     
     public boolean contractable(Term t){
         Term ret = new Term(0);
         for(int i=0;i<26;i++){
             if(this.pow[i]!=t.pow[i]) return false;
         }
         return true;
     }
     
     public Term contract(Term t){
         Term ret = new Term(0);
         for(int i=0;i<26;i++) ret.pow[i] = this.pow[i];
         ret.coefficient = this.coefficient + t.coefficient;
         return ret;
     }
     
     public Term neg(){
         Term ret = new Term(0);
         for(int i=0;i<26;i++) ret.pow[i] = this.pow[i];
         ret.coefficient = -this.coefficient;
         return ret;
     }
 }