Problem description Main objective: Determine whether any expression with multiple kinds of brackets, braces and parentheses is balanced using a reference-based stack. You must implement the stack directly yourselves. Using a stack library, or JCF stacks, or a list ADT will earn no credit.

Types of brackets:

There are four parenthesis/bracket pairs:

( and )

[ and ]

{ and }

< and >

A line may contain other characters (including spaces) besides these 8 characters, but those characters are ignored. An expression is balanced if all the open parentheses are closed by a matching close parentheses, and nested parenthesis match, so that (for example) you can have ] closing {, or a stray extra ) when there isnt an open (.

2 For example, the following lines are all not valid (N):

ab(x]w

alpha{ beta

(([[Turing]])

The ( quick [ brown ( fox ( jumped ) over ) the ] lazy ) dog )

< { }

> html <

And the following lines are all valid (Y):

ab[x]w

alpha{ betadelta}

([[Turing]]) The ( quick [ brown ( fox ( jumped ) over ) the ] lazy ) dog

metamorphosis

< html >

( [ < { } > ] ) < < ( ) > >

You will not get any credit if you do not implement your solution to HW3 using a reference-based stack. Furthermore, you have to write your own stack from scratch. You cannot use any built-in libraries for stacks or linked lists, nor can you use an ADT for lists or an array-based stack.

Format: You should provide a Makefile. Running make should create Balanced.jar. Your program should take two command line arguments, an input file and an output file.

Input: The input file consists of a series of lines as described above, each (including the last line) ending with an end-of-line.

Output: On running (say) :

java -jar Balanced.jar my-input.txt my-output.txt

the file my-input.txt is read in and the file my-output.txt should be output. The ith line of the output file my-output.txt corresponds to the ith line in the input file my-input.txt. The ith line of the output file should contain just :a single character, as follows:

If the ith line is not valid, then the ith line should just be N (without the quotes).

If the ith line is valid, then the he ith line should just be Y (without the quotes).

Examples: Piazza has a zip file for HW3 called HW3files.zip. The files test-input.txt and test-output.txt (which should help you see if your program is correct) are for the checker. Two additional files, more-input.txt and more-output.txt that are in the zip file will also help you test your program.

test-input.txt:

b(x]w alpha{ beta (([[Turing]]) The ( quick [ brown ( fox ( jumped ) over ) the ] lazy ) dog ) < { } > html < ab[x]w alpha{ betadelta} ([[Turing]]) The ( quick [ brown ( fox ( jumped ) over ) the ] lazy ) dog metamorphosis < html > ( [ < { } > ] ) < < ( ) > >

test-output.txt:

N N N N N N Y Y Y Y Y Y Y