# Checking brackets nesting in a string

I took a training challenge on Codility that checks for the proper nesting of brackets in a string. The brackets to be checked are {,},(,),[,]. I have written the following Java program which passes in O(n) time and space, but I have a feeling that the extra space I use can be reduced. Also I think that there must be a data structure that can handle this scenario more efficiently. Using an ArrayList instead of an array might help. What I need here is a critique of my code.

import java.util.HashMap;
class Solution {
public int solution(String S) {
char[] stack = new char[S.length()];
int last = -1;
HashMap hm = new HashMap();
hm.put('}', '{');
hm.put(')', '(');
hm.put(']', '[');
for(int i=0; i<S.length(); i++){
char next = S.charAt(i);
if(next == '}' || next == '{' || next == ')' || next == '(' ||
next == ']' || next == '[')
{
if(last!=-1 && hm.containsKey(next) && stack[last] == hm.get(next)){
last--;
}
else{
last++;
stack[last] = S.charAt(i);
}
}
}
if(last == -1){
return 1;
}
return 0;
}
}

-

### Naming

• Class name: Solution A solution for what?
• Method name: solution - again I ask: Solution for what?
• Parameter name: S - And what on earth is S? Parameter names are by convention named beginning with a lowercase letter.

None of these three names are descriptive names. It is easier to read and understand code when the names tell a bit about what it is that the code does. Now, naming things are hard, and something that programmers do a lot. For this case, consider names such as BracketNestingVerifier, verify and input. You might even be able to come up with better names.

### General things

• Use Generics for your HashMap. Since Java 1.5, it's been possible to define which kind of HashMap it is. Is it a HashMap of <Integer, String>? <String, Byte>? No, in your case; it's HashMap<Character, Character>

• Why do the method return an int when it would make much more sense to return a true/false boolean? Returning a boolean allows you to simplify the end of your method

if (last == -1) { // note the fixed spacing ;)
return 1;
}
return 0;


To simply return (last == -1);

### Spacing

I find that code like this:

for(int i=0; i<S.length(); i++){


Is much more readable if you use spacing (and a better variable name for S of course)

for (int i = 0; i < input.length(); i++) {


### Algorithm

Now, about that algorithm... You have a variable called stack and yet it isn't a stack structure, it's only an array. Using a somewhat real stack structure can be helpful. In the code below, I have used the LinkedList class to provide this structure (Even though there is also a Stack class, I like the Deque interface and wanted to go with LinkedList).

In this code, I have improved the variable names, the return type, and I am using a HashSet to store all "special" characters in. The contains method of a HashSet is performing in constant speed, so you should not experience any significant lack of performance. I noticed that in your if-statement, you had hard-coded the values that were put into your HashMap, this is what made me want to add the HashSet.

To make this work, I had to flip the key/values of your HashMap. The key is now the starting character, and the target is the expected ending character.

The loop through the string here is pretty simple and straight-forward:

• Have we waited for this character? If so, remove it from the list of expected characters we are waiting for (The "stack")
• If the above is not true, does this character have a matching ending character? If it does, add it to the stack
• Again, if the above also is not true, is this character regarded as a special character? If it is, then we know here already that we have failed so we can return from the method.

public boolean simonsVerify(String input) {
HashMap<Character, Character> matches = new HashMap<Character, Character>();
matches.put('{', '}');
matches.put('(', ')');
matches.put('[', ']');

Set<Character> specialChars = new HashSet<Character>();
for (Entry<Character, Character> ee : matches.entrySet()) {
}

for (int i = 0; i < input.length(); i++) {
char next = input.charAt(i);
Character expect = expected.peekLast();
if (expect != null && expect == next) {
expected.removeLast();
}
else if (matches.containsKey(next)) {
}
else if (specialChars.contains(next)) {
return false;
}
}
return true;
}


Here is the testing (with JUnit) I used, for both your original code and also for my method:

@Test
public void testVerifying() {
assertTrue(verify("{,},({,}),[,]"));

assertFalse(verify("{(,},({,}),[,]"));
assertFalse(verify("{,)},({gfdgfd}),[,]"));
assertFalse(verify("{(,}),({,}),[,]"));

assertTrue(verify("{,},(,),[[,]]"));
assertTrue(verify("{,},(,),[,]"));
assertTrue(verify("{{,}},(,),[,]"));
assertTrue(verify("{,},((,)),[,]"));
assertTrue(verify("{,},(,),[,]"));
assertTrue(verify("(), {{{,}}},(,),[,]"));
}


There might even be a better way to do this algorithm, this is just my way.

-
Well, this was a coding challenge at Codility.com and the return type had to be an int to pass the test cases :). So I am not "entirely" at fault :D. But all your points definitely make a lot of sense. I have not been an active part of the online community, but I think it will definitely help me learn a lot. Thanks!! –  Pankaj Feb 14 at 22:19
Why no spaces in "i=0"? –  Alexis Wilke Feb 14 at 22:21
@AlexisWilke Because I missed them :) Thanks! –  Simon André Forsberg Feb 14 at 22:24
@Pankaj Just added a review of the algorithm itself. –  Simon André Forsberg Feb 14 at 22:57
specialChars should just be a set of the closing delimiters, and should be renamed accordingly. You would only reach if (specialChars.contains(next)) when next is not an opening delimiter. –  200_success Feb 15 at 2:33

