1. Overview

Determining if a string containing some number of brackets is balanced is an important problem within computer science. It has many applications in designing compilers for programming languages as most programming languages include syntax for building expressions with brackets and other types of parenthesis.

For example, mathematical expressions must be parenthesized in order to enforce correct execution of operations, e.g. (a + b+c)/3 correctly computes the average of the three numbers a, b, c, but a+b+c/3 does not. In this assignment, you will implement a simple balanced brackets checker using a stack.

You are required to write a Java program that reads a string from stdin and determines if the string entered contains a set of balanced brackets or not.

For example, the string ((())[]) consists of balanced brackets while the string ()) does not. Additionally,

your program must be able to handle any type of string entered by the user, in particular, it may contain other characters besides brackets.

For example, the string ((a + b) c)/d is balanced, while the string (a + b)) is not. Your program must be able to determine if a given string is balanced or not. You may assume that the types of brackets that the user may enter will be from: (), [], {}, <>. No other types of brackets need be maintained by your program.

Additionally, a string containing no brackets at all is vacuously balanced.

2. Data Structures

The following is a description of the data structures that your program is required to use. 2.1 Parallel Arrays A parallel array data structure is a collection of arrays, A1, A2, . . . , An, each of the same length, that implicitly stores a collection of records.

Each field of the record is contained in a separate array and the indices of the arrays correspond to a particular record. Thus, A1[0], A2[0], . . . , An[0] is a complete record. In this project your program must maintain two parallel arrays each of length 4: 1. openBrackets[0, . . . , 3] = (, {, [, < 2. closeBrackets[0, . . . , 3] = ), }, ], > Thus, openBrackets[0] = ( and closeBrackets[0] = ). These arrays will be necessary to implement the bracket matching algorithm described below.

The type of the arrays in your program should be char[]. 2.2 Stack Your program is required to use a stack. The way the stack is to be used is described by the bracket matching algorithm itself. You may use either an array based stack implementation or a linked list based stack implementation.

However, do not re-implement a stack data structure! Use the existing implementations we have completed in class.

Page 1 of 3 3 Bracket Matching Algorithm The following is the pseudo-code for an algorithm that checks if a given string is properly balanced.

Assume that the algorithm has access to a stack object (called stack in the pseudo-code below). Algorithm 1 Input: A string s = s1s2 sn. Output: True if the string s is balanced; false otherwise.

1: function MATCH(s)

2: for i = 1, 2, . . . , n do 3: 4: if s[i] is an opening bracket then 5: stack.push(s[i]) 6: 7: else if s[i] is a closing bracket then 8: c stack.pop() .

Assume that pop() on an empty stack returns null 9: 10: if c is not the corresponding opening bracket to s[i] then 11: return false 12: 13: if stack.isEmpty() then 14: return true 15: else 16: return false Remark:

You must write the correct Boolean expressions to implement the conditionals in lines 4, 7, and 10.

This are where the parallel arrays will be useful.

4 Structural Requirements All of your code for implementing the bracket matching algorithm must be contained in a class called BracketMatcher.

Your BracketMatcher class must contain implementations of the following methods.

You may use additional supporting methods, but, a call to the match method described below should produce the correct result.

1. private int isOpenBracket(char b); If the parameter b is an opening bracket symbol, then this method should return the index of the openBrackets array that contains the symbol b. If b is not an opening bracket, then the method should return 1.

2. private int isCloseBracket(char b); If the parameter b is a closing bracket symbol, then this method should return the index of the closeBrackets array that contains the symbol b. If b is not a closing bracket, then the method should return 1.

3. public boolean match(String s); If the parameter s is properly balanced, then this method should return true; otherwise it should return false. Thus, this method contains the implementation of the MATCH(s) algorithm described in pseudo-code above.

Additionally, your BracketMatcher class must have the following instance variables:

1. private final char[] openBrackets

2. private final char[] closeBrackets

3. private Stack ms Page 2 of 3 5 Sample Class //Any import statements necessary will go here.

public class BracketMatcher { //These fields MUST be initialized to the correct values.

private final char[] openBrackets;

private final char[] closeBrackets;

private Stack ms;

/** The following methods will all need to be implemented. That is, you must fill in the bodies of these methods. Make sure to include comments (as well as Javadoc comments) for each of your methods. */ //------BEGIN METHODS-------// /*** @param s The string to be checked for balance property. @return True if the string s is balanced; false otherwise. */ public boolean match(String s) { } /*** @param b @return */

private int isOpenBracket(char b) { } /*** @param b @return */

private int isCloseBracket(char b) { } } Page 3 of 3