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

Question

我有一个方法，该方法应该使用java验证字符串中准确的左括号和右括号。此方法将用于解析数学表达式，因此平衡括号很重要。出于某种原因，在这两次运行中都返回false：

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

下面是使用堆栈解决问题的方法。这里有些错误，因为对于一组平衡的括号，它也返回false。有什么问题吗？先谢谢你

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

}

下面是我正在使用的堆栈类：

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或更少，则会给出first char=“”，因此，由于堆栈为空，您将退出循环

注：这在java 1.8split difference between java 1.7 and 1.8中已更改

改为：

char[] tokens = str.toCharArray();

我猜想，你需要考虑的事实是，在你的第一个^ {{CD3}}之前可以有字符，并且你可以有其他字符，然后^ {< CD3>}和^ {CD5>}

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