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

全栈若城

发布于 2024-02-29 18:37:24

4800

问题描述

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>> stk;

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

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;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-02-29，如有侵权请联系 cloudcommunity@tencent.com 删除

字符串