如何在没有堆栈/正则表达式的情况下检查平衡括号？

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

    }