【栈问题】括号匹配 题解
2023-04-06
242
本文为本站原创,未经允许请勿随意转载,谢谢!

题目:

描述:

假设表达式中只包含三种括号:圆括号、方括号和花括号,它们可相互嵌套,如([{}])或({[][()]})等均为正确的格式,而{[]})}或{[()]或([]}均为不正确的格式.

输入一串括号

如果输入的右括号多余,输出:Extra right brackets

如果输入的左括号多余, 输出:Extra left brackets

如果输入的括号不匹配,输出:Brackets not match

如果输入的括号匹配,输出:Brackets match

输入格式:

一行只含 ( ) [ ] { } 这6种字符,不含其它任何字符的字符串。字符串不超过1000个字符。

输出格式:

如果输入的右括号多余,输出:

Extra right brackets
    
 

如果输入的左括号多余, 输出:

Extra left brackets
    
 

如果输入的括号不匹配,输出:

Brackets not match
    
 

如果输入的括号匹配,输出:

Brackets match
    
 

输入样例:

{{{{)))
 

输出样例:

Brackets not match

思路:

本来这个题打算用s.find()、count()函数,来先找到左括号,再往后查数量和顺序是否对应。但实际上括号并不一定是从中间对称的(例如 ({[][()]}) ),使用上述办法不仅十分复杂,还不能考虑到所有情况。

其实这个题的最佳解法是用栈。因为栈的特性能够很好地用于这种套娃问题的处理。

废话不多说,说明都写在下面代码的注释里了。


解法:

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

stack<int> st;
map<char, char> mp;

int main()
{
    // 用map创建键值对,建立左右括号的对应关系
    mp['('] = ')';
    mp['{'] = '}';
    mp['['] = ']';

    string s;
    cin >> s;
    for (size_t i = 0; i < s.length(); i++) {
        // 从前往后依次读入字符
        int c = s[i];
        if (c == '(' || c == '[' || c == '{') {
            // 如果读取的是左括号,就先入栈保存(放到了栈顶)
            st.push(c);
        } else if (c == ')' || c == ']' || c == '}') {
            // 如果读取的是右括号
            if (st.empty()) {
                // 如果栈为空,就说明没有左括号与之匹配,则该右括号是多余的,程序结束例如 {[]})
                cout << "Extra right brackets" << endl;
                return 0;
            } else {
                if (c == mp[st.top()]) {
                    // 如果栈顶的左括号与当前右括号匹配,就弹出栈顶的左括号,意味着当前这对括号合法不用在管了,程序进行下一轮循环
                    st.pop();
                } else {
                    // 如果栈顶的左括号与当前右括号不匹配,就输出不匹配,程序结束例如 [{)]
                    cout << "Brackets not match" << endl;
                    return 0;
                }
            }
        }
    }
    // 当所有字符处理完之后
    if (!st.empty()) {
        // 如果此时栈里还有元素,也就说明左括号有多余的,例如 {[()]
        cout << "Extra left brackets" << endl;
    } else {
        // 如果此时栈空了,就说明万事大吉,括号是匹配的
        cout << "Brackets match" << endl;
    }

    return 0;
}
C++C语言算法题解