P76057 括号是否匹配 — 题解

专题： STL
适用题目： 新生 OJ 本地题包中的 P76057，不要直接用于外站同名题。

解题思路

遇到左括号就入栈，遇到右括号必须先确认栈非空再弹出；最后栈为空才合法。

复杂度

时间 $O(n)$，空间 $O(n)$。

易错点

任意前缀都不能出现右括号多于左括号的情况。

C++17 参考程序

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define nl '\n'

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin>>s;
    stack<char>st;
    bool ok=true;
    for(char c:s){
        if(c=='(')st.push('(');
        if(c==')'){
            if(st.empty()){
                ok=false;
                break;
            }
            st.pop();
        }
    }
    cout<<(ok&&st.empty()?"YES":"NO")<<nl;
    return 0;
}

为什么只提供 C++： 本题专题要求使用 STL 容器或算法，C 语言没有 STL；C 可以用手写数据结构解决，但不属于本专题的教学目标。

题解建议设置为训练结束后开放。普通判题无法验证是否实际使用指定函数或 STL。