题面描述

给定一个仅由 (, ), {, }, [, ] 六种括号组成的字符串，判断该字符串是否为有效字符串。有效字符串的条件是：

1. 每种类型的左右括号数量相等。
2. 括号的闭合顺序正确（即先左后右）。

如果字符串有效，输出括号的最大嵌套深度；如果字符串无效，输出 0。

思路

1. 栈的使用：我们可以使用栈来检查括号的有效性。遍历字符串时，遇到左括号就将其压入栈中，遇到右括号时检查栈顶的左括号是否与之匹配。如果匹配，则弹出栈顶元素；如果不匹配，则字符串无效。

2. 深度计算：在遍历过程中，我们可以记录栈的最大深度，即为括号的最大嵌套深度。

3. 无效情况：

   • 如果遍历结束后栈不为空，说明有未匹配的左括号，字符串无效。
   • 如果遇到右括号时栈为空，说明有未匹配的右括号，字符串无效。

cpp

#include <iostream>
#include <stack>
#include <unordered_map>
using namespace std;

int maxDepth(string s) {
    stack<char> st;
    int max_depth = 0;
    unordered_map<char, char> mapping = {{')', '('}, {']', '['}, {'}', '{'}};
    
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
            max_depth = max(max_depth, (int)st.size());
        } else if (c == ')' || c == ']' || c == '}') {
            if (st.empty() || st.top() != mapping[c]) {
                return 0;
            }
            st.pop();
        }
    }
    
    return st.empty() ? max_depth : 0;
}

int main() {
    string s;
    cin >> s;
    cout << maxDepth(s) << endl;
    return 0;
}

python

def max_depth(s: str) -> int:
    stack = []
    max_depth = 0
    mapping = {')': '(', ']': '[', '}': '{'}
    
    for char in s:
        if char in mapping.values():
            stack.append(char)
            max_depth = max(max_depth, len(stack))
        elif char in mapping.keys():
            if not stack or stack[-1] != mapping[char]:
                return 0
            stack.pop()
    
    return max_depth if not stack else 0

# 测试
s = input().strip()
print(max_depth(s))

java

import java.util.*;

public class Main {
    public static int maxDepth(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        int maxDepth = 0;
        Map<Character, Character> mapping = new HashMap<>();
        mapping.put(')', '(');
        mapping.put(']', '[');
        mapping.put('}', '{');
        
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
                maxDepth = Math.max(maxDepth, stack.size());
            } else if (c == ')' || c == ']' || c == '}') {
                if (stack.isEmpty() || stack.peek() != mapping.get(c)) {
                    return 0;
                }
                stack.pop();
            }
        }
        
        return stack.isEmpty() ? maxDepth : 0;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        System.out.println(maxDepth(s));
    }
}

题目内容

现有一字符串仅由 ‘(‘，’)’，'{‘，’}’，'[‘，’]’六种括号组成。

若字符串满足以下条件之一，则为无效字符串：

①任一类型的左右括号数量不相等；

②存在未按正确顺序（先左后右）闭合的括号。

输出括号的最大嵌套深度，若字符串无效则输出0。

0≤字符串长度≤100000

输入描述

一个只包括 ‘(‘，’)’，'{‘，’}’，'[‘，’]’的字符串

输出描述

一个整数，最大的括号深度

样例1

输入

[]

输出

1

说明

有效字符串，最大嵌套深度为1

样例2

输入

([]{()})

输出

3

说明

有效字符串，最大嵌套深度为3

样例3

输入

(]

输出

0

说明

无效字符串，有两种类型的左右括号数量不相等

样例4

输入

([)]

输出

0

说明

无效字符串，存在未按正确顺序闭合的括号

样例5

输入

)(

输出

0

说明

无效字符串，存在未按正确顺序闭合的括号。