Как проверить наличие сбалансированных скобок БЕЗ стека / регулярных выражений?

Question

Итак, прежде чем люди начнут задавать вопросы, почему я не использую стек для экономии времени по сравнению с использованием счетчиков и прочего. Это домашняя задача, связанная с пространственной сложностью, поэтому, игнорируя временную сложность, мы пытаемся уменьшить сложность пространства.

Для этого мне нужно использовать счетчики, чтобы отслеживать скобки.

Возможные типы скобок: '(' ')' '[' ']'

Я попробовал немного кодирования, но, похоже, у меня проблема с одной из тестовых строк, и я просто не могу точно определить, где происходит проблема.

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;
  }
}

Струны, которые я тестирую:

()[] - 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

Answer 1

Не прямой ответ на вопрос, где ошибка в вашем подходе, но следующий подход, кажется, решает ваши входные случаи и намного проще.По сути, вы перебираете строку, проверяя, является ли следующий символ тем, который вы можете принять, например, вы не можете принять ) сразу после [ и сохраняете счетчик открытых / закрытых скобок.Если они когда-нибудь станут отрицательными, значит, вы что-то упустили.

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";

    }