P1739 表达式括号匹配——题解

思路

只需要关心左右圆括号，其他字符全部跳过。

设 cnt 表示当前还没有被匹配的左括号数量：

• 遇到 (，令 cnt++；
• 遇到 )：若 cnt==0，说明右括号出现在可匹配的左括号之前，立即判定不合法；否则令 cnt--；
• 遇到 @ 时停止。

最后只有 cnt==0 才说明没有多余的左括号。

复杂度

时间复杂度 $O(|s|)$，额外空间复杂度 $O(1)$。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    int cnt = 0;
    for (char c : s) {
        if (c == '@') break;
        if (c == '(') cnt++;
        else if (c == ')') {
            if (cnt == 0) {
                cout << "NO\n";
                return 0;
            }
            cnt--;
        }
    }
    cout << (cnt == 0 ? "YES\n" : "NO\n");
    return 0;
}

#include <bits/stdc++.h> using namespace std; int main(){ string s; cin>>s; int cnt=0; for(char c:s){ if(c=='@') break; if(c=='(') cnt++; else if(c==')'){ if(cnt0){ cout<<"NO\n"; return 0; } cnt--; } } cout<<(cnt0?"YES\n":"NO\n"); return 0; }