题解 | #括号配对问题#

题目链接

括号配对问题

题目描述

给定一个包含多种字符的字符串 s，你需要判断这个字符串中的括号子序列是否是合法的。合法的括号序列定义如下：

空序列是合法的。
如果 A 是合法的，那么 (A) 和 [A] 也是合法的。
如果 A 和 B 都是合法的，那么 AB 也是合法的。

字符串中只考虑 (, ), [, ] 四种括号字符，其他所有字符都应被忽略。

输入格式 一个字符串 s。

输出格式 如果括号序列合法，输出 true；否则输出 false。

示例

输入: a[x(y)z]
输出: true (提取括号后为 [()])
输入: abcd(])[efg
输出: false (提取括号后为 (])[ )

解题思路

这是一个经典的括号匹配问题，使用栈（Stack）数据结构是解决此类问题的标准方法。栈的"后进先出"（LIFO）特性完美地契合了括号"最晚打开的必须最早闭合"的匹配规则。

算法步骤如下：

初始化一个空栈。这个栈将用来存放我们遇到的所有左括号。
遍历输入字符串中的每一个字符。
对于每一个字符，我们进行以下判断：
- 如果它是一个左括号 (( 或 [)，就将其压入（push）栈中。
- 如果它是一个右括号 () 或 ])，这时需要进行匹配检查： a. 首先，检查栈是否为空。如果栈为空，说明这个右括号没有对应的左括号来匹配，因此序列不合法，可以直接返回 false。 b. 如果栈不为空，就弹出（pop）栈顶的元素。 c. 检查弹出的左括号是否与当前的右括号相匹配： - 如果当前是 )，但弹出的不是 (，则不匹配。 - 如果当前是 ]，但弹出的不是 [，则不匹配。 - 一旦发现不匹配，序列不合法，立即返回 false。
- 如果字符不是括号，则直接忽略它，继续遍历。
最终检查：当遍历完整个字符串后，检查栈的状态。
- 如果栈是空的，说明所有遇到的左括号都找到了与之匹配的右括号，整个序列是合法的。返回 true。
- 如果栈不为空，说明有多余的左括号没有被匹配，整个序列不合法。返回 false。

这个算法能够高效且准确地验证所有类型的括号序列。

代码

c++
java
python

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int main() {
    string s;
    cin >> s;
    
    stack<char> brackets;
    bool is_valid = true;
    
    for (char c : s) {
        if (c == '(' || c == '[') {
            brackets.push(c);
        } else if (c == ')') {
            if (brackets.empty() || brackets.top() != '(') {
                is_valid = false;
                break;
            }
            brackets.pop();
        } else if (c == ']') {
            if (brackets.empty() || brackets.top() != '[') {
                is_valid = false;
                break;
            }
            brackets.pop();
        }
    }
    
    if (!brackets.empty()) {
        is_valid = false;
    }
    
    if (is_valid) {
        cout << "true" << endl;
    } else {
        cout << "false" << endl;
    }
    
    return 0;
}

import java.util.Scanner;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        
        Deque<Character> stack = new ArrayDeque<>();
        boolean isValid = true;
        
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[') {
                stack.push(c);
            } else if (c == ')') {
                if (stack.isEmpty() || stack.pop() != '(') {
                    isValid = false;
                    break;
                }
            } else if (c == ']') {
                if (stack.isEmpty() || stack.pop() != '[') {
                    isValid = false;
                    break;
                }
            }
        }
        
        if (!stack.isEmpty()) {
            isValid = false;
        }
        
        System.out.println(isValid);
    }
}

def main():
    s = input()
    stack = []
    is_valid = True
    
    for char in s:
        if char == '(' or char == '[':
            stack.append(char)
        elif char == ')':
            if not stack or stack.pop() != '(':
                is_valid = False
                break
        elif char == ']':
            if not stack or stack.pop() != '[':
                is_valid = False
                break
    
    if stack: # 如果循环结束后栈不为空
        is_valid = False
        
    print(str(is_valid).lower())

if __name__ == "__main__":
    main()

算法及复杂度

算法: 基于栈的序列扫描。
时间复杂度: $\mathcal{O}(L)$ ，其中 $L$ 是输入字符串 s 的长度。我们只需要对字符串进行一次完整的遍历。
空间复杂度: $\mathcal{O}(P)$ ，其中 $P$ 是字符串中左括号的数量。在最坏的情况下（例如，字符串全是左括号），空间复杂度为 $\mathcal{O}(L)$ 。