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 <>, 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 delimitMap;
private Map charMap;
public BalancedDelimiters(){
delimitMap = new LinkedHashMap();
charMap = new LinkedHashMap();
initDelimitDics(delimitMap);
initCharMap(charMap);
}

private void initCharMap(Map charMap){
charMap.put('(',')');
charMap.put(')','(');
charMap.put('[',']');
charMap.put(']','[');
charMap.put('{','}');
charMap.put('}','{');
charMap.put('');
charMap.put('>',' delimitMap){
delimitMap.put('(',0);
delimitMap.put(')',0);
delimitMap.put('[',0);
delimitMap.put('{',0);
delimitMap.put('',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 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;
}

ret

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 blockDelimiters = new HashMap();
    static {
        blockDelimiters.put('(', ')');
        blockDelimiters.put('[', ']');
        blockDelimiters.put('{', '}');
        blockDelimiters.put('');
    }

    private static final Set stringDelimiters = new HashSet();
    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 < 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 < 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).

StackExchange Code Review Q#10712, answer score: 3