Java 中的有效括号

Question

代码：

public static void main(String[] args) {
    Arrays.asList("a+(b*c)-2-a", "(a+b*(2-c)-2+a)*2", "(a*b-(2+c)", "2*(3-a))", ")3+b*(2-c)(")
            .stream().forEach((expression) -> {
                if (replaceAll(expression, "[(]") == replaceAll(expression, "[)]")) {
                    System.out.println("correct");
                } else {
                    System.out.println("incorrect");
                }
            });
}

private static int replaceAll(String word, String regex) {
    int count = word.length() - word.replaceAll(regex, "").length();
    return count;
}

我必须检查表达式是否有效。决定表达式是否有效的是括号。自闭则有效，否则无效。

我的代码几乎正确，正在打印：

correct
correct
incorrect
incorrect
correct

但必须打印

correct
correct
incorrect
incorrect
incorrect -> the last expression isn't valid.

Answer 1

您不仅需要检查左括号的数量是否与右括号的数量相匹配，而且还需要检查每个右括号是否都在左括号之后，而左括号还不是 "closed"：

static boolean checkParentheses(String s) {
     int opened = 0;
     for (int i = 0; i < s.length(); i++) {
         if (s.charAt(i) == '(')
             opened++;
         else if (s.charAt(i) == ')') {
             if (opened == 0)    // means that all parentheses are "closed" yet
                return false;
             opened--;
         }
     }
     return opened == 0;
}

如果您确实需要使用正则表达式，请执行以下操作：

static boolean checkParentheses(String s) {
    // capture a text starting with one opening parenthesis, 
    // ending with one closing and having no parentheses inside
    Pattern p = Pattern.compile("\([^()]*\)");  
    Matcher m;
    while ((m = p.matcher(s)).find())
       s = m.replaceAll("");
    return !(s.contains("(") || s.contains(")"));
}

Answer 2

您可以一个字符一个字符地检查它，并使用计数器来判断语句中的括号级别。

boolean valid = true;
int level = 0;
for(int i=0; i < expr.length(); i++) {
    if(expr.charAt(i) == '(') level++;
    if(expr.charAt(i) == ')') level--;
    if(level < 0) { // ) with no (
        valid = false; 
        break;
    }
}
if(level > 0) valid = false; // ( with no )
return valid; // true if level returned to 0

Answer 3

你的问题是仅仅计算括号是不够的；您还需要找出 ')' 来得太早的地方。例如 ")(" 无效，即使左括号和右括号的数量相同。

一种方法是进行计数。从零开始。每次看到“(”，count++。每次看到“)”，count--。

递减后，if(count<0)输入无效。

输入结束，if(count!0)输入无效

有人指出，这不能在单个正则表达式中完成。那是因为正则表达式表示 finite 状态机。 count原则上可以无限增加。

如果您选择最大嵌套深度，您可以编写一个正则表达式来检查它。例如，最大深度为 3：

x*(<x*(<x*(<x*>)*x*>)*x*>)*x*

（为了可读性，我在这里使用 'x' 而不是任意字符。将其替换为 [^<>] 以实际匹配其他字符。我还使用 <> 而不是\(\) 再次为了可读性。这里的 () 是为了分组。）。

您始终可以通过将中间的 x* 替换为 x*(<x*>)*x* 使其更深地工作一个级别——但是您永远无法制作一个不会在特定深度停止工作的正则表达式.

另一种方法更接近于真正的语句解析器对嵌套结构所做的处理：递归。像（伪代码）：

def consumeBlock() {
    switch(next char)
       case end-of-input
          throw error -- reached end of input inside some parentheses 
       case '('
          consumeBlock() -- go down a nesting level
          break;
       case ')'
          return -- go up a nesting level
       default
          It's an uninteresting character. Do nothing.
          (a real parser compiler would do something more interesting)
}

这里 consumeBlock() 假设您刚刚消费了一个“(”并且您打算阅读直到它的对。

您的一些输入不是以“(”开头的，因此请先在末尾附加一个“)”，作为您所说的 "silent"“)”的对已经吃完了。

伪代码已经表明，如果您在块中输入结束，则它是无效输入。此外，如果您在顶层调用 consumeBlock() returns 时未处于输入末尾，则它是无效输入。

Java 中的有效括号

Valid parentheses in Java

java

regex

replaceall