3
\$\begingroup\$

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

    private void initCharMap(Map<Character,Character> charMap){
        charMap.put('(',')');
        charMap.put(')','(');
        charMap.put('[',']');
        charMap.put(']','[');
        charMap.put('{','}');
        charMap.put('}','{');
        charMap.put('<','>');
        charMap.put('>','<');
    }

    private void initDelimitDics(Map<Character,Integer> delimitMap){
        delimitMap.put('(',0);
        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<Character,Integer> 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?

\$\endgroup\$
  • 1
    \$\begingroup\$ One issue with your code is that a)test( returns as a balanced expression, although the bracket is closed before being opened. \$\endgroup\$ – assylias Apr 8 '12 at 22:34
  • \$\begingroup\$ And another one (but you probably already know that) is that you don't cover the second part of the requirement on the effect of ", ' and \. \$\endgroup\$ – assylias Apr 8 '12 at 22:36
  • \$\begingroup\$ @assylias - Thanks for pointing out the issue with the logic. I guess I need to maintain two different Maps, one for opening delimiter and one for closing delimiter. The appropriate entry in the right collection will be incremented based on whether it is an opening or a closing delimiter. After all the characters have been processed, the entries of these two maps will be examined for whether they have the same number of opening or closing delimiters. This is too much bookkeeping though. There should be a simpler/more elegant way to solve this problem in a streaming fashion. \$\endgroup\$ – sc_ray Apr 9 '12 at 1:41
  • \$\begingroup\$ Perhaps consider java.util.Stack or anything that is equivalent to it. \$\endgroup\$ – minopret Apr 9 '12 at 6:46
  • 1
    \$\begingroup\$ @sc_ray This is one way to do it: stackoverflow.com/a/3918697/829571 \$\endgroup\$ – assylias Apr 9 '12 at 7:43
3
\$\begingroup\$

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

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

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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