Homework Soursehome study engineering computer science questions and an
home / study / engineering / computer science / questions and answers / the third programming project involves writing ...
Question: The third programming project involves writing a p...
Bookmark
The third programming project involves writing a program that performs a sort by using a binary search tree. The program should be able to sort lists of integers or lists of fractions in either ascending or descending order. One set of radio buttons should be used to determine whether the lists contain integers or fractions and a second set should be used to specify the sort order. The main class should create the GUI shown below:
The GUI must be generated by code that you write. You may not use a drag-and-drop GUI generator. Pressing the Perform Sort button should cause all the numbers in the original list to be added to a binary search tree. Then an inorder traversal of the tree should be performed to generate the list in sorted order and that list should then be displayed in the sorted list text field. In addition to the main class that defines the GUI, you should have a generic class for the binary search tree. That class needs a method to initialize the tree, one that allows a new value to be inserted in the tree and one that performs an inorder tree traversal that generates and returns a string that contains the tree elements in sorted order. The insert method does not need to rebalance the tree if it becomes unbalanced. It should allow duplicate entries and it must be written using recursion. It is not necessary to have a method to delete a node from the tree nor one to check whether a particular value is in the tree. The third class required for this project is one that defines fractions. It should have a constructor that accepts a string representation of a fraction and a toString method. It must implement the Comparable interface, which means a compareTo method is also required. A second example of a run of this program is shown below that sorts fractions in descending order:
Note that fractions are to be written with a slash separating the numerator and denominator with no spaces on either side of the slash. The only error checking required of this program is to check for nonnumeric input which includes improperly formatted fractions such as 3/4/8. Such malformed fractions should cause a NumberFormatExpression to be thrown. The main class must catch these exceptions and display an appropriate error message as shown below:
d Binary Search Tree Sort Original List 4 8 2 123 16 8 16 3 14 2 10 24 Sorted List 1223 488 10 14 16 16 23 24 Perform Sort Sort Order Numeric Type Integer Ascending Descending FractionSolution
package test;
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import javax.swing.JOptionPane;
public class TextFields implements ActionListener {
JTextField originalList;
JTextField sortedList;
JButton sortButton = new JButton(\"Perform Sort\");
public static boolean isInteger(String s) {
try {
Integer.parseInt(s);
} catch (NumberFormatException e) {
return false;
} catch (NullPointerException e) {
return false;
}
return true;
}
JRadioButton ascendingButton;
JRadioButton descendingButton;
JRadioButton integerButton;
JRadioButton fractionButton;
public TextFields() {
JFrame frame = new JFrame(\"BST Sort\");
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.setSize(new Dimension(800, 800));
// Create fields for I/O
originalList = new JTextField(16);
sortedList = new JTextField(16);
sortedList.setEnabled(false);
JPanel inFieldPane = new JPanel();
inFieldPane.setLayout(new GridLayout(2, 2));
inFieldPane.add(new JLabel(\"Original List\"));
inFieldPane.add(originalList);
originalList.addActionListener(this);
inFieldPane.add(new JLabel(\"Sorted List\"));
inFieldPane.add(sortedList);
sortedList.addActionListener(this);
frame.add(inFieldPane, BorderLayout.NORTH);
// Add submission button
JPanel submitPane = new JPanel();
submitPane.setLayout(new FlowLayout());
sortButton.addActionListener(this);
submitPane.add(sortButton);
frame.add(submitPane, BorderLayout.CENTER);
// Add Output fields
// JPanel outFieldPane = new JPanel();
// outFieldPane.setLayout(new GridLayout(1, 2));
// outFieldPane.add(new JLabel(\"Full Name\"));
// outFieldPane.add(fullName);
// frame.add(outFieldPane, BorderLayout.SOUTH);
//
ascendingButton = new JRadioButton(\"Ascending\", true);
descendingButton = new JRadioButton(\"Descending\");
ButtonGroup group = new ButtonGroup();
group.add(ascendingButton);
group.add(descendingButton);
integerButton = new JRadioButton(\"Integer\", true);
fractionButton = new JRadioButton(\"Fraction\");
ButtonGroup group1 = new ButtonGroup();
group1.add(integerButton);
group1.add(fractionButton);
// Add labelled input fields to display
JPanel inFieldPane1 = new JPanel();
inFieldPane1.setLayout(new GridLayout(2, 2));
inFieldPane1.add(ascendingButton);
inFieldPane1.add(integerButton);
integerButton.addActionListener(this);
inFieldPane1.add(descendingButton);
inFieldPane1.add(fractionButton);
fractionButton.addActionListener(this);
frame.add(inFieldPane1, BorderLayout.SOUTH);
frame.setVisible(true);
}
public void actionPerformed(ActionEvent e) {
if (e.getSource() == sortButton) {
ascendingButton.isSelected();
String fullString = originalList.getText().trim();
System.out.println(fullString);
String[] values = fullString.split(\" \");
boolean error = false;
if (integerButton.isSelected()) {
for (int i = 0; i < values.length; i++) {
if (!isInteger(values[i])) {
error = true;
break;
}
}
} else {
// Fraction Button Selected
for (int i = 0; i < values.length; i++) {
String[] s = values[i].split(\"/\");
if (s.length != 2) {
error = true;
break;
}
if (!isInteger(s[0]) || !isInteger(s[1])) {
error = true;
}
}
}
if (error) {
MessageBox.infoBox(\"Non Numeric Input\", \"MESSAGE\");
System.exit(-1);
}
boolean reversed = false;
if (descendingButton.isSelected()) {
reversed = true;
}
if (integerButton.isSelected()) {
BST<Integer> tree = new BST<Integer>();
for (int i = 0; i < values.length; i++) {
tree.insert(Integer.parseInt(values[0]));
}
fullString = tree.getSorted(reversed);
System.out.println(\"fullString is\" + fullString + \" \" + tree.root.element);
} else {
BST<Fraction> tree = new BST<Fraction>();
for (int i = 0; i < values.length; i++) {
tree.insert(new Fraction(values[0]));
}
fullString = tree.getSorted(reversed);
}
// print output
sortedList.setText(fullString);
}
}
public static void main(String[] args) {
new TextFields();
}
}
class MessageBox {
public static void infoBox(String infoMessage, String titleBar) {
JOptionPane.showMessageDialog(null, infoMessage, \"Message: \" + titleBar, JOptionPane.INFORMATION_MESSAGE);
}
}
package test;
public class BST<T extends Comparable<? super T>> {
/**
* This class represents a single node in our Binary Tree.
*
* @author yourname
* @date todays date
*/
String result;
public class BinaryNode {
// Local variables
public T element; // The data in the node
BinaryNode left; // Pointer to the left child
BinaryNode right; // Pointer to the right child
/**
* This constructor initializes a childless binary node.
*
* @param elem
* Any generic object that implements Comparable
* @post A childless binary node is initialized
*/
public BinaryNode(T elem) {
element = elem;
left = null;
right = null;
}
public String toString() {
return element.toString();
}
/**
* This constructor initializes a binary node with children.
*
* @param elem
* Any generic object that implements Comparable
* @param lt
* The left node to which this node points
* @param rt
* The right node to which this node points
* @post A binary node with two children is initialized
*/
public BinaryNode(T elem, BinaryNode lt, BinaryNode rt) {
element = elem;
left = lt;
right = rt;
}
}
// Local variables
public BinaryNode root; // Pointer to root node, if present
/**
* This constructor initializes an empty BST. An empty BST contains no
* nodes.
*
* @post An empty tree is initialized
*/
public BST() {
root = null;
result = \"\";
}
/**
* This method determines if the BST is empty.
*
* @return Returns true if the BST contains no nodes
*/
public boolean isEmpty() {
return (root == null);
}
/**
* This method attempts to find an element in the BST.
*
* @param elem
* The element to find
* @return Returns a pointer to the matching data element or null if no
* matching element exists in the BST
*/
public T find(T elem) {
BinaryNode found = find(root, elem);
return (found == null) ? null : found.element;
}
/**
* This method attempts to find an element in the BST.
*
* @param start
* The node from which to start the search
* @param elem
* The element to find
* @return Returns a pointer to the matching data element or null if no
* matching element exists in the BST
*/
public BinaryNode find(BinaryNode start, T elem) {
// If the element isn\'t found, return null
if (start == null) {
return null;
}
// Compare the current node\'s element to the element we\'re looking for
int comparison = start.element.compareTo(elem);
// If we should look down the left tree
if (comparison > 0) {
return find(start.left, elem);
}
// If we should look down the right tree
else if (comparison < 0) {
return find(start.right, elem);
}
// If we\'ve found it
else {
return start;
}
}
/**
* This method inserts an element into the BST, unless it is already stored.
*
* @param elem
* The element to insert into the BST
* @return Returns true if the insertion is performed and false otherwise
* @post The element will be inserted into the BST
*/
public boolean insert(T elem) {
return insert(root, elem);
}
/**
* This method inserts an element into the BST, unless it is already stored.
*
* @param start
* The node from which to start the insertion
* @param elem
* The element to insert into the BST
* @return Returns true if the insertion is performed and false otherwise
*/
public boolean insert(BinaryNode start, T elem) {
// We\'ve reached the point of insertion
if (start == null) {
// Insert our element into a new node
root = new BinaryNode(elem, null, null);
return true;
}
// Compare the current node\'s element to the element we\'re looking to
// delete
int comparison = start.element.compareTo(elem);
// If are insertion will happen somewhere down the left tree
if (comparison >= 0) {
// If we\'ve reached the point of insertion
if (start.left == null) {
// Insert our element into a new node
start.left = new BinaryNode(elem, null, null);
return true;
}
// Otherwise, keep traversing until we reach the point of insertion
return insert(start.left, elem);
}
// If are insertion will happen somewhere down the right tree
else if (comparison < 0) {
// If we\'ve reached the point of insertion
if (start.right == null) {
// Insert our element into a new node
start.right = new BinaryNode(elem, null, null);
return true;
}
// Otherwise, keep traversing until we reach the point of insertion
return insert(start.right, elem);
}
// If the element is already in the tree
else {
// Don\'t insert the element
return false;
}
}
/**
* This method returns the tree to an empty state.
*
* @post The tree will be empty
*/
public void clear() {
root = null;
}
/**
* This heper method prints the BST rooted at the given start node.
*
* @param start
* The node from which to root the printing proceedure.
*/
void print() {
print(root);
}
public void print(BinaryNode start) {
if (start != null) {
print(start.left);
System.out.println(start.element);
print(start.right);
}
}
void inOrder(BinaryNode node) {
if (node == null)
return;
inOrder(node.left);
result = result + node.element + \" \";
inOrder(node.right);
}
void revInOrder(BinaryNode node) {
if (node == null)
return;
inOrder(node.right);
result = result + node.element + \" \";
inOrder(node.left);
}
public String getSorted(boolean reversed) {
if (reversed) {
revInOrder(root);
} else {
inOrder(root);
}
System.out.println(result);
return result;
}
}
package test;
/* Fraction.java */
import java.io.*;
/**
* The Fraction class implements non-negative fractions, i.e., rational numbers.
*/
class Fraction implements Comparable<Fraction> {
/**
* Constructs a Fraction n/d.
*
* @param n
* is the numerator, assumed non-negative.
* @param d
* is the denominator, assumed positive.
*/
Fraction(int n, int d) {
numerator = n;
denominator = d;
}
/**
* Constructs a Fraction n/1.
*
* @param n
* is the numerator, assumed non-negative.
*/
public Fraction(int n) {
this(n, 1);
}
/**
* Constructs a Fraction 0/1.
*/
public Fraction() {
numerator = 0;
denominator = 1;
}
public Fraction(String s) {
String[] nums = s.split(\"/\");
numerator = Integer.parseInt(nums[0]);
denominator = Integer.parseInt(nums[1]);
}
/**
* Converts this fraction to a string format: \"numerator/denominator.\"
* Fractions are printed in reduced form (part of your assignment is to make
* this statement true).
*
* @return a String representation of this Fraction.
*/
public String toString() {
int thisGcd = gcd(numerator, denominator);
return (numerator / thisGcd + \"/\" + denominator / thisGcd);
}
/**
* Calculates and returns the double floating point value of a fraction.
*
* @return a double floating point value for this Fraction.
*/
public double evaluate() {
double n = numerator; // convert to double
double d = denominator;
return (n / d);
}
/**
* Add f2 to this fraction and return the result.
*
* @param f2
* is the fraction to be added.
* @return the result of adding f2 to this Fraction.
*/
public Fraction add(Fraction f2) {
Fraction r = new Fraction((numerator * f2.denominator) + (f2.numerator * denominator),
(denominator * f2.denominator));
return r;
}
/**
* Computes the greatest common divisor (gcd) of the two inputs.
*
* @param x
* is assumed positive
* @param y
* is assumed non-negative
* @return the gcd of x and y
*/
static private int gcd(int x, int y) {
/* Remove the following line. */
return 1;
}
/* private fields within a Fraction. */
private int numerator;
private int denominator;
/**
* Put the Fraction class through some test sequences.
*
* @param argv
* is not used.
*/
public static void main(String[] argv) {
/* Test all three contructors and toString. */
Fraction f0 = new Fraction();
Fraction f1 = new Fraction(3);
Fraction f2 = new Fraction(12, 20);
System.out.println(\"\ Testing constructors (and toString):\");
System.out.println(\"The fraction f0 is \" + f0.toString());
System.out.println(\"The fraction f1 is \" + f1); // toString is implicit
System.out.println(\"The fraction f2 is \" + f2);
/* Test methods on Fraction: add and evaluate. */
System.out.println(\"\ Testing add and evaluate:\");
System.out.println(\"The floating point value of \" + f1 + \" is \" + f1.evaluate());
System.out.println(\"The floating point value of \" + f2 + \" is \" + f2.evaluate());
/*
* Fraction sumOfTwo = _______________; Fraction sumOfThree =
* ______________;
*
* System.out.println(\"The sum of \" + f1 + \" and \" + f2 + \" is \" +
* sumOfTwo); System.out.println(\"The sum of \" + f0 + \", \" + f1 +
* \" and \" + f2 + \" is \" + sumOfThree);
*/
/* Test gcd function (static method). */
System.out.println(\"\ Testing gcd:\");
System.out.println(\"The gcd of 2 and 10 is: \" + gcd(2, 10));
System.out.println(\"The gcd of 15 and 5 is: \" + gcd(15, 5));
System.out.println(\"The gcd of 24 and 18 is: \" + gcd(24, 18));
System.out.println(\"The gcd of 10 and 10 is: \" + gcd(10, 10));
System.out.println(\"The gcd of 21 and 400 is: \" + gcd(21, 400));
System.out.println();
}
@Override
public int compareTo(Fraction fraction2) {
int numerator1 = numerator * fraction2.denominator;
int numerator2 = fraction2.numerator * denominator;
// subtract to get the result
// if numerator1 > numerator2, then will have positive integer
// if numerator1 == numerator2, then will have zero (0)
// if numerator1 < numerator2, then will have negative integer
int result = numerator1 - numerator2;
return result;
}
}
