Well Balanced Project

Overview

For this project you will write a program which determines if the parentheses, curly brackets, and square brackets in a text file are properly paired within a text file. The parentheses characters are ( and ). The curly bracket characters are { and }. The square bracket characters are [ and ]. Properly paired means for each left parenthesis there is a corresponding right parenthesis, for each left curly bracket there is a corresponding right curly bracket, and for each left square bracket there is a corresponding right square bracket. In addition to this, the left and right parentheses, curly brackets, and square brackets have to occur in the correct order.

The algorithm to perform the check of well­balanced parentheses, curly brackets, and square brackets uses a stack and is straight forward:

One at a time, the algorithm reads in a character from the input file, prints the character, and processes the character as follows:

A. If the character is anything other than a parenthesis, curly bracket, or square bracket then ignore that character and read in the next character from the input file.

B. If the character is a left parenthesis, left curly bracket, or left square bracket then push that character onto the stack and read in the next character from the input file.

C. If the character is a right parenthesis, right curly bracket, or right square bracket then:

1. Pop just one character off the top of the stack.

2. Compare the character just read in with the character just popped off the top of the stack:

a. If both characters are parentheses, or both characters are curly brackets, or both characters are square brackets (Hence, both characters are the same type) then balance is maintained and read in the next character from the input file.

b. If both characters are not the same type then print an error message telling the user the input does not have well­balanced parentheses, curly brackets, or square brackets and terminate the program.

There are two other situations where the text within a text file are not properly paired. One situation is when the number of left parentheses, curly brackets, and/or square brackets is more than the number of right parentheses, curly brackets, and/or square brackets. The other situation is when the number of right parentheses, curly brackets, and/or square brackets is more than the number of left parentheses, curly brackets, and/or square brackets. You'll have to figure out how to detect and when each situation might occur within the algorithm given in the previous paragraph.

Design

1. The input to your program will be read from a plain text file called project2.txt. This is the statement you'll use to open the file:

FileInputStream fstream = new FileInputStream("project2.txt");

Assuming you are using Eclipse to create your project, you'll store the input file project2.txt in the parent directory of your source code (.java files) which happens to be the main directory of your project in Eclipse. If you're using some other development environment, you'll have to figure out where to store the input file.

Any text file containing computer code can be used to test your program. You should use a number of test text files to test your program. Some of your test text files have well­balanced parentheses, curly brackets, and square brackets and other test text files do not have well­balanced parentheses, curly brackets, and square brackets.

2. Make the name of the driver class Project2 and it should only contain only one method:

public static void main(String args[]).

The main method will open the file project2.txt and hand off the input to another class or classes to perform the well­balanced parentheses, curly brackets, and square brackets algorithm. Therefore, the main method itself should be fairly short.

3. Download the files Stack.java and DynamicArrayStack.java containing the some of the array implementation of the stack class. You cannot add data members to or modify the data members of the dynamic array stack class. You cannot modify the dynamic array stack class constructor. You will write the code for the size, isEmpty, push(AnyType newValue), top(), and pop() methods.

You will add the appropriate code to the dynamic array stack class to resize the array data (the stack's storage) when the array data is completely full or when the number of values in the stack is ¼ the size of the array data. You do not need to write this code yourself, it is code discussed in class.

You do not need to write any additional methods to help in your implementation of the dynamic array stack class.

4. Your program will, one at a time, read in a character from the input file, print the character, and process the character according to the algorithm described in the overview section. If the text in the input file does not contain well­balanced parentheses, curly brackets, or square brackets then your program will print an error message and terminate properly. If the text in the input file does contain well­balanced parentheses, curly brackets, and square brackets then your program will print a message stating this and complete its execution normally.

5. Do NOT use your own packages in your program. Do NOT use any graphical user interface code in your program.

6. Make your program as modular as possible, not placing all your code in one .java file. You can create as many classes as you need in addition to the classes described above. Methods should be reasonably small following the guidance that "A function should do one thing, and do it well."

7. Document and comment your code thoroughly.