// 【场景】栈应用
//  编写一个程序，判断给定的字符串是否是有效的括号序列。例如，对于字符串 "{[()]}"，应返回 true；对于字符串 "{[(])}"，应返回 false。
// 【提示】华为OD的机试题
#include <iostream>
#include <stack>
#include <string>

using namespace std;

bool judge(const string &str)
{
    stack<char> stk;
    int max_depth = 0;

    for (char c : str) // 增强型 for 循环，用于遍历字符串
    {
        if (c == '(' || c == '[' || c == '{')
        {
            stk.push(c); // 当左括号出现时，入栈
        }
        else if (c == ')' || c == ']' || c == '}') // 当碰到右括号时，开始匹配
        {
            if (stk.empty()) // 如果栈已经为空，说明没有左括号与之匹配
            {
                return false; // 返回无法匹配
            }

            char top = stk.top(); // 拿出栈顶元素

            if (max_depth < stk.size())
                max_depth = stk.size();

            stk.pop(); // 弹出栈顶元素

            // 判断本次取出的字符与栈顶元素是否匹配，即左右括号是否匹配，不匹配则返回无效，匹配则继续进行下一轮遍历循环
            if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{'))
            {
                return false; // 括号不匹配
            }
        }
    }

    cout << "括号栈的最大深度为: " << max_depth << endl;
    return stk.empty(); // 栈为空表示括号完全匹配 = 有效 = true = 1，反之，如果栈非空，说明还有未匹配的左括号，返回无效 = false = 0
}

string print(bool flag)
{
    if (flag) // flag 为 true = 1
        return "有效";
    else
        return "无效";
}

int main()
{
    // string str1 = "{[(])}";
    // string str1 = "{(])}";
    string str1 = "{[(s[s])s]}[][[[[()]]]]";
    cout << "括号序列 " << str1 << " 是否有效: " << print(judge(str1)) << endl; // 1
    return 0;
}