有效的括号

GitHub跳转原题关系图返回列表

栈匹配：左括号入栈，右括号必须与栈顶严格配对，最终栈空则合法。

OJ: leetcodecn

题目 ID: valid-parentheses

难度:入门

标签:栈字符串

创建: 2026-07-29 12:02

更新: 2026-07-29 15:20

后置题目
roj 3030火车进栈B 的第一步直接沿用 A 教的括号合法性判定（栈空不能出栈），把火车进出站序列归约为合法括号序列结构，再在其上叠加字典序 DFS 枚举与剪枝。roj 1356计算(calc)A 教的两类括号分别入栈/消解至配对左括号这一步，被 B 的调度场括号屏障规则直接复用，B 只是再叠加优先级弹栈与后缀求值luogu P1241括号序列B 原样复用 A 的栈顶即最近未匹配左括号且右括号只与栈顶匹配这一步，再叠加未匹配括号原位补全的输出规则luogu P4387【深基15.习9】验证栈序列B 复用 A 的「压入/按栈顶条件弹出/以栈空收尾」这一栈判定流程，只是把括号配对规则换成 pushed→poped 的出栈序列匹配

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

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

思路

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

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

代码

cpp
#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
#!/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)，每个字符一次入栈或弹出。
  • 空间复杂度：O(n)O(n)，栈最深存所有左括号。

总结

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