Using an array as a simplistic stack can work, as long as you are confident that your input is reasonably sized. However, I think your code is repetitive: the giant if condition fails to take advantage of the HashMap.

public class DelimiterMatcher {
private static final HashMap<Character, Character> DELIMITERS = new HashMap<Character, Character>();
static {
DELIMITERS.put('(', ')');
DELIMITERS.put('{', '}');
DELIMITERS.put('[', ']');
}
private static final Collection<Character> CLOSING_DELIMITERS = DELIMITERS.values();

public static boolean hasMatchingDelimiters(String s) {
char[] stack = new char[s.length() / 2 + 1];
int last = 0;
try {
for (int i = 0; i < s.length(); i++) {
char next = s.charAt(i);
Character closingDelimiter;
if (next == stack[last]) {
// Found expected closing delimiter.  Pop it from the stack.
--last;
} else if ((closingDelimiter = DELIMITERS.get(next)) != null) {
// Found opening delimiter.  Push the corresponding closing
// delimiter onto the stack.
stack[++last] = closingDelimiter;
} else if (CLOSING_DELIMITERS.contains(next)) {
// Found unexpected closing delimiter
return false;
}
}
return last == 0;
} catch (ArrayIndexOutOfBoundsException tooManyOpenOrCloseDelimiters) {
return false;
}
}
}

-

Just to add different approach for the given problem. I was thinking that it is the typical problem using the stack so I am adding an approach that is using the system stack and recursion instead the user stack. I incorporated the great idea of the maps from the previous answer.

private static final Map<Character, Character> DELIMITERS = new HashMap<Character, Character>();

static {
DELIMITERS.put('(', ')');
DELIMITERS.put('{', '}');
DELIMITERS.put('[', ']');
}
private static final Collection<Character> CLOSING_DELIMITERS = DELIMITERS.values();

public static void main(String[] args) {
String s = "{(65)45dfa";
final CharacterIterator it = new StringCharacterIterator(s);

System.out.println(new CorrectBrackets().areDelimitersCorrect(CharacterIterator.DONE, it, it.current()));
}

public boolean areDelimitersCorrect(Character closingDelimiter, CharacterIterator it, Character currentCharacter) {
boolean correctDelimitersInside = true;
while (currentCharacter != CharacterIterator.DONE && correctDelimitersInside) {
if ( currentCharacter.equals(closingDelimiter) ){
return true;
}
//If it is not my closing delimiter but it is some other closing delimiter then it is wrong
if ( CLOSING_DELIMITERS.contains(currentCharacter) ){
return false;
}
//If there is an opening one lets recurse.
if (DELIMITERS.containsKey(currentCharacter)) {
correctDelimitersInside = areDelimitersCorrect(DELIMITERS.get(currentCharacter), it, it.next());
}
currentCharacter = it.next();
}

//Check if all the inside was correct plus if I am closing correctly.
return correctDelimitersInside && currentCharacter.equals(closingDelimiter);
}

-