How to check for balanced brackets WITHOUT a stack/regex?

Question

So basically before people start questioning why I'm not using a stack to save time over using counters and stuff. This is a homework problem working with space complexity, so ignoring time complexity, we are attempting to reduce space complexity.

To do so, I have to use counters to keep track of the brackets.

Possible bracket types: '(' ')' '[' ']'

I've tried some coding but I seem to be having a problem with one of the test strings, and I just can't pinpoint where the problem is happening.

Boolean isWF(String w) {
// maxLevel is found and any variables I'm using has been initialized

  for(int i = 0; i < maxLevel; i++) {
      x = w.charAt(i);
      currentLevel = i;

      if(x == '(' || x == '[') {
        holder = x; // Store bracket here to check match
        savedLevel++;
        counter++;
        currentLevel++;

        for(int j = i+1; j < w.length(); j++) {
          x = w.charAt(j);

          if(x == '(' || x == '[') {
            currentLevel++; 
            if(currentLevel == savedLevel) {
              holder = x;
              counter++;
            }
          }
          else if(x == ')' || x == ']') {
            if(currentLevel == savedLevel) {
              if((holder == '(' && x == ')') || (holder == '[' && x == ']')) {
                currentLevel--;
                counter--;
              }
              else
                return false;
            }
            else {
              currentLevel--;
            }
          }
        }
      }
      else if(x == ')' || x == ']') {
        counter--;
        if(counter < 0) {
          return false;
        }
      }
    }
    if(counter != 0) {
      return false;
    }

    return true;
  }
}

The strings I'm testing:

()[] - expected to be true, actual is true
([)] - expected to be false, actual is false
[([([()])])] - expected to be true, actual is true
([()([])()][()(())]()) - expected to be true, actual is false
([()([])())[()(())]()) - expected to be false, actual is false

