java 中检查正确的括号问题

Question

如果满足以下条件，则输入字符串有效：

左括号必须由相同类型的括号闭合。
左括号必须以正确的顺序闭合。

请注意，空字符串也被视为有效。

这是我的代码：

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        int len = s.length();
        for(int i=0;i<len;i++){
            char cur = s.charAt(i);
            if(cur=='{'){
                stack.push('{');
            }
            else if(cur=='['){
                stack.push('[');
            }
            else if(cur =='('){
                stack.push('(');
            }
            else if(stack.peek()=='(' && cur==')'){
                System.out.println(stack.peek());
                stack.pop();
            }
            else if(stack.peek()=='[' && cur==']'){
                stack.pop();
            }
            else if(stack.peek()=='{' && cur=='}'){
                stack.pop();
            }

        }

        if(stack.empty()) return true;
        else return false;

    }

}

当我给出输入时：

")"

我收到一个错误：

java.util.EmptyStackException

在我检查 ')' 条件的行中。请解释

Answer 1

我猜你正在解决 LeetCode 20，你可以稍微简化你的代码。例如，return stack.isEmpty(); 就足以满足您的 return 语句。

以下是更具可读性的版本：

Java

class Solution {
    public boolean isValid(String baseString) {
        Stack<Character> stack = new Stack<Character>();

        for (char character : baseString.toCharArray()) {
            if (character == '(')
                stack.push(')');

            else if (character == '{')
                stack.push('}');

            else if (character == '[')
                stack.push(']');

            else if (stack.isEmpty() || stack.pop() != character)
                return false;

        }

        return stack.isEmpty();
    }
}

C++

class Solution {
    public boolean isValid(String baseString) {
        Stack<Character> stack = new Stack<Character>();

        for (char character : baseString.toCharArray()) {
            if (character == '(')
                stack.push(')');

            else if (character == '{')
                stack.push('}');

            else if (character == '[')
                stack.push(']');

            else if (stack.isEmpty() || stack.pop() != character)
                return false;

        }

        return stack.isEmpty();
    }
}

Python

class Solution:
    def isValid(self, base_string):
        memo = {')': '(', '}': '{', ']': '['}
        stack = [0]
        for character in base_string:
            if character in memo:
                if stack.pop() != memo[character]:
                    return False
            else:
                stack.append(character)
        return stack == [0]

参考

Solution

java 中检查正确的括号问题

Checking correct brackets question in java

java

algorithm

brackets

Java

C++

Python

参考