無法正確驗證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; 
}