洛谷-P1739 表达式括号匹配 题解

题目链接：https://www.luogu.com.cn/problem/P1739

题目解析

• 输入是一个由小写字母、运算符（+ - * /）、左右括号 () 和结束符 @ 组成的字符串。
• 只需关注 圆括号的匹配性，其他字符（包括字母、运算符、@）均可忽略。
• 匹配规则：每个 ) 必须有其前面未匹配的 ( 与之对应；最终不能有多余的 ( 或 )。

示例：

• (a+b) → YES
• ((a+b) → NO（多一个左括号）
• a+b) → NO（右括号无匹配）

核心思想

• 遍历字符串中的每个字符：遇到 (：入栈；遇到 )：若栈为空 → 多余的右括号，直接输出 NO 并退出；否则弹出一个 (（表示匹配成功）；
• 遍历结束后，若栈为空 → 所有括号都匹配，输出 YES；否则输出 NO。

注意：题目中 @ 仅为结束标志，不影响逻辑，可当作普通字符处理（代码中无需特殊判断）。

代码详解（C++）

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int main() {
    string str;
    cin >> str;               // 读入整个表达式（含 @）
    stack<char> S;

    for (char ch : str) {
        if (ch == '(') {
            S.push(ch);       // 左括号入栈
        } else if (ch == ')') {
            if (S.empty()) {  // 右括号出现时栈空 → 不匹配
                cout << "NO";
                return 0;     // 立即退出
            }
            S.pop();          // 匹配成功，弹出对应左括号
        }
        // 其他字符（字母、运算符、@）全部忽略
    }

    // 最后检查是否还有未匹配的左括号
    if (S.empty())
        cout << "YES";
    else
        cout << "NO";

    return 0;
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串长度（< 255），每个字符访问一次。
• 空间复杂度：O(k)，k为左括号数量（< 20），栈最大深度很小。