package com.learn.algorithm.ploy;

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;


/**
 *多项式 相关 运算
 */
public class Ploy {
	
	public static void main(String[] args) {
		
		List<Node> La = init();
		List<Node> Lb = init();
		
		System.out.println(polyMulti(La,Lb));
	}

	
	private static List<Node> init() {
		List<Node> poly = new LinkedList<Node>();
		Scanner sc = new Scanner(System.in);
		
		System.out.println("请输入 系数和参数(例如  a,b 表示 aX^b,输入  0,0  结束。)：");
		while (true) {
			String line = sc.nextLine();
			if ( vaildate(line) ){
				String[] split = line.split(",");
				
				int coefficient = Integer.parseInt(split[0]);
				int exponential = Integer.parseInt(split[1]);
				
				if(coefficient == 0 && exponential == 0){
					break;
				}
				
				poly.add(new Node(coefficient, exponential));
			} else {
				System.out.println("[" + line + "]输入有误");
			}
		}
		System.out.println(poly);
		return poly;
	}
	
	
	
	/**
	 * 多项式加法
	 * @param La
	 * @param Lb
	 * @return
	 */
	public static List<Node> polyPlus(List<Node> La,List<Node> Lb){
		List<Node> Lc = new LinkedList<>();
		
		int Sa = La.size(),Sb=Lb.size(),ia=0,ib=0;
		
		while( ia < Sa && ib < Sb ){
			
			if ( La.get(ia).getExponential()< Lb.get(ib).getExponential()){
				Lc.add(La.get(ia));
				ia ++ ;
			} else if( La.get(ia).getExponential() == Lb.get(ib).getExponential() ){
				
				 int coe = La.get(ia).getCoefficient() + Lb.get(ib).getCoefficient();
				if( coe != 0 ){
					Lc.add(new Node(coe,La.get(ia).getExponential()));
				}
				ia ++ ;
				ib ++;
				
			} else {
				Lc.add(Lb.get(ib));
				ib ++;
			}
		}
		
		while (ia < Sa) {
			Lc.add( La.get(ia++) );
		}
		while (ib < Sb) {
			Lc.add( Lb.get(ib++) );
		}
		
		return Lc ;
		
	}
	/**
	 * 多项式加法(无序)
	 * @param La
	 * @param Lb
	 * @return
	 */
	public static List<Node> polyPlus_update(List<Node> La,List<Node> Lb){
		
		int Sa = La.size(),Sb=Lb.size(),ia=0,ib=0;
		
		while( ia < Sa ){
			
			Node node = La.get(ia);
			
			Node nodeByExp = getNodeByExp( Lb,node.getExponential() );
			
			if (nodeByExp != null) {
				if (node.getCoefficient() + nodeByExp.getCoefficient() == 0) {
					Lb.remove(nodeByExp);
				} else{
					nodeByExp.setCoefficient( node.getCoefficient() + nodeByExp.getCoefficient() );
				}
			} else {
				Lb.add(node);
			}
			ia ++;
		}
		
		
		return Lb ;
		
	}
	
	/**
	 * 多项式乘法
	 * @param La
	 * @param Lb
	 * @return
	 */
	public static List<Node> polyMulti(List<Node> La,List<Node> Lb){
		List<Node> Lc = new LinkedList<>();
		int Sa = La.size(),Sb=Lb.size(),ia=0,ib=0;
		
		while( ia < Sa ){
			
			ib = 0;
			
			Node Na = La.get(ia);
			
			while (ib < Sb) {

				Node Nb = Lb.get(ib);
				
				int exp = Nb.getExponential() + Na.getExponential();//指数相加
				int coe = Nb.getCoefficient() * Na.getCoefficient();//系数相乘
				
				Node nodeByExp = getNodeByExp( Lc, exp);
				
				if (nodeByExp != null) {
					if (coe + nodeByExp.getCoefficient() == 0) {
						Lc.remove(nodeByExp);
					} else{
						nodeByExp.setCoefficient( coe+ nodeByExp.getCoefficient() );
					}
				} else {
					Lc.add(new Node(coe,exp));
				}
				ib ++ ;
			}
			
			ia ++;
		}
		
		
		return Lc ;
		
	}
	
	
	
	
	/**
	 * 根据系数 寻找对应的项，没有则返回null
	 * @param p
	 * @param exp
	 * @return
	 */
	public static Node getNodeByExp(List<Node> p,Integer exp){
		if (exp == null || p == null ){
			return null;
		}
		
		for (Node node : p) {
			if (node.exponential == exp) {
				return node;
			}
		}
		return null;
		
	}
	
	
	/**
	 * 验证输入字符串的合法性
	 * @param s
	 * @return
	 */
	public static boolean vaildate(String s){
		return s.matches("[-]{0,1}[0-9]+[,]{1}[0-9]+");
	}
}


/**实体类
 * 
 */
class Node {

	Integer coefficient =0; //系数
	Integer exponential  =0; //指数
	
	public Node(Integer coefficient,Integer exponential){
		this.coefficient = coefficient;
		this.exponential = exponential;
	}

	public Integer getCoefficient() {
		return coefficient;
	}

	public void setCoefficient(Integer coefficient) {
		this.coefficient = coefficient;
	}

	public Integer getExponential() {
		return exponential;
	}

	public void setExponential(Integer exponential) {
		this.exponential = exponential;
	}


	@Override
	public String toString() {
		return this.coefficient.toString() + "X^" + this.exponential.toString() ;
	}
}