有效的括号

题意

给定仅含括号的字符串，判断是否有效：每个右括号与最近未匹配的左括号类型相同且顺序正确。

思路

左括号入栈，遇到右括号时栈顶必须与之匹配：) 对应 (，] 对应 [，} 对应 {。不匹配或栈空则非法。扫描结束后栈必须为空（所有左括号都已闭合）。

关键：栈顶始终是"最近一个未匹配的左括号"，右括号只能匹配栈顶——这对应括号的就近闭合规则。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for (char ch : s) {
            if (ch == '(' || ch == '{' || ch == '[')
                st.push(ch);
            else {
                if (st.empty())
                    return false;
                if (ch == ')' && st.top() != '(')
                    return false;
                if (ch == '}' && st.top() != '{')
                    return false;
                if (ch == ']' && st.top() != '[')
                    return false;
                st.pop();
            }
        }
        return st.empty();
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    cout << Solution().isValid(s) << '\n';
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19#!/usr/bin/env python3
class Solution:
    def isValid(self, s: str) -> bool:
        st = []
        mp = {")": "(", "}": "{", "]": "["}
        for ch in s:
            if ch in mp.values():
                st.append(ch)
            elif not st or st.pop() != mp[ch]:
                return False
        return not st


def main():
    print(Solution().isValid(input().strip()))


if __name__ == "__main__":
    main()

复杂度

时间复杂度： $O(n)$ ，每个字符一次入栈或弹出。
空间复杂度： $O(n)$ ，栈最深存所有左括号。

总结

括号匹配是栈的基础应用：左括号"等待匹配"，右括号"检查并消解栈顶"。栈的 LIFO 性质天然保证就近闭合规则。

目录

题意

思路

代码

复杂度

总结