题解 | 牛群的秘密通信

语言： C++

知识点： 栈

分析： 对输入的字符串进行遍历，遍历过程中若当前是左括号则入栈；当前是右括号，则将其与栈顶的左括号进行匹配：若匹配成功，则将匹配过的左括号（当前栈顶元素）出栈；若匹配不成功，则直接返回false。在遍历过程中遇到当前为右括号而此时栈为空的情况，则表示此右括号无法匹配，直接返回false。最终遍历完整个字符串后：若此时栈不为空，表示仍有左括号未被匹配，则返回false；否则即为全部括号都匹配成功，返回true。

代码实现：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    bool is_valid_cow_communication(string s) {
        stack<char> sk; // 使用栈存储左括号
        for(int i = 0; i < s.size(); i++)
        {
            if(s[i] == '(' || s[i] == '[' || s[i] == '{')
            {
                sk.push(s[i]); // 遇到左括号则入栈
            }
            else // 遇到右括号
            {
                char t;
                if(!sk.empty())
                {
                    t = sk.top(); // 若栈不空，则将栈顶左括号取出用于匹配
                }
                else
                {
                    return false; // 若栈空，表示没有与该右括号匹配的左括号，返回false
                }
                if(s[i] == ')' && t == '(' || s[i] == ']' && t == '[' || s[i] == '}' && t == '{')
                {
                    sk.pop(); // 若左右括号匹配成功，将匹配过的左括号出栈
                }
                else
                {
                    return false; // 若匹配不成功，返回false
                }
            }
        }
        if(!sk.empty())
        {
            return false; // 若最终遍历完后栈中还有剩余的左括号，也需返回false
        }
        else
        {
            return true; // 最终所有条件均满足返回true
        }
    }
};