<![CDATA[import java.io.*;
import java.util.*;
class Variable implements Comparable, Cloneable {
char id;
int exp;
Variable() {
}
Variable(char c, int i) {
id = c; exp = i;
}
public int compareTo(Object v) {
return id - ((Variable)v).id;
}
public boolean equals(Object v) {
return id == ((Variable)v).id && exp == ((Variable)v).exp;
}
public Object clone() {
return new Variable(id,exp);
}
}
class Term implements Comparable, Cloneable {
public Term() {
}
int coeff;
Vector vars = new Vector();
public Object clone() {
Term t = new Term();
t.coeff = coeff;
t.vars = (Vector) vars.clone();
for (int i = 0; i < vars.size(); i++)
t.vars.setElementAt(((Variable)vars.elementAt(i)).clone(),i);
return t;
}
/** two terms are equal if all varibles are the same and
* corresponding variables are raised to the same power;
* the first cell of the node containing a term is excluded
* from comparison, since it stores coefficient of the term;
*/
public boolean equals(Object term) {
int i;
for (i = 0; i < Math.min(vars.size(),((Term)term).vars.size()) &&
vars.elementAt(i).equals(((Term)term).vars.elementAt(i)); i++);
return i == vars.size() && vars.size() == ((Term)term).vars.size();
}
public int compareTo(Object term2) {
if (vars.size() == 0)
return 1; // this is just a coefficient;
else if (((Term)term2).vars.size() == 0)
return -1; // term2 is just a coefficient;
Variable var1, var2;
for (int i = 0; i < Math.min(vars.size(),((Term)term2).vars.size()); i++) {
var1 = (Variable)vars.elementAt(i);
var2 = (Variable)((Term)term2).vars.elementAt(i);
if (var1.id < var2.id)
return -1; // this precedes term2;
else if (var2.id < var1.id)
return 1; // term2 precedes this;
else if (var1.exp < var2.exp)
return -1; // this precedes term2;
else if (var2.exp < var1.exp)
return 1; // term2 precedes this;
}
return vars.size() - ((Term)term2).vars.size();
}
}
class Polynomial {
private LinkedList terms = new LinkedList();
Polynomial() {
}
private void error(String s) {
System.out.println(s);
Runtime.getRuntime().exit(-1);
}
Polynomial add(Polynomial polyn2) {
ListIterator p1, p2;
Polynomial result = new Polynomial(), tmp = new Polynomial();
Term term1, term2;
int i;
for (p1 = terms.listIterator(); p1.hasNext(); ) // create new polynomial
result.terms.add(((Term)p1.next()).clone());// out of copies
for (p2 = polyn2.terms.listIterator(); p2.hasNext(); ) // of this
result.terms.add(((Term)p2.next()).clone());// polynomial and polyn2;
for (i = 0, p1 = result.terms.listIterator(); p1.hasNext();
i++, p1 = result.terms.listIterator(i)) {
term1 = (Term) p1.next();
for (p2 = p1; p2.hasNext(); ) {
term2 = (Term) p2.next();
if (term1.equals(term2)) {
term2.coeff += term1.coeff;
result.terms.remove(term1);
if (term2.coeff == 0) // remove terms with zero
result.terms.remove(term2); // coefficients;
i = -1; // to become i = 0 after autoincrement;
break;
}
}
}
java.util.Collections.sort(result.terms);
return result;
}
void get(InputStream fIn) {
int ch = ' ', i, sign, exp;
boolean coeffUsed;
char id;
Term term = new Term();
try {
while (ch > -1) {
coeffUsed = false;
while (true)
if (ch > -1 && Character.isWhitespace((char)ch)) // skip
ch = fIn.read(); // blanks;
else break;
if (!Character.isLetterOrDigit((char)ch) &&
ch != ';' && ch != '-' && ch != '+')
error("Wrong character entered2");
if (ch == -1)
break;
sign = 1;
while (ch == '-' || ch == '+') { // first get sign(s) of Term
if (ch == '-')
sign *= -1;
ch = fIn.read();
while (Character.isWhitespace((char)ch))
ch = fIn.read();
}
if (Character.isDigit((char)ch)) { // and then its coefficient;
String number = "";
while (Character.isDigit((char)ch)) {
number += (char) ch;
ch = fIn.read();
}
while (Character.isWhitespace((char)ch))
ch = fIn.read();
term.coeff = sign * Integer.valueOf(number).intValue();
coeffUsed = true;
}
else term.coeff = sign;
for (i = 0; Character.isLetterOrDigit((char)ch); i++) {
id = (char) ch; // process this term:
ch = fIn.read(); // get a variable name
if (Character.isDigit((char)ch)) { // and an exponent
String number = ""; // (if any);
while (Character.isDigit((char)ch)) {
number += (char) ch;
ch = fIn.read();
}
exp = Integer.valueOf(number).intValue();
while (Character.isWhitespace((char)ch))
ch = fIn.read();
}
else exp = 1;
term.vars.addElement(new Variable(id,exp));
}
terms.add(term.clone());
term.vars = new Vector();
while (Character.isWhitespace((char)ch))
ch = fIn.read();
if (ch == ';') // finish if a semicolon is entered;
if (coeffUsed || i > 0)
break;
else error("Term is missing"); // e.g., 2x - ; or just ';'
else if (ch != '-' && ch != '+') // e.g., 2x 4y;
error("wrong character entered");
}
} catch (IOException io) {
}
for (Iterator p = terms.iterator(); p.hasNext(); ) {
term = (Term) p.next(); // order alphabetically variables
if (term.vars.size() > 1) // in each term separately;
Collections.sort(term.vars);
}
}
void display() {
boolean afterFirstTerm = false;
Term term;
for (Iterator it = terms.iterator(); it.hasNext(); ) {
term = (Term) it.next();
System.out.print(" ");
if (term.coeff < 0) // put '-' before polynomial
System.out.print("-"); // and between terms (if needed);
else if (afterFirstTerm) // don't put '+' in front of
System.out.print("+"); // polynomial;
afterFirstTerm = true;
System.out.print(" "); // print a coefficient if
if (term.vars.size() == 0 || // the term has only
Math.abs(term.coeff) != 1) // a coefficient or coefficient
System.out.print(Math.abs(term.coeff)); // is not 1 or -1;
for (int i = 1; i <= term.vars.size(); i++) {
Variable var = (Variable) term.vars.elementAt(i-1);
System.out.print(var.id); // print a variable name
if (var.exp != 1) // and an exponent, only
System.out.print(var.exp); // if it is not 1.
}
}
System.out.println();
}
}
class AddPolyn {
static public void main(String[] a) {
Polynomial polyn1 = new Polynomial(), polyn2 = new Polynomial();
System.out.println("Enter two polynomials, each ended with a semicolon:");
polyn1.get(System.in);
polyn2.get(System.in);
System.out.println("The result is:");
polyn1.add(polyn2).display();
}
}
]]>