Java 字符串括号匹配验证算法 - 使用栈实现

Java 字符串括号匹配验证算法 - 使用栈实现

问题描述：

给定一个只包括 '(', ')', '{', '}', '[' 和 ']' 的字符串 s，判断字符串是否有效。

有效字符串需满足以下条件：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。
• 每个右括号都有一个对应的相同类型的左括号。

解法：

使用栈可以有效地判断字符串是否有效。遍历字符串，执行以下操作：

1. 当遇到左括号时，将其入栈。
2. 当遇到右括号时，判断栈顶元素是否与其匹配。
   • 如果匹配，则出栈；
   • 如果不匹配，则返回 false。
3. 最后判断栈是否为空。
   • 如果为空，则字符串有效，返回 true；
   • 如果不为空，则字符串无效，返回 false。

Java 代码实现：

class Solution {
    public boolean isValid(String s) {
        java.util.Stack<Character> stack = new java.util.Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                char top = stack.peek();
                if ((c == ')' && top == '(') || (c == '}' && top == '{') || (c == ']' && top == '[')) {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

代码解释：

1. 使用 java.util.Stack 类创建一个栈。
2. 遍历字符串 s 中的每个字符 c。
3. 如果 c 是左括号，将其入栈。
4. 如果 c 是右括号，判断栈是否为空。
   • 如果栈为空，则说明没有对应的左括号，返回 false。
   • 如果栈不为空，则获取栈顶元素 top，判断 c 和 top 是否匹配。
     • 如果匹配，则出栈；
     • 如果不匹配，则返回 false。
5. 遍历完字符串后，判断栈是否为空。
   • 如果栈为空，则说明所有左括号都匹配了右括号，返回 true。
   • 如果栈不为空，则说明存在没有匹配的左括号，返回 false。

示例：

• isValid('()') 返回 true。
• isValid('()[]{}') 返回 true。
• isValid('(]') 返回 false。
• isValid('([)]') 返回 false。
• isValid('{[]}') 返回 true。

总结：

使用栈可以有效地判断字符串是否有效，代码简洁易懂，并能有效地处理各种括号匹配情况。该算法可广泛应用于代码语法分析、表达式求值等领域。