# 题目：2023Q1A-括号检查
# 分值：100
# 作者：闭着眼睛学数理化
# 算法：栈
# 代码看不懂的地方，请直接在群上提问

s = input()
# 初始化用于判断异常的变量isError，初始化为False表示没有异常
isError = False
# 初始化答案变量ans和记录当前深度的变量cur_depth
ans, cur_depth = 0, 0
# 构建三种括号的两两配对关系
pairs = [('(', ')'), ('{', '}'), ('[', ']')]

# 若字符串长度为奇数，必定无法配对，isError设置为True
if len(s) % 2 == 1:
    isError = True
else:
    # 使用列表list初始化一个空栈
    stack = list()
    # 一次遍历字符串s中的每一个字符ch
    for ch in s:
        # 若ch为某种左括号
        if ch == '(' or ch == '{' or ch == '[':
            # 则将ch加入栈顶，同时括号深度+1，更新最大括号深度
            stack.append(ch)
            cur_depth += 1
            ans = max(ans, cur_depth)
        # 若ch为某种右括号
        else:
            # 若此时栈为空
            if len(stack) == 0:
                # 该右括号无法与左括号配对，出现异常，isError设置为True，同时退出循环
                isError = True
                break
            # 若栈不为空，则弹出栈顶字符，同时括号深度-1
            ch_stack_top = stack.pop()
            cur_depth -= 1
            # 若栈顶左括号字符ch_stack_top和当前右括号字符ch不配对，
            # 出现异常，isError设置为True，同时退出循环
            if (ch_stack_top, ch) not in pairs:
                isError = True
                break
    # 经过一次遍历后，若仍存在元素，说明存在括号未配对，出现异常，isError设置为True
    if len(stack) > 0:
        isError = True

# 如果isError标志为True，说明前面某一步出现异常，输出0，否则输出最大深度ans
print(0 if isError else ans)

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        // 初始化用于判断异常的变量isError，初始化为False表示没有异常
        boolean isError = false;
        // 初始化答案变量ans和记录当前深度的变量cur_depth
        int ans = 0;
        int cur_depth = 0;
        // 构建三种括号的两两配对关系
        List<Character[]> pairs = new ArrayList<>();
        pairs.add(new Character[]{'(', ')'});
        pairs.add(new Character[]{'{', '}'});
        pairs.add(new Character[]{'[', ']'});

        // 若字符串长度为奇数，必定无法配对，isError设置为True
        if (s.length() % 2 == 1) {
            isError = true;
        } else {
            // 使用列表list初始化一个空栈
            List<Character> stack = new ArrayList<>();
            // 一次遍历字符串s中的每一个字符ch
            for (char ch : s.toCharArray()) {
                // 若ch为某种左括号
                if (ch == '(' || ch == '{' || ch == '[') {
                    // 则将ch加入栈顶，同时括号深度+1，更新最大括号深度
                    stack.add(ch);
                    cur_depth++;
                    ans = Math.max(ans, cur_depth);
                } else {
                    // 若此时栈为空
                    if (stack.isEmpty()) {
                        // 该右括号无法与左括号配对，出现异常，isError设置为True，同时退出循环
                        isError = true;
                        break;
                    }
                    // 若栈不为空，则弹出栈顶字符，同时括号深度-1
                    char ch_stack_top = stack.remove(stack.size() - 1);
                    cur_depth--;
                    // 若栈顶左括号字符ch_stack_top和当前右括号字符ch不配对，
                    // 出现异常，isError设置为True，同时退出循环
                    boolean isPair = false;
                    for (Character[] pair : pairs) {
                        if (pair[0] == ch_stack_top && pair[1] == ch) {
                            isPair = true;
                            break;
                        }
                    }
                    if (!isPair) {
                        isError = true;
                        break;
                    }
                }
            }
            // 经过一次遍历后，若仍存在元素，说明存在括号未配对，出现异常，isError设置为True
            if (!stack.isEmpty()) {
                isError = true;
            }
        }

        // 如果isError标志为True，说明前面某一步出现异常，输出0，否则输出最大深度ans
        System.out.println(isError ? 0 : ans);
    }
}

C++

#include <iostream>
#include <vector>
using namespace std;

int main() {
    string s;
    getline(cin, s);
    // 初始化用于判断异常的变量isError，初始化为False表示没有异常
    bool isError = false;
    // 初始化答案变量ans和记录当前深度的变量cur_depth
    int ans = 0;
    int cur_depth = 0;
    // 构建三种括号的两两配对关系
    vector<pair<char, char>> pairs = {{'(', ')'}, {'{', '}'}, {'[', ']'}};

    // 若字符串长度为奇数，必定无法配对，isError设置为True
    if (s.length() % 2 == 1) {
        isError = true;
    } else {
        // 使用列表vector初始化一个空栈
        vector<char> stack;
        // 一次遍历字符串s中的每一个字符ch
        for (char ch : s) {
            // 若ch为某种左括号
            if (ch == '(' || ch == '{' || ch == '[') {
                // 则将ch加入栈顶，同时括号深度+1，更新最大括号深度
                stack.push_back(ch);
                cur_depth++;
                ans = max(ans, cur_depth);
            } else {
                // 若此时栈为空
                if (stack.empty()) {
                    // 该右括号无法与左括号配对，出现异常，isError设置为True，同时退出循环
                    isError = true;
                    break;
                }
                // 若栈不为空，则弹出栈顶字符，同时括号深度-1
                char ch_stack_top = stack.back();
                stack.pop_back();
                cur_depth--;
                // 若栈顶左括号字符ch_stack_top和当前右括号字符ch不配对，
                // 出现异常，isError设置为True，同时退出循环
                bool isPair = false;
                for (auto pair : pairs) {
                    if (pair.first == ch_stack_top && pair.second == ch) {
                        isPair = true;
                        break;
                    }
                }
                if (!isPair) {
                    isError = true;
                    break;
                }
            }
        }
        // 经过一次遍历后，若仍存在元素，说明存在括号未配对，出现异常，isError设置为True
        if (!stack.empty()) {
            isError = true;
        }
    }

    // 如果isError标志为True，说明前面某一步出现异常，输出0，否则输出最大深度ans
    cout << (isError ? 0 : ans) << endl;
    return 0;
}

时空复杂度

时间复杂度：O(N)。仅需一次遍历数组。

空间复杂度：O(N)。栈所占用的额外空间。