[What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173) — Andy Turner, Apr 16 '19 at 19:27
What's your theory on how this works? Because I don't see a way to keep track of the [ and ( without using a stack or something similar. I suspect that's your problem. — markspace, Apr 16 '19 at 19:29
you could also show us the entire assignment so we know what is allowed for exampel are you allowed to save the brackets in a string ? — jonathan Heindl, Apr 16 '19 at 19:29
@markspace i guess you could transform them into numbers to create the illusion that your not saving them oO — jonathan Heindl, Apr 16 '19 at 19:30
you could solve it recursively :o how about creating a function that you pass the current index and bracket type that calls itself if it encounters a new open bracket with the new bracket or aborts with false if it encounters a different clsoe bracket than you started with ... but to be honest while your not using "a" stack this method just keeps the references on "the" stack — jonathan Heindl, Apr 16 '19 at 19:33
You could use a HashMap (aka. dictionary) where the key is a character and the value its the counter. — acarlstein, Apr 16 '19 at 19:36
@acarlstein wouldnt help since you alos need the order of types not jsut the count — jonathan Heindl, Apr 16 '19 at 19:38
@jonathanHeindl woops, somehow my eyes glanced right over that without seeing it. — Nick Vitha, Apr 16 '19 at 19:48
@Amai second case is also wrong (probably I assumed all the other variables initialized to 0) ok now i initialized maxLEvel to 1 (makes sense :D) and its all green no faults ? — jonathan Heindl, Apr 16 '19 at 19:48
@Amai have you checked for typos in your test cases ? or forgot to reinitialize a variable between the tests ? — jonathan Heindl, Apr 16 '19 at 19:51
@Amai can you edit in your initialization for the variables so we can more easily run the code? — Nick Vitha, Apr 16 '19 at 19:55
@Amai You could solve this in 3 passes? First pass check that the `()` are balanced. Second pass, check that `[]` are balanced. Third pass check that there are no 'invalid' pairs such as `[)`, or `(]`. — user268396, Apr 16 '19 at 20:51

Cratylus · Accepted Answer · 2019-04-19T19:18:41.737

1

Not a direct answer to where is the bug in your approach but the following approach seems to solve your input cases and is much simpler. Basically you go over the string checking if the next symbol is one you can accept e.g. you can't accept a ) right after a [ and you keep a count of the open/close of brackets. If they ever go negative it means you are missing something.

public static boolean isBalanced(String s) {
        int sOpen = 0;
        int rOpen = 0;
        for(int i = 0; i < s.length() - 1; ++i) {
            final char current = s.charAt(i);
            final char next = s.charAt(i + 1);
            if(!isValidSymbol(current, next)) {
                return false;
            }
            if(current == '(') rOpen++;
            else if(current == '[') sOpen++;
            else if(current == ')') rOpen--;
            else if(current == ']') sOpen--;
            if(rOpen < 0 || sOpen < 0) return false;
        }
        final char lastChar = s.charAt(s.length() - 1);
        if(lastChar == '(') rOpen++;
        else if(lastChar == '[') sOpen++;
        else if(lastChar == ')') rOpen--;
        else if(lastChar == ']') sOpen--;

        return s.length() > 1 && rOpen == 0 && sOpen == 0;
    }

    private static boolean isValidSymbol(char from, char to) {
        if(from == '(') {
            return to == ')' || to == '['  || to == '(' ;
        }
        else if(from == '[') {
            return to == ']' || to == '(' || to == '[';
        }
        return true;        
    }


public static void main(String[] args) {
        String testInput = "()[]";
        assert isBalanced(testInput) : "expected true";

        testInput = "([)]";
        assert isBalanced(testInput) == false : "expected false";

        testInput = "[([([()])])]";
        assert isBalanced(testInput) : "expected true";


        testInput = "([()([])()][()(())]())";
        assert isBalanced(testInput) : "expected true";

        testInput = "([()([])())[()(())]()) ";
        assert isBalanced(testInput) == false : "expected false";

    }

edited Apr 19 '19 at 19:18

answered Apr 16 '19 at 19:35

Cratylus

52,998
69
209
339

usual starting thought but doesnt differentiate between the types – jonathan Heindl Apr 16 '19 at 19:35
this one would evaluate to true : ( [ ) ] – jonathan Heindl Apr 16 '19 at 19:36
And just dropping code at people without explanations ... beyond that, I think the OP is more looking to find out why *his* solution isn't working. – GhostCat Apr 16 '19 at 19:38
@jonathanHeindl: I added another answer – Cratylus Apr 17 '19 at 19:43
@GhostCat actually I copied the example code into a junit test just as is (initialized all variables to 0 except maxLevel to 1) and it did work – jonathan Heindl Apr 17 '19 at 20:47
@Cratylus while your code seems alright liek ghostCat said its not directly a solution for ops question – jonathan Heindl Apr 17 '19 at 20:49
1

@jonathanHeindl: Indeed but from my point of view, when someone asks how to fix their approach to a problem their concern to begin with is a solution to the problem. So pointing out a much simpler way to solve what they need is always a better way. – Cratylus Apr 17 '19 at 21:31
Doesn't this break on the most trivial of cases like `((((`? It doesn't actually check at the end of the `for` loop to make sure the counters remain `0` (if they are non-zero that would be unbalanced). – user268396 Apr 19 '19 at 18:07
@user268396: I have considered that input of `(` is invalid. You think it should be considered as valid? – Cratylus Apr 19 '19 at 18:08
I meant a sequence of `(`, e.g. 2 or more of those. – user268396 Apr 19 '19 at 18:09
@user268396: Passing `((((` returns `false` – Cratylus Apr 19 '19 at 18:13
1

No, it really doesn't. :) In fact, if you have a balanced string you can append any one character and your method will not detect this because you only check based on `current` and do not fully evaluate `next`. – user268396 Apr 19 '19 at 18:19
@user268396: Is there any other input that won't work? – Cratylus Apr 22 '19 at 19:58
Well with your last modification your code will blow up on an empty string, because you wind up trying to invoke `s.charAt(-1)`. Also,more generally if `s.length()` is odd you know the string must be unbalanced. – user268396 Apr 24 '19 at 19:53
@user268396: Yes I am ignoring null or empty input and my question was about the core algorithm – Cratylus Apr 24 '19 at 20:29

How to check for balanced brackets WITHOUT a stack/regex?

1 Answers1