Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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;
    }
}
share|improve this question

3 Answers 3

up vote 6 down vote accepted

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>();
    Deque<Character> expected = new LinkedList<Character>();
    for (Entry<Character, Character> ee : matches.entrySet()) {
        specialChars.add(ee.getKey());
        specialChars.add(ee.getValue());
    }

    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)) {
            expected.addLast(matches.get(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.

share|improve this answer
    
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
1  
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;
        }
    }
}
share|improve this answer

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);
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.