合法的括号信奥-数据结构-栈与队列

Question

题目描述
假设表达式中允许包含三种括号：圆括号、方括号和大括号，其嵌套的顺序随意，如{()}或[([]{}[])]等为正确的匹配，[({]})或(均为错误的匹配。
  现在的问题是，要求检验一个给定表达式中的括弧是否正确匹配？
输入一个只包含圆括号、方括号和大括号的字符串，判断字符串中的括号是否匹配，匹配就输出 “OK” ，不匹配就输出“Wrong”。
输入一个字符串：{()}，输出：OK
字符串中的空格不对结果造成影响。
注意要求输入英文括号。
输入
第一行输入括号个数N，N<255
第二行为包含N个括号的字符串（字符个数小于255）
输出
匹配就输出 “OK” ，不匹配就输出“Wrong”。
样例输入 复制
6
{[( )]}
样例输出 复制
OK
各位请问这道怎么做？

Answer 1

引自免费微信小程序：皆我百晓生

为了解决这个问题，我们可以使用栈（stack）数据结构来检查括号的正确匹配。下面是一个C++程序实现：

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

// 定义一个枚举类型来表示不同类型的括号
enum BracketType {
    ROUND_BRACKET = 0, // 圆括号 '(' 和 ')'
    SQUARE_BRACKET = 1, // 方括号 '[' 和 ']'
    CURLY_BRACKET = 2   // 大括号 '{' 和 '}'
};

// 判断当前括号与栈顶括号是否匹配
bool isMatchingBracket(char current, BracketType& top) {
    switch (current) {
        case ')':
            return top == ROUND_BRACKET;
        case ']':
            return top == SQUARE_BRACKET;
        case '}':
            return top == CURLY_BRACKET;
        default:
            return false; // 输入不合法
    }
}

// 检查括号字符串是否匹配
bool isValidBracketSequence(const string& s) {
    stack<BracketType> bracketStack;

    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            bracketStack.push(
                c == '(' ? ROUND_BRACKET :
                c == '[' ? SQUARE_BRACKET :
                CURLY_BRACKET
            );
        } else if (c == ')' || c == ']' || c == '}') {
            if (bracketStack.empty() || !isMatchingBracket(c, bracketStack.top())) {
                return false;
            } else {
                bracketStack.pop();
            }
        } else {
            // 非括号字符，忽略或处理错误（根据题目要求）
        }
    }

    return bracketStack.empty(); // 如果所有括号都已正确关闭，则返回true
}

int main() {
    int N;
    cin >> N;
    cin.ignore(); // 忽略换行符

    string input;
    getline(cin, input);

    if (isValidBracketSequence(input)) {
        cout << "OK" << endl;
    } else {
        cout << "Wrong" << endl;
    }

    return 0;
}

这段代码首先定义了一个枚举类型 BracketType 来区分三种括号。接着，我们创建了一个栈来存储未闭合的左括号，并在遍历输入字符串时，遇到左括号就将其类型压入栈中，遇到右括号则检查其与栈顶元素是否匹配，若匹配则弹出栈顶元素，否则返回错误。

最后，在遍历完成后，如果栈为空，则说明所有的括号都已经正确匹配；反之则存在未匹配的括号。