2
\$\begingroup\$

Is this code okay?

import java.util.Stack;

public class DelimiterMatching {

    public static void main(String[] args) {

        final String input = "[(A+B)]";

        delimiterCheck(input);
    }

    public static void delimiterCheck(String input) {
        if (input.length() == 0) {
            System.out.println("String is empty");
        }
        Stack<Character> theStack = new Stack<>();
        for (int i = 0; i < input.length(); i++) {
            char individualChar = input.charAt(i);
            if (individualChar == '{' || individualChar == '['
                    || individualChar == '(') {
                theStack.push(individualChar);

            } else if (individualChar == '}' || individualChar == ']'
                    || individualChar == ')') {
                if (!theStack.isEmpty()) {
                    char individualCharRight = theStack.pop();
                    if ((individualChar == '}' && individualCharRight != '{')
                            || (individualChar == ')' && individualCharRight != '(')
                            || (individualChar == ']' && individualCharRight != '[')) {
                        System.out.println("Error at index " + i);
                    }
                }
            }
        }
        if (!theStack.isEmpty()) {
            System.out.println("Error in delimiter");
        }
    }
}
\$\endgroup\$
7
\$\begingroup\$

Technically the code is broken: it will accept a ")" string as valid (test at line 25 doesn't flag an error if the stack is empty).

Naming

I think you got a bit overboard. Names shall be descriptive, which doesn't imply that they shall be long. individualCharRight is definitely confusing. I'd suggest something like innermost perhaps.

delimiterCheck also doesn't reflect the nature of the function. It is supposed to test a validity of nested brackets; isNested could be more to the point.

Error reporting

For a low level function I'd recommend to avoid printing anything, but return an error code instead. There are 2 clearly defined error conditions (an unbalanced closing bracket and an unclosed opening one); the method should return an error code and a position of an offending bracket. The latter observation means that a bracket position should be recorder at the stack along with the bracket itself.

Interface

As mentioned above, the method should return an error code and an error location.

\$\endgroup\$
6
\$\begingroup\$

I suggest making the code easier to maintain by storing the bracket pairs in

private static final char[] opening = new char[]{'(', '[', '{'};
private static final char[] closing = new char[]{')', ']', '}'};

then make a utility function wich gives you the matching index

private static int getOpenCode(char c)
private static int getCloseCode(char c)

both should return some -1 for not found and the index if found. Finally you can store the bracketing as a

Stack<Integer>

with codes corresponding to indices. The logic would change to

protected int checkBrackets(String input) {
// ...
if (getOpenCode(individualChar) != -1) { // Opening bracket
    theStack.push(getOpenCode(individualChar));
} else if (getCloseCode(individualChar) != -1) { // Closing bracket
    if (theStack.isEmpty() || theStack.pop() != getCloseCode(individualChar)) return -1; // Unbalanced
}
// ...
if (!theStack.isEmpty()) return -2; // Unclosed
return 0; // Okay
}

Note we are using an int return code instead of stdout so that the executing code can decide on how to report. You may also return a different code wich contains the erroneous index. The nice thing about this approach is its extensibility: If you want to support a new type of brackets, just append them to the static arrays.

\$\endgroup\$
  • \$\begingroup\$ Alex, you are welcome to contact me by gmail. \$\endgroup\$ – hardmath May 7 '15 at 17:01
6
\$\begingroup\$

I think {[( are not called "delimiters", they are called brackets. A delimiter is for example the comma in a CSV format, or the semicolon in a for (;;).

In fact the problem you're trying to solve is called checking if the brackets are balanced. So a better name for the method would be isBalanced, and it should return a boolean instead of void, to give you the flexibility to do with the result whatever you want. For example, you can print it, or better: use in unit tests.

Simplify

Your code looks a bit untidy, because of all the checks for the various bracket characters. One way to simplify is to generalize. For example here:

if (individualChar == '{' || individualChar == '['
        || individualChar == '(') {

Asking "is it X, or is it Y, or is it Z" is kind of the wrong question. The right question is actually: "is it an opening bracket"?

if (individualChar == '}' || individualChar == ']'
        || individualChar == ')') {

The same thing here too. The real question is: "is it a closing bracket"?

Finally:

if ((individualChar == '}' && individualCharRight != '{')
        || (individualChar == ')' && individualCharRight != '(')
        || (individualChar == ']' && individualCharRight != '['

The question is really, is individualChar the matching closing bracket for individualCharRight. (By the way individualCharRight is a really confusing name, considering that its expected values are {([...)

If you extract these conditions to methods and rewrite, the code magically becomes a lot more readable:

static boolean isBalanced(String input) {
    Stack<Character> stack = new Stack<>();
    for (char c : input.toCharArray()) {
        if (isOpeningBracket(c)) {
            stack.push(c);
        } else if (isClosingBracket(c)) {
            if (stack.isEmpty() || !isMatchingBrackets(stack.pop(), c)) {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

Implementing the helper methods is almost trivially easy:

private static boolean isOpeningBracket(char c) {
    return "({[".indexOf(c) > -1;
}

private static boolean isClosingBracket(char c) {
    return ")}]".indexOf(c) > -1;
}

private static boolean isMatchingBrackets(char opening, char closing) {
    switch (opening) {
        case '(': return closing == ')';
        case '{': return closing == '}';
        case '[': return closing == ']';
        default: return false;
    }
}

Notice that I simplified the if c == X || c == Y || ... conditions with a much simpler .indexOf call on a string with XYZ.

Unit tests

A non-trivial task like this really deserves some unit tests. How else can you be sure that if you touch anything in it it won't fall apart? Here are some example test cases:

@Test
public void testEmpty() {
    assertTrue(isBalanced(""));
}

@Test
public void testBalancedWithoutBrackets() {
    assertTrue(isBalanced("hello"));
    assertTrue(isBalanced("blah"));
}

@Test
public void testUnbalancedSingleChar() {
    assertFalse(isBalanced("("));
    assertFalse(isBalanced(")"));
    assertFalse(isBalanced("{"));
    assertFalse(isBalanced("}"));
    assertFalse(isBalanced("["));
    assertFalse(isBalanced("]"));
}

@Test
public void testNonBracketIgnored() {
    assertTrue(isBalanced("he(ll)o"));
    assertTrue(isBalanced("he(llo)"));
    assertTrue(isBalanced("(he)(()llo)"));
    assertFalse(isBalanced("(he)(()llo"));
    assertFalse(isBalanced("(he)()llo)"));
}

@Test
public void testComplicated() {
    assertTrue(isBalanced("()()(){}{}[]"));
    assertTrue(isBalanced("((()))"));
    assertTrue(isBalanced("(({()}{}[{hello}]))"));
    String balanced = "(({()}{}[{}]))";
    for (int i = 0; i < balanced.length(); ++i) {
        assertFalse(isBalanced(replaceCharAt(balanced, i, 'x')));
    }
}

private String replaceCharAt(String string, int i, char c) {
    return string.substring(0, i) + c + string.substring(i + 1);
}
\$\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.