无法正确验证java方法中的平衡括号解析

Question

我有一个方法，它应该验证在使用java的字符串中准确打开和关闭括号。这个方法将被用来解析数学表达式，所以对括号进行平衡很重要。出于某种原因，它在这两个运行的返回false：

System.out.println(parChecker("(()")); // returns false :-) 
System.out.println(parChecker("((()))")); // returns false :-( WHY?? 

下面是一个使用栈来解决问题的方法。有些事情是错误的，因为它也是一个平衡的括号。有什么问题？先谢谢你。

public static boolean parChecker(String str) { 
    String[] tokens = str.split(""); 
    int size = tokens.length; 
    Stack theStack = new Stack(size); 
    int index = 0; 
    boolean balanced = true; 
    while ((index < size) && balanced) { 
     String symbol = tokens[index]; 
     if (symbol.equals("(")) { 
      theStack.push(symbol); 
     } else { 
      if (theStack.isEmpty()) { 
       balanced = false; 
      } else { 
       theStack.pop(); 
      } 
     } 
     index++; 
    } 

    if (balanced && theStack.isEmpty()) { 
     return true; 
    } else { 
     return false; 
    } 

} 

下面是我用我的Stack类：

public class Stack { 

    private Object [] stack; 
    private int maxSize = 0; 
    private int top; 

    public Stack(int size){ 
     maxSize = size; 
     stack = new Object[maxSize]; 
     top = -1; 
    } 

    public void push(Object obj){ 
     top++; 
     stack[top] = obj; 
    } 

    public Object pop(){ 
     return stack[top--]; 
    } 

    public Object peek(){ 
     return stack[top]; 
    } 

    public boolean isEmpty(){ 
     return (top == -1); 
    } 

    public boolean isFull(){ 
     return (top == maxSize -1); 
    } 
} 

Answer 1

眼前的问题是这样的

String[] tokens = str.split(""); 

给你第一个字符= “” 如果你使用java 1.7以下，所以你会退出你的循环，因为堆栈是空的...

注意：这已在java 1.8split difference between java 1.7 and 1.8

变化：

char[] tokens = str.toCharArray(); 

然而，我想，你需要考虑的是，有可能在你的第一(是字符，而您可能有其他字符，然后(和)

Answer 2

据我所知，代码没有问题（证明这是一个Java 7特定问题。））。

我想，虽然提供了一个替代方法，用于教育目的，就是短，并且是宽容的其他人物存在：

public static boolean parChecker(String str) { 
    Stack stack = new Stack(str.length()); 
    for (char c : str.toCharArray()) 
     switch (c) { 
     case '(': 
      stack.push(c); 
      break; 
     case ')': 
      if (stack.isEmpty() || stack.pop() != Character.valueOf('(')) 
       return false; 
     } 
    return stack.isEmpty(); 
} 

按照要求，这里是另一种解决方案是不使用堆栈：

public static boolean parChecker(String str) { 
    str = str.replaceAll("[^()]", ""); 
    while (str.contains("()")) 
     str = str.replace("()", ""); 
    return str.isEmpty(); 
} 

还有一对道路：@ FredK的算法：

public static boolean parChecker(String str) { 
    int depth = 0; 
    for (char c : str.toCharArray())  
     if ((depth += c == '(' ? 1 : c == ')' ? -1 : 0) < 0) 
      return false; 
    return depth == 0; 
}