判断括号是否有效(c++描述)

开门见山，假设我们有一大串的由'{', '}', '[', ']', '(', ')' 这些括号构成比如像这样的"{[}][()"符号串，我们肉眼当然能看出它是非法的，那么如何使用代码来判断是否合法呢？

其实我们可以借助栈来判断这些符号串是否非法 ：

1.首先我们我需要建立符号的一对一映射,如下所示：

1  map<char, char> mp = {{')', '('}, {'}', '{'}, {']', '['}}; // 映射括号

2.我们对字符串进行遍历

1.如果能通过映射的键找到当前字符str[i]，我们就从栈顶弹出一个元素并获取该元素。当然，如果是栈为空的清空的话，我们就为这个字符随便赋个值，比如说赋值为 '@'，我们假记该变量为top_element。接下来我们看看是否能从当前字符str[i]映射所对应的值与top_element是否相同，若不同，则可以判断该符号串为非法的。

2.若果找不到该字符str[i]映射的键，则先将其加入栈中。

3. 循环结束 ，若栈为空则表示当前字符串合法，若不为空，则表示当前字符串非法

4. 可能光用语言描述不能只管表达，下面我们来看图示，假设我们输入了"()"字符串，其具体过程如下:

5. 好了看完图，接下来我们C++的代码来描述一下该过程:

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

class Solution
{
public:
    bool isValid(string s)
    {
        if (s == "") // 如果时空字符串也合法
            return true;
        if (s.size() == 1) // 只有一个字符肯定非法
            return false;
        stack<char> st;
        map<char, char> mp = {{')', '('}, {'}', '{'}, {']', '['}}; // 映射括号
        for (int i = 0; i < s.size(); i++)
        {
            if (mp.find(s[i]) != mp.end()) // 查找mp是否映射了该符号
            {
                char top_ele = (st.size() == 0) ? '#' : st.top(); // 获取栈顶元素，若为空则随便设置一个字符
                if (top_ele != '#')                               // 栈不为空则弹出元素
                    st.pop();
                if (top_ele != mp.find(s[i])->second) // 如果这个元素被弹出的元素和mp对应映射的值不一样，则直接返回false
                    return false;
            }
            else
            {
                st.push(s[i]); //压入栈中
            }
        }
        return st.size() == 0; // 如果栈为空则表示合法
    }
};

6. 注意代码中map是直接用list初始化的，所以这段代码必须在c++11下上的版本中才可以运行。

好了以上就是这次分享的全部内容了，如有错误还望斧正，我们下次见。

原文链接: https://www.cnblogs.com/maoqifansBlog/p/12498130.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