/* * Polynomial.java * * Created on August 19, 2007, 1:12 PM * * To change this template, choose Tools | Template Manager * and open the template in the editor. */ package project3; import java.lang.*; import java.io.*; import java.util.*; import java.math.*; /** * * @author Tim */ public class Polynomial { private int[] coefficients; public Polynomial(int[] coefficients) { this.coefficients = coefficients; } public static Polynomial input(String text) throws IOException { //PROVIDED BY INSTRUCTOR int coefficient, exponent, maxExponent; int[] coefficients; if (text == null) return null; StringTokenizer tokenizer = new StringTokenizer(text); coefficient = Integer.parseInt(tokenizer.nextToken()); maxExponent = Integer.parseInt(tokenizer.nextToken()); coefficients = new int[maxExponent + 1]; for (exponent = 0; exponent <= maxExponent; exponent++) coefficients[exponent] = 0; coefficients[maxExponent] = coefficient; do{ coefficient = Integer.parseInt(tokenizer.nextToken()); exponent = Integer.parseInt(tokenizer.nextToken()); coefficients[exponent] = coefficient; }while(tokenizer.hasMoreTokens() == true); Polynomial polynomial = new Polynomial(coefficients); return polynomial; } //TO STRING METHOD public String toString(){ String Poly = ""; for(int x=coefficients.length-1; x>=0; x--){ //CONVERTS THE POLYNOMIAL OBJECT INTO A STRING TO BE OUTPUT TO THE SCREEN AND INTO THE NEW TEXT FILE Poly += (String.valueOf(coefficients[x]) + "x^" + String.valueOf(x) ); //ADDS A + SIGN TO THE EQUATION IF IT IS NOT THE LAST NUMBER IN THE POLYNOMIAL if (x!=0){ Poly += ("+"); } } //RETURNS A STRING IN THE FORMAT 8x^3+4x^2+2x+1 return Poly; } //COMPARETO METHOD public boolean compareTo(Polynomial other){ //BOOLEAN FOR USE COMPARE POLYNOMIALS boolean inorder = false; int x=this.coefficients.length-1; int y=other.coefficients.length-1; //THIS CHECKS TO SEE ONE HAS A HIGHER EXPONENT OR NOT if (x>y){ inorder = true; } if(x<y){ inorder = false;} //IF EXPONENTS ARE TO SAME DEGREE, THIS CHECKS OUT THE COEFFICIENTS if (x==y){ boolean looking = true; int i=0; while (looking){ if(this.coefficients[i] > other.coefficients[i]){ looking = false; inorder = true;} if(this.coefficients[i] < other.coefficients[i]){ looking=false; inorder = false;} i++; } } return inorder; } public double evaluate(double exponent){ double result=0, temp=0; double power=0; String Poly = ""; for(int x=coefficients.length-1; x>=0; x--){ power = (double)x; temp = (coefficients[x] * (Math.pow(exponent, power)) ) ; power = 0; result = temp + result; temp=0; } return result; } }

Project3.java Main( ) /* Boyd, Timmothy */ package project3; import java.util.*; import java.io.*; import java.applet.*; import java.awt.*; import java.awt.event.*; public class Project3 { private static BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in)); /*MAIN METHOD*/ public static void main(String[] args) throws IOException{ String token, token2, token3="", prefix="", polynomial=""; StringTokenizer tokenizerPrefix, tokenizerPoly, tokenizerGraph; double exponent = 0; double polyResult = 0; double finalanswer = 0; String evaledPrefix = ""; Stack stack = new Stack(); Stack reverse = new Stack(); //GETS PREFIX EXPRESSION System.out.println("Enter a prefix expression:"); prefix = stdin.readLine(); tokenizerPrefix = new StringTokenizer(prefix, "Pp+-/* ", true); //GETS POLYNOMIAL System.out.println("Enter a Polynomial:"); polynomial = stdin.readLine(); Polynomial polyObject = Polynomial.input(polynomial); /*BUILDS A STACK WITH THE PREFIX EXPRESSION*/ while(tokenizerPrefix.hasMoreTokens() ) { token = tokenizerPrefix.nextToken(); if(token.equals( "+" ) || token.equals( "-" ) || token.equals( "/" ) || token.equals( "*" ) || token.equals( " " ) || Character.isDigit(token.charAt(0)) ){ stack.push(token); } //DETERMINES WHAT THE EXPONENT IS if(token.equals( "P" ) || token.equals( "p" )){ token = tokenizerPrefix.nextToken(); token = tokenizerPrefix.nextToken(); exponent = (Double.parseDouble(token)); /*EVALUATES THE POLYNOMIAL BY PLUGGING IN THE EXPONENT IT THEN PUSHES THE RESULT ONTO THE STACK IN THE PLACE OF P # */ polyResult = polyObject.evaluate(exponent); stack.push(polyResult); }//END IF }//END WHILE LOOP /*NOW THAT THE STACK IS CORRECT, THIS PUTS IT BACK IN THE RIGHT ORDER*/ while(!stack.isEmpty()){ reverse.push( stack.pop() ); } /*THIS EMPTIES THE NEW STACK INTO A STRING WHICH CAN BE USED TO EVALUATE THE PREFIX EXPRESSION*/ while(!reverse.isEmpty()){ evaledPrefix += reverse.pop(); } /*THE DOUBLE FINALANSWER NOW CONTAINS THE COMPLETED PREFIX EXPRESSION*/ finalanswer = prefixEval(evaledPrefix); /*GETS READY TO DRAW THE GRAPH*/ tokenizerGraph = new StringTokenizer(evaledPrefix, "+-/* ", true); String graphString=""; while(tokenizerGraph.hasMoreTokens()){ token3 = tokenizerGraph.nextToken(); if(token3.equals("+") || token3.equals("-") || token3.equals("/") || token3.equals("*")) graphString += "^"; if( Character.isDigit(token3.charAt(0)) ) graphString += "*"; }//END WHILE /*DRAWS THE GRAPH*/ TreeCanvas canvas = new TreeCanvas(); try { Tree tree = new Tree(graphString); canvas.draw(tree); } catch (SyntaxException exception) { } /*THIS IS FOR TESTING PURPOSES TO SHOW HOW THE PROGRAM WORKS, STEP BY STEP*/ System.out.println("You entered: " + prefix); System.out.println("Exponent is: " + exponent); System.out.println("Polynomial is: " + polyObject.toString() ); System.out.println("Polynomial result: " + polyResult ); System.out.println("Evaled Prefix is: " + evaledPrefix ); System.out.println("Final is: " + finalanswer ); System.out.println("Graphing: " + graphString ); }//END MAIN /*THIS RECURSIVE METHOD IS USED TO EVALUATE THE PREFIX EXPRESSION*/ private static double prefixEval (StringTokenizer st) { final String t = st.nextToken(); final char c = t.charAt(0); switch (c) { case '+': return prefixEval(st) + prefixEval(st); case '-': return prefixEval(st) - prefixEval(st); case '*': return prefixEval(st) * prefixEval(st); default: return Double.parseDouble(t);}} public static double prefixEval (String s) { return prefixEval(new StringTokenizer(s)); } }//end class

Node.java package project3; import java.awt.*; abstract public class Node { protected static final int SIZE = 10, SPACING = 25; protected static int x; abstract public Point draw(Graphics graphics, int depth); public static void initDraw() { x = SPACING; } }

Operand.java package project3; import java.awt.*; class Operand extends Node { public Point draw(java.awt.Graphics graphics, int depth) { Point location = new Point(x + SIZE / 2, depth * SPACING + SIZE / 2); graphics.fillRect(x, depth * SPACING, SIZE, SIZE); x += SPACING; return location; } }

Operator.java package project3; import java.awt.*; class Operator extends Node { private Node left, right; public Operator(Node left, Node right) { this.left = left; this.right = right; } public Point draw(java.awt.Graphics graphics, int depth) { Point leftLocation, rightLocation, location; leftLocation = left.draw(graphics, depth + 1); graphics.fillOval(x, depth * SPACING, SIZE, SIZE); location = new Point(x + SIZE / 2, depth * SPACING + SIZE / 2); x += SPACING; rightLocation = right.draw(graphics, depth + 1); graphics.drawLine(leftLocation.x, leftLocation.y, location.x, location.y); graphics.drawLine(rightLocation.x, rightLocation.y, location.x, location.y); return location; } }

SyntaxException.java/*BOYD TIMMOTHY*/ package project3; class SyntaxException extends Exception { public SyntaxException(String message) { super(message); } }

Tree.java package project3; public class Tree { private Node root; private char[] treeString; private int i; public Tree(String tree) throws SyntaxException { treeString = tree.toCharArray(); i = 0; try { root = makeNode(); if (i != tree.length()) throw new SyntaxException("Extra Nodes"); } catch (ArrayIndexOutOfBoundsException exception) { throw new SyntaxException("Missing Nodes"); } } public Node getRoot() {return root;} public Node makeNode() throws SyntaxException { Node node, left ,right; if (treeString[i] == '^') { i++; left = makeNode(); right = makeNode(); node = new Operator(left, right); } else if (treeString[i] == '*') { i++; node = new Operand(); } else throw new SyntaxException("Invalid Symbol"); return node; } }

treeCanvas.javapackage project3; import java.awt.*; class TreeCanvas extends Canvas { private static final int HEIGHT = 200, WIDTH = 400; private Tree tree; public TreeCanvas() { setSize(WIDTH, HEIGHT); setBackground(Color.lightGray); } public void draw(Tree tree) { this.tree = tree; repaint(); } public void paint(Graphics graphics) { Node.initDraw(); if (tree != null) tree.getRoot().draw(graphics, 1); } }