Reference no: EM132493794

The brace checker class should have one public static boolean function: checkBraces, which takes a string parameter. The function should return true if the string parameter contains correctly nested parenthesis (), square-braces [], and curly-braces {}. Any letter other than those six should be ignored. Examples of correctly nested and incorrectly nested strings can be found in the tests for this class.

This is a task that would be quite dicult without a good algorithm (and a good stack) but is quite easy with a stack. Below is pseudocode for this algorithm:

1. begin by creating a stack. This stack will store characters to help us track which open-parenthesis (, left-square-brace [ and left-curly-brace { we've seen, but have not yet matched (an in what order).

2. Loop over each character in the string:

(a) if the character is an open parenthesis (, left-square-brace [ or left-curly-brace {simply push these characters onto the stack. This will remember that we've seen these characters.

(b) if the character is a closing-parenthesis ), right-square-brace ], or right-curly-brace} and the stack is empty, then return false, we've found a right brace/parenthesis which is not matched by a left brace/parenthesis.

(c) if the character is a closing-parenthesis ), right-square-brace ], or right-curly brace } and the top of the stack doesn't match it, then we've found a mismatched brace/parenthesis and can return false.

(d) Otherwise, if the character is a closing-parenthesis ), right-square-brace ], or right-curly-brace } and the top of the stack matches the letter, then we can pop the stack to mark that we've closed that brace/parenthesis, and continue

(e) If the letter is not one of the 6 braces/parenthesis letters, we can ignore it. 

3. Once we've processed every string, if the stack is empty, every left-parenthesis/brace was matched by a right-parenthesis/brace therefore we can return true.

4. If the stack is not empty, then there are some left-parenthesis/braces which were unmatched, and we should return false.