典型的括号匹配问题c++

2023-07-25 101

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 典型的括号匹配问题c++

问题描述

C++栈问题，括号匹配问题求解，无法AC，求指教！

【题目描述】

设有一字符串中有三种括号：()，[]，{}；忽略不看其他字符，判断这些括号的匹配情况是否成立。例如：“(([()])){}”是匹配的，而“([)]”则是不匹配的。

【输入格式】

只有一行且只有一个数据：一串以“@”为结束符的字符串。字符串长度不会超过20000

【输出格式】

只有一行且只有一个数据：如果是匹配的，则输出：“OK!”，否则输出第一个不相匹配的括号位置（输入数据保证相同类型的左右括号个数相等）。

【输入样例】

82u(idkj[kdk]js{ksf(k[sk)k])o}i@

【输出样例】

25

代码分析

首先读入以@结尾的字符串：

string s;
getline(cin, s, '@');

接着定义一个pair类型的栈，用来存储左括号及其位置：

stack<pair<char, int>> st

然后遍历字符串中的每个字符，在遍历过程中，如果是左括号，则将其加入栈中，如果是右括号，则弹出栈顶元素进行比较，如果不匹配则输出位置，匹配则弹出栈顶元素：

for (int i = 0; i < s.size(); i++) {
    if (s[i] == '(' || s[i] == '[' || s[i] == '{') { // 左括号入栈
        stk.push({s[i],i}); // 这里记录了左括号位置
    } else if (s[i] == ')' || s[i] == ']' || s[i] == '}') { // 右括号出栈比较
        if (stk.empty() || !isMatch(stk.top().first, s[i])) { // 不匹配
            cout << i << endl;
            return 0;
        } else { // 匹配，弹出左括号
            stk.pop();
        }
    }
}

isMatch函数判断两个括号是否匹配，这里使用了逻辑运算符的短路性质来判断：

bool isMatch(char left, char right) {
    return (left == '(' && right == ')') || (left == '[' && right == ']') || (left == '{' && right == '}');
}

最后，如果遍历完字符串之后，栈中还有元素，则说明不匹配，输出栈顶元素的位置，否则输出"OK!"表示匹配：

if (!stk.empty()) {
    cout << stk.top().second << endl;
} else {
    cout << "OK!" << endl;
}

代码比较简洁明了，这样就能够实现括号匹配的功能。

完整代码

#include <iostream>
#include <stack>
using namespace std;
bool isMatch(char left, char right) {
    return (left == '(' && right == ')') || (left == '[' && right == ']') || (left == '{' && right == '}');
}
int main() {
    string s;
    getline(cin, s, '@'); // 读入以@结尾的字符串
    stack<pair<char, int>> stk; // 使用pair记录括号类型和位置
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(' || s[i] == '[' || s[i] == '{') { // 左括号入栈
            stk.push({s[i],i});
        } else if (s[i] == ')' || s[i] == ']' || s[i] == '}') { // 右括号出栈比较
            if (stk.empty() || !isMatch(stk.top().first, s[i])) { // 不匹配
                cout << i << endl;
                return 0;
            } else { // 匹配，弹出左括号
                stk.pop();
            }
        }
    }
    // 遍历完字符串后，栈中还有元素说明不匹配
    if (!stk.empty()) {
        cout << stk.top().second << endl;
    } else {
        cout << "OK!" << endl;
    }
    return 0;
}

典型的括号匹配问题c++

问题描述

代码分析

完整代码

热门文章

最新文章

相关课程

相关电子书