表达式括号匹配

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

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

OJ: luogu

题目 ID: P1739

难度:入门

标签:栈字符串模拟

创建: 2026-07-06 20:42

更新: 2026-10-07 10:45

后置题目
roj 3030火车进栈B 的第一步把火车进出站操作序列翻译成合法括号结构，直接复用 A 教的「扫描中 balance 不能为负」这一前缀非负判定，再叠加 A 未教的 DFS 按「先出栈后进栈」字典序枚举与收满 20 个整树剪枝。roj 1358中缀表达式值(expr)B 的 tokenize 合法性子过程直接沿用 A 教的「单计数器记录未匹配左括号、过程中不得为负、末尾归零」这一配对判定（代码里的 depth：expect_operand 位置遇 ) 而 depth==0 判 NO，扫描结束 depth 非 0 判 NO），只在此之上叠加记号类别状态机、调度场转后缀与操作数栈求值。luogu P1241括号序列B 复用 A 教的「栈维护未匹配左括号、右括号只能与之前未匹配左括号配对」这一步，再叠加本题特有规则（类型不符时两者都保留为未匹配）与扫描后按位补全括号输出。luogu P3056[USACO12NOV] Clumsy Cows SB 原样复用 A 的 balance 计数与 balance<0 判定步骤，在其上叠加最少翻转的贪心决策

目录

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

题意

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

如果匹配，输出 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;
}

STL 写法

这道题正是 cppbook 里「用栈做配对」的标准例子：用 stack<char> 保存还没配对上的左括号，扫到 ( 就 push，扫到 ) 时先判断栈是否为空，非空就 pop 掉最近的那个左括号，扫到 @ 结束，最后栈为空才输出 YES。它和上面计数器写法的判断条件完全一样，区别只在于栈把「最近的左括号」真的存了下来，所以换成多种括号时只要多一张配对表，框架不用重写；代价是栈最坏要占 O(n)O(n) 的空间，而计数器只用一个变量。

对应的 cppbook 章节：stack：最后放入，最先取出

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 00:52
 * update_at: 2026-10-07 01:02
 */
// 这是 STL 写法：用 stack<char> 保存还没配对上的左括号，
// 扫到 ')' 就弹出栈顶配对，扫到 '@' 结束，最后栈空才输出 YES。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

string expr;    // 读入的整个表达式，以 '@' 结尾
stack<char> st; // 还没有配对上的左括号：后进先出，弹出的总是最近的那个左括号

// 扫描表达式，判断其中的圆括号是否匹配。
bool brackets_match() {
    ll len = expr.size();
    for (ll i = 0; i < len; i++) {
        if (expr[i] == '@') {
            break; // '@' 是结束符，它后面的字符都不属于表达式
        }
        if (expr[i] == '(') {
            st.push('('); // 左括号压栈，等后面的右括号来配对
        } else if (expr[i] == ')') {
            if (st.empty()) {
                return false; // 栈空说明右括号多了，没有左括号可以配
            }
            st.pop(); // 和最近的那个左括号配掉
        }
    }
    return st.empty(); // 栈空说明没有多余的左括号
}

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

    cin >> expr;

    if (brackets_match()) {
        cout << "YES" << '\n';
    } else {
        cout << "NO" << '\n';
    }

    return 0;
}

复杂度

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

总结

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