COSC5315 Group
Project
due: 11/28/2012
Exploration
of Grammar/Acceptor/Language Applications
Task:
This is a group project for
which up to two people can work together.
Your task is to write a
report of no more than seven pages on application of Grammars or Acceptors or
Languages of any type or types, 0, 1, 2, or 3.
One such application is a
design of a CFG for an abbreviated version of java illustrated by the following
java program.
Your report must be well
organized with some suitable headings such as introduction that includes (a)
your own preference/reason for choosing a particular application when others are
also available, (b) anticipated results or findings and (c) how work/labor is
divided among group members in case of a group work, (d) the main body that
clearly shows a detailed process of realizing a particular practical
application, and (e) conclusion that includes what you
think you really have learned, if any, and what you think is the
contributions/benefits of the application you explored.
//**
import java.util.*;
public class BinarySearchTree
//visibility modifier can be also
private
{
public class TreeNode
// an inner class of class
BinarySearchTree, for binary
trees
{ // 3 private instance
variables
////////////////////////////////////////////////////////
private int data;
// visibility modifier can be also public or
protected and
// type can be also float, double, char, short, long or boolean
private TreeNode leftLink;
private TreeNode rightLink;
// One constructor for TreeNode
///////////////////////////////////////////////////////
public TreeNode(int newData, TreeNode newLeftLink,
TreeNode newRightLink)
{
data = newData;
leftLink = newLeftLink;
rightLink = newRightLink;
}
} //End of TreeNode inner class
// Declaration of class
BinarySearchTree begins here.
///////////////////////////////////////////
// Just two instance variables.
///////////////////////////////////////////
private TreeNode root;
private TreeNode parent;
//////////////////////////////////////////////////////////
// One no-argument
constructor for creating an empty binary tree.
//////////////////////////////////////////////////////////
public BinarySearchTree( )
{
root = null;
private = null;
}
/////////////////////////////////////////////////
public boolean remove (int oldItem)
{
boolean success =
true;
TreeNode target, replaceNode, rightChild;
int[] parentLinks=
{0,0};
int parentLink;
target = isInSubtree
(oldItem, parentLinks);
parentLink = parentLinks[0];
if (target == null) return
!success;
if (parentLink!=0) //
target node has a parent
{
if (target.leftLink==null && target.rightLink==null)
{ if (parentLink==1) parent.leftLink=null;
else if (parentLink==2) parent.rightLink=null;
return success;
}
if (target.leftLink!=null && target.rightLink==null)
{ if (parentLink==1)
parent.leftLink =target.leftLink;
else if (parentLink==2)
parent.rightLink=target.leftLink;
return success;
} } }
private static void showInOrder(TreeNode treeRoot)
{
//Uses inorder traversal.
if (treeRoot != null)
{
showInOrder(treeRoot.leftLink);
System.out.print(treeRoot.data + "
");
showInOrder(treeRoot.rightLink);
}//else do nothing. Empty tree has nothing to
display.
}
public static void main(String[]
args)
{
Scanner keyboard = new Scanner(System.in);
BinarySearchTree tree = new BinarySearchTree( );
// above creates an empty
binary tree where root=null.
System.out.println ("Enter a list of some
nonnegative integers.");
System.out.println ("Make sure to Include 1000.");
System.out.println ("Place a negative integer
at the end.");
int x, y, result; // Any number of
variables is OK.
result=0; x=0;
y=10;
int next = keyboard.nextInt( );
while (next >= 0)
// Comparison operators can also be >, <,
<=, == or !=
{ result += x+result*y;
tree.add(result, tree.root);
next = keyboard.nextInt( );
}
System.out.println("In sorted
order:");
tree.showElements();
boolean success = tree.remove (1000);
if
(success)
System.out.println ("\nRESULTING TREE AFTER REMOVING” +
“ NODE WITH 1000:::\n");
else
System.out.println ("\nWANTED NODE NOT FOUND, SORRY!!!");
tree.showElements();
}
}