表达式括号匹配

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

扫描表达式时维护左括号数量，遇到右括号必须能匹配，结束时数量归零才合法。

OJ: luogu

题目 ID: P1739

难度:入门

标签:栈字符串模拟

日期: 2026-07-06 20:42

目录

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

题意

给出一个以 @ 结尾的表达式，只需要检查其中的圆括号 ( 和 ) 是否匹配。

如果匹配，输出 YES，否则输出 NO。

思路

先看一个用栈的朴素写法：

cpp
// brute.cpp：小数据朴素解，用栈检查每个右括号是否有左括号匹配。
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;

    vector<char> st;
    bool ok = true;
    for (int i = 0; i < (int)s.size() && s[i] != '@'; i++) {
        if (s[i] == '(') {
            st.push_back(s[i]);
        } else if (s[i] == ')') {
            if (st.empty()) {
                ok = false;
            } else {
                st.pop_back();
            }
        }
    }
    if (!st.empty()) {
        ok = false;
    }

    cout << (ok ? "YES" : "NO") << '\n';
    return 0;
}

括号匹配只关心两个条件：

  1. 扫描过程中，任意一个右括号 ) 前面都必须有还没匹配的左括号；
  2. 扫描结束时，不能剩下未匹配的左括号。

因为这里只有一种括号，所以不一定真的需要保存每个左括号，只维护一个计数器 balance 即可：

  • 遇到 (，balance++；
  • 遇到 )，balance--；
  • 如果 balance < 0，说明右括号多了；
  • 最后如果 balance != 0，说明左括号多了。

遇到 @ 后表达式结束，后面不再处理。

代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;

    int balance = 0;
    bool ok = true;
    for (int i = 0; i < (int)s.size() && s[i] != '@'; i++) {
        if (s[i] == '(') {
            balance++;
        } else if (s[i] == ')') {
            balance--;
            if (balance < 0) {
                ok = false;
            }
        }
    }

    if (balance != 0) {
        ok = false;
    }
    cout << (ok ? "YES" : "NO") << '\n';
    return 0;
}

复杂度

  • 时间复杂度：O(∣s∣)O(|s|)
  • 空间复杂度：O(1)O(1)

总结

只有一种括号时，栈可以简化成计数器。过程中不能为负，最后必须归零。