平衡的判定

题目描述

给定一个由括号组成的字符序列，该序列只会出现六种字符，分别是 ( 、)、[ 、]、{、} 。

请判断输入的括号序列是否是平衡的。

平衡的定义如下：

• 空序列是平衡的；
• 如果某个括号序列 s 是平衡的，那么 [s]、 (s)、{s} 也是平衡的；
• 如果某两个括号序列 s 与 t 是平衡的，那么 s 拼接 t 后也是平衡的。

不能由上述规则得到的括号序列都是不平衡的。

输入格式

一个字符序列：表示输入的括号序列。

输出格式

如果是平衡的，输出 B，否则，输出 U。

数据范围

设 |S| 表示输入序列的长度，

• 对于 50% 的数据，$1\le |S|\le 1000$，保证输入的括号序列只含有 ( 及 )；
• 对于 100% 的数据，$1\le n\le 1000000$；

样例

样例1

输入：

({})[]

输出：

B

样例2

输入：

{)(}

输出：

U

我的题解

这道题是经典的括号匹配问题，我使用栈这个数据结构来辅助判断。
遍历整个字符串，遇到左括号 (、[、{ 就压入栈中；遇到右括号时，先检查栈是否为空，若为空说明没有左括号可以匹配，直接判定为不平衡；否则检查栈顶的左括号是否与当前右括号匹配，若匹配则弹出栈顶，若不匹配也判定为不平衡。
遍历结束后，如果栈为空，说明所有括号都正确匹配，输出 B；若栈非空，则说明有多余的左括号，输出 U。
时间复杂度 O(n)，空间复杂度 O(n)，n 为序列长度，本题 n 最大 1000000，栈空间足够。

带注释的源代码

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

// 我定义一个字符栈，用来存储等待匹配的左括号
stack <char> t;
string s;

int main() {
    cin >> s;  // 读入括号序列

    // 遍历整个字符串
    for (int i = 0; i < s.size(); i++) {
        // 如果当前字符是左括号，则将其压入栈中
        if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
            t.push(s[i]);
        }
        // 否则当前字符是右括号，先检查栈是否为空
        else if (t.empty()) {
            // 栈空说明没有左括号与当前右括号匹配，不平衡，直接输出U并结束
            cout << "U";
            return 0;
        }
        // 栈非空，则检查栈顶左括号是否与当前右括号匹配
        else {
            // 若匹配失败（三种不匹配的情况），则不平衡，输出U并结束
            if (s[i] == ')' && t.top() != '(' ||
                s[i] == ']' && t.top() != '[' ||
                s[i] == '}' && t.top() != '{') {
                cout << "U";
                return 0;
            } else {
                // 匹配成功，弹出栈顶的左括号
                t.pop();
            }
        }
    }

    // 遍历结束后，如果栈为空，说明全部匹配，输出B
    if (t.empty()) {
        cout << "B";
    } else {
        // 栈非空，说明有未匹配的左括号，输出U
        cout << "U";
    }
    return 0;
}