Balanced delimiter method I was trying to solve the following Programming Praxis problem:


  Write a function that takes a string and determines if the delimiters
  in the string are balanced. The pairs of delimiters are (), [], {},
  and &lt;>, and delimiters may be nested. In addition, determine that
  string delimiters ‘ and ” are properly matched; other delimiters lose
  their magical delimiter-ness property within quoted strings. Any
  delimiter is escaped if it follows a backslash.


Here's my attempt to solve the problem:

import java.util.*;
public class BalancedDelimiters{
    private Map&lt;Character,Integer&gt; delimitMap;
    private Map&lt;Character,Character&gt; charMap;
    public BalancedDelimiters(){
         delimitMap = new LinkedHashMap&lt;Character,Integer&gt;();
         charMap = new LinkedHashMap&lt;Character,Character&gt;();    
         initDelimitDics(delimitMap);
         initCharMap(charMap);
    }

    private void initCharMap(Map&lt;Character,Character&gt; charMap){
        charMap.put('(',')');
        charMap.put(')','(');
        charMap.put('[',']');
        charMap.put(']','[');
        charMap.put('{','}');
        charMap.put('}','{');
        charMap.put('&lt;','&gt;');
        charMap.put('&gt;','&lt;');
    }

    private void initDelimitDics(Map&lt;Character,Integer&gt; delimitMap){
        delimitMap.put('(',0);
        delimitMap.put(')',0);
        delimitMap.put('[',0);
        delimitMap.put('{',0);
        delimitMap.put('&lt;',0);
        delimitMap.put('&gt;',0);
        delimitMap.put(']',0);
        delimitMap.put('}',0);
    }

    public boolean checkForBalance(String extractedString){
        int balancedIndicator = 0;
        char[] charArr = extractedString.toCharArray();
        for(char c:charArr){
            if(delimitMap.containsKey(c)){
                delimitMap.put(c,delimitMap.get(c)+1);
            }       
        }
        for(Map.Entry&lt;Character,Integer&gt; entry:delimitMap.entrySet()){
            System.out.println("Entry Key:"+entry.getKey()+"Entry value:"+entry.getValue());
            System.out.println("Complementary delimiter:"+charMap.get(entry.getKey()));
            if(delimitMap.get(charMap.get(entry.getKey())) != entry.getValue())
                return false;   
        }

        return true;
    }

}


Can somebody review my code and let me know how I would be able to improve this snippet?
In order to solve this problem you should either use a stack or recursion to keep track of the current nesting levels. The proposed solutions (including the linked one from assylias) will not do when you have multiple different delimiters and also string delimiters.

Here is a solution that seems to work based on recursion. It can probably be made a little shorter but i tried to keep it readable:

public class BalancedDelimiters {

    private static class NotBalancedException extends RuntimeException {
        private static final long serialVersionUID = 1L;
    }

    private static final Map&lt;Character, Character&gt; blockDelimiters = new HashMap&lt;Character, Character&gt;();
    static {
        blockDelimiters.put('(', ')');
        blockDelimiters.put('[', ']');
        blockDelimiters.put('{', '}');
        blockDelimiters.put('&lt;', '&gt;');
    }

    private static final Set&lt;Character&gt; stringDelimiters = new HashSet&lt;Character&gt;();
    static {
        stringDelimiters.add('\"');
        stringDelimiters.add('\'');
    }


    public boolean checkForBalance(String extractedString) {
        try {
            consume(extractedString, null);
            return true;
        } catch (NotBalancedException e) {
            return false;
        }
    }

    private String consume(String remainingString, Character currentDelimiter) {
        while (true) {
            int nextInterestingCharacter = getNextInterestingCharacter(remainingString);
            if (nextInterestingCharacter == -1) {
                if (currentDelimiter == null) {
                    return "";
                } else {
                    throw new NotBalancedException();
                }
            }

            char delimiter = remainingString.charAt(nextInterestingCharacter);
            remainingString = remainingString.substring(nextInterestingCharacter + 1);
            if (closes(delimiter, currentDelimiter)) {
                return remainingString;
            } else if (isBlockStartDelimiter(delimiter)) {
                remainingString = consume(remainingString, delimiter);
            } else if (isStringDelimiter(delimiter)) {
                remainingString = consumeToNextStringDelimiter(remainingString, delimiter);
            } else {
                throw new NotBalancedException(); // we found a delimiter that we could not use!
            }
        }
    }

    private int getNextInterestingCharacter(String remainingString) {
        for (int i = 0; i &lt; remainingString.length(); i++) {
            if (remainingString.charAt(i) == '\\') {
                i++; // also skip next character
            } else if (isAnyKindOfDelimiter(remainingString.charAt(i))) {
                return i;
            }
        }
        return -1;
    }

    private String consumeToNextStringDelimiter(String remainingString, char delimiter) {
        for (int i = 0; i &lt; remainingString.length(); i++) {
            if (remainingString.charAt(i) == '\\') {
                i++; // also skip next character
            } else if (remainingString.charAt(i) == delimiter) {
                return remainingString.substring(i + 1);
            }
        }
        throw new NotBalancedException();
    }

    private boolean closes(char delimiter, Character currentDelimiter) {
        if (currentDelimiter == null) {
            return false;
        }
        return blockDelimiters.get(currentDelimiter).equals(delimiter);
    }

    private boolean isAnyKindOfDelimiter(char c) {
        return isBlockDelimiter(c) || isStringDelimiter(c);
    }

    private boolean isBlockDelimiter(char c) {
        return isBlockStartDelimiter(c) || isBlockEndDelimiter(c);
    }

    private boolean isBlockStartDelimiter(char c) {
        return blockDelimiters.containsKey(c);
    }

    private boolean isBlockEndDelimiter(char c) {
        return blockDelimiters.containsValue(c);
    }

    private boolean isStringDelimiter(char c) {
        return stringDelimiters.contains(c);
    }
}


Note that I handle normal delimiters (i call them block delimiters) differently from string delimiters as they behave quite differently. I'm using an exception to control flow when the string is not balanced. Maybe some will find that a bit ugly but it saves a few lines of code (i think).