【程序设计训练】合法的括号串

左手的ㄟ右手 2022-11-26 10:56 356阅读 0赞

## 【问题描述】 ##

一个合法的括号串，是指只包含括号的串，如果满足如下条件：

（1）<> () \[\] \{\} 这四对括号是合法的；

（2）如果r是合法括号串，则 ® \[r\] \{r\}也是；

（3）如果r，s是合法括号串，则rs也是；

所以<<>> , \[<>\{\}(())\],\[(\{<>\})\]是合法的括号串，而)(,\[( \])就不是。

## 【输入形式】 ##

输入第一行正整数t (10 ≤ n ≤ 100)，表示有多少组测试数据。

后面有t行，每行一个只包含8种括号符号的括号串。

40%的括号串的长度L 2 ≤ L≤ 20；

30%的括号串的长度L 2 ≤ L≤ 200；

20%的括号串的长度L 2 ≤ L≤ 2000；

10%的括号串的长度L 2 ≤ L≤ 20000；

## 【输出形式】 ##

对于每组测试数据，如果括号串是合法的，输出“Yes”（输出没有引号）占一行，否则，输出“No”（输出没有引号）占一行。

## 【样例输入】 ##

6
    <<>> 
    )(
    [<>{
        }(())]
    [({
        <>})]
    [(])
    <([{

## 【样例输出】 ##

Yes
    No
    Yes
    Yes
    No
    No

## 【提交代码】 ##

仅供参考，有不足之处欢迎指出。

//34.合法的括号串
    #include <iostream>
    #include <stack>
    #include <string>
    using namespace std;
    
    int main()
    {
        
        int n, len;
        char chr;
        string str;
        cin >> n;
        for (int i = 0; i < n; i++)
        {
        
            stack<char> _left, _right;//左括号、右括号
            cin >> str;
            len = str.length();
            for (int j = 0; j < len; j++)
            {
        
                chr = str[j];
                if (chr == '(' || chr == '[' || chr == '{' || chr == '<')
                {
        
                    _left.push(chr);//是左括号则压入_left，表示暂时没有右括号与之对应
                }
                else if (chr == ')')//遇到右括号
                {
        
                    if (!_left.empty() && _left.top() == '(')//如果_left的顶部与其对应
                    {
        
                        _left.pop();//删去对应左括号
                    }
                    else
                    {
        
                        _right.push(chr);//否则将该右括号压入_right，表示没有左括号与之对应
                    }
                }
                else if (chr == ']')
                {
        
                    if (!_left.empty() && _left.top() == '[')
                    {
        
                        _left.pop();
                    }
                    else
                    {
        
                        _right.push(chr);
                    }
                }
                else if (chr == '}')
                {
        
                    if (!_left.empty() && _left.top() == '{')
                    {
        
                        _left.pop();
                    }
                    else
                    {
        
                        _right.push(chr);
                    }
                }
                else if (chr == '>')
                {
        
                    if (!_left.empty() && _left.top() == '<')
                    {
        
                        _left.pop();
                    }
                    else
                    {
        
                        _right.push(chr);
                    }
                }
            }
            if (_left.empty() && _right.empty())//左右括号没有对应不上的
            {
        
                cout << "Yes" << endl;
            }
            else
            {
        
                cout << "No" << endl;
            }
        }
        return 0;
    }