Programming Assignment 6

Due April 12, before midnight.

Program Description
In this assignment, you will use a recursive algorithm to determine if nested bracketing operators are balanced.  In Java, these bracketing operators are

   (  and  )
   [  and  ]
   {  and  }

In a properly formed program, these characters will be properly nested and matched.  In a legal configuration, all the operators match up correctly, as shown in the following example:

   { ( [ ] ) ( [ ( ) ] ) }

The following configurations, however, are illegal for the reasons stated:

   ( ( [ ] )    The line is missing a close parenthesis
   ) (          The close parenthesis comes before the open parenthesis
   { ( } )      The parentheses and braces are improperly nested.

The assignment was developed by Paritosh Shroff, at Johns Hopkins University.

What You Do
It is assumed that you are using NetBeans to develop your code for this assignment.  Create a new NetBeans project that is a "General" "Java Application". Name your NetBeans project program6.

Download the source for the Main.java, Nested.java classes, and store these in the program6/src/program6 directory.

Using NetBeans, you are to implement a recursive static method for the class Nested:
  1. public static boolean isBalanced(String s)
This method returns true if the bracketing operators in the string s are balanced, which means they are correctly nested and matched. If the string is not balanced, then the method returns false.

You can assume that the input String s contains only bracket operator characters.

Recursive Algorithm

There are many ways to implement the recursive algorithm; however, you should code your solution so that it embodies the recursive insight that a string consisting of bracketing characters is balanced if and only if one of the following conditions holds:
  • The string is empty.
  • The string contains "()", "[]", "{}" as a substring and is balanced if you remove that substring.
For example, the string "[(){}]" is shown to be balanced by the following chain of recursive calls:
isBalanced("[(){}]")   -->
isBalanced("[{}]")   -->
isBalanced("[]")   -->
isBalanced("")   --> true

Hint

You will probably want to use the String class methods indexOf(...) and substring(...).

Programming Style

You are expected to follow the CS111 / CS112 Java Coding Standard.  You will be graded on programming style. Each student must schedule two meetings with course staff to review a submitted program's style.   Two lab times will be set aside for this (refer to course schedule).  You can also arrange to have tutors review your program style during scheduled tutoring hours.   This is meant to allow students to get guidance and feedback on style, and the grading of style is separate from the grading of Program Assignment 5.

Testing

You are responsible for testing your method.  To help you in testing, a few example tests are provided in the file Main.java.  Other tests will be conducted in grading -- so test your methods carefully before submitting your code. 
     

What You Submit
Submit your  file called Nested.java in a directory named 06 via gsubmit .

Under no circumstances will late assignments be accepted.

Grading Criteria

20% Submitted code compiles without errors
40% isBalanced returns the correct value for the cases given in Main.java
40% isBalanced returns the correct value for other cases given at testing time.