Balanced parenthesis, with backslash escaping

Question

Given a Balanced Parenthesis problem.

"Balanced Parenthesis

Create a program that checks if in a given string expression all the parenthesis are balanced.

For Example:

(test) - valid

(no() - invalid

()(()) - valid

(123(456)(7))( - invalid

(val()id) - valid

Also, take into account the "\" escape sequences:

(nope\) - invalid

(v\(al) - valid

Too easy? Try doing the same for [] and {} and <>.

(The description from Sololearn application)"

This is my solution. Do you have any advice? Is it clear enough?

import java.util.Stack;

public class BalancedParenthesis {

private static final Stack<Character> STACK = new Stack<>();
private static final String BRACELETS = "({[<)}]>";
private static final int SEPARATOR = BRACELETS.length() / 2;
private static final char BACKSLASH = '\\';

public static boolean isBalanced(String str) {
    int index; char ch;
    STACK.clear();
    for (int pos = 0; pos < str.length(); pos++) {
        ch = str.charAt(pos);
        if (ch == BACKSLASH) {
            pos ++;
            continue ; }
        index = BRACELETS.indexOf(ch);
        if (isBaceletFind(index)) {
            if (isOpenBracelet(index)) STACK.push(ch);
            else if (isPopable(index)) STACK.pop();
            else return false; }
    }
    return STACK.empty();
}

private static boolean isPopable(int index) {
    return !STACK.empty() && STACK.peek() == BRACELETS.charAt(index - SEPARATOR);
}

private static boolean isBaceletFind(int index) {
    return index != -1;
}

private static boolean isOpenBracelet(int index) {
    return index < SEPARATOR;
}

public static void checkBalance(String str) {
    System.out.print("\"" + str + "\" is");
    System.out.println((isBalanced(str) ? "" : " not") + " balanced");

}
public static void main(String[] args) {
    checkBalance("");
    checkBalance("\\");
    checkBalance("\\(");
    checkBalance("(({[<>]}))");
    checkBalance("))");
    checkBalance("(({[<(>]}))");
    checkBalance("(({[<\\(>]}))");
}
}

Answer 1

Superficial remarks

Whats a "bacelet", in isBaceletFind()? Did you mean "bracelet"? Even that is questionable English terminology, as I would take it to mean a piece of jewelry worn at the wrist. Or maybe you meant "bracket"?

isPopable() should be isPoppable().

I normally don't like to be pedantic about brace styles, but the one you use for your if statements is really very unconventional, and certainly not easy to read. Wikipedia lists 8 common brace styles, and yours is not any of them. In fact, I'd say that it's the first time I've ever seen it in use.

Data structure

java.util.Stack is deprecated, because it has bad object-oriented design (it allows random access because it extends java.util.Vector), and because its methods are synchronized (which incurs unnecessary performance overhead). Normally, the recommended replacement for Stack is ArrayDeque. However, in this case, since each element is a char, I'd use a StringBuilder instead, so that you don't have to incur the char ↔︎ Character boxing/unboxing overhead.

Even if your code works, it's a bad practice to write:

private static final Stack<Character> STACK = new Stack<>();

• static means that there is only one instance shared throughout the Java interpreter. Having to write STACK.clear() at the beginning of isBalanced() is ugly. It also unnecessarily introduces the possibility of multithreading problems, when isBalanced() should be a simple deterministic function with no threading issues.
• The ALL_CAPS name suggests that it's a constant, which it isn't in nature, even if it's technically a final variable.

Instead, isBalanced() should instantiate the stack as a local variable, and explicitly pass it to any helper function that needs it.

Algorithm

I'm not a big fan of the BRACELETS constants, with the first half being the opening delimiters, with their counterparts in the second half. I think it's more cryptic than it needs to be. I'd just write a switch containing all of the characters of interest: it compiles to very clean and efficient bytecode, even simpler than String.indexOf().

When you encounter an opening delimiter, it would be smarter to push its counterpart onto the stack instead. That way, you don't have to repeatedly ask "is this the right closing delimiter?" when looking at every subsequent character.

public class BalancedParenthesis {
    private static class CharStack {
        private StringBuilder sb = new StringBuilder();
        public boolean isEmpty() { return this.sb.length() == 0; }
        public void push(char c) { this.sb.append(c); }
        public char pop() {
            char last = this.sb.charAt(this.sb.length() - 1);
            this.sb.setLength(this.sb.length() - 1);
            return last;
        }
    }

    public static boolean isBalanced(String str) {
        CharStack stack = new CharStack();
        for (int pos = 0; pos < str.length(); pos++) {
            char ch = str.charAt(pos);
            switch (ch) {
              // Backslash: ignore the next character
              case '\\': pos++; continue;

              // Opening delimiters
              case '(':  stack.push(')'); break;
              case '{':  stack.push('}'); break;
              case '[':  stack.push(']'); break;
              case '<':  stack.push('>'); break;

              // Closing delimiters
              case ')':
              case '}':
              case ']':
              case '>':
                if (stack.isEmpty() || stack.pop() != ch) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

Answer 2

I am not a pro Java programmer, so I will only talk about the algorithm

Your reasoning is good, a stack is the right container to use, but:

• You don't catch the case where backslash itself is escaped
• You can avoid SEPERATOR in two way:
  • build your list like "(){}[]<>" and check if index is odd or not
  • make two list, one for openings, one for closures
• Try do don't call str.length() each time (not sure about overhead in java).
• You maybe define too much function for nothing.
• For your checkBalance(...), it would be nice if you supplied what's the expected value as second parameter.

So it would give something like this:

private static final Stack<Character> STACK = new Stack<>();
private static final char BACKSLASH = '\\';
private static final String BRACELETS = "(){}[]<>";

public static boolean isBalanced(String str) {
    int index;
    char ch;
    int length = str.length();
    boolean escaped = false;
    STACK.clear();
    for (int pos = 0; pos < length; pos++) {

      ch = str.charAt(pos);
      if (escaped || ch == BACKSLASH) {
        escaped = !escaped;
      }
      else {
        index = BRACELETS.indexOf(ch);
        if (index != -1) {
          if (index % 2 == 0) { STACK.push(ch); }
          else if (!STACK.empty() && STACK.peek() == BRACELETS.charAt(index-1)) {
            STACK.pop();  
          }
          else return false; 
        }
      }
    }
    return STACK.empty();
}

public static void checkBalance(String str, boolean expected) {
    boolean result = isBalanced(str);
    System.out.print("[" + (result == expected ? "OK" : "ERROR") + "] ");
    System.out.print("'" + str + "' " + (result ? "is" : "is not") + " balanced\n");

}
public static void main(String[] args) {
    checkBalance("", true);
    checkBalance("\\", true);
    checkBalance("\\(", true);
    checkBalance("()", true);
    checkBalance("(({[<>]}))", true);
    checkBalance("))", false);
    checkBalance("(({[<(>]}))", false);
    checkBalance("(({[<\\(>]}))", true);
    checkBalance(")(", true); //oops
}