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();

}

}