P1739 题解

ikunTLE · 2025-12-15 22:19:31 · 题解

思路

括号匹配用栈进行实现。

遍历字符串，每遍历到 ( 就将它放入栈中。遍历到 ) 就看栈内是否有 ( 即可，如果有，那么这对括号匹配；否则无法匹配，输出 NO。

最后注意判断是否所有 ( 都匹配了（即栈是否为空）。

但对于这道题来说，由于无需对括号进行操作，那么可以用一个计数器代替栈，计数器统计栈内有多少 (。

AC CODE

#include<bits/stdc++.h>
using namespace std;
const int N=300;
char s[N];
int main(){
    scanf("%s",s+1);
    int n=strlen(s+1),cnt=0;
    for(int i=1;i<=n;++i)
        if(s[i]=='(')
            ++cnt;
        else if(s[i]==')'){
            if(!cnt)
                return printf("NO\n"),0;
            --cnt;
        }
    printf(cnt?"NO\n":"YES\n");
    return 0;
}