栈的应用（括号匹配）

括号匹配

栈的应用
括号匹配有两种，一种是只用匹配一种类型的括号的，还有一种是要多种都匹配

// 栈的应用，括号的匹配问题

// 简单的括号匹配 -> 只有一中类型的括号
#include <iostream>
#include <algorithm>
#include <stack>
#include <string>

using namespace std;

// 初始化栈
bool match(string str_test)
{
    if (str_test == "") return true;
    // normal
    // 初始化栈
    stack<char> s;
    // 遍历字符串的每一个字符
    for (int i = 0; i < str_test.length(); i ++)
    {
        if (str_test[i] == '(')
        {
            // 左括号进栈
            s.push(str_test[i]);
        }
        else if (str_test[i] == ')')
        {
            // 在栈中匹配右括号
            // 当前的栈是空的，无法匹配直接失败
            if (s.empty()) return false; 
            // 成功匹配
            else s.pop(); // 对应的左括号弹栈
        }
    }
    // 如果遍历结束的时候，栈没空，失败，栈空，成功
    if (s.empty()) return true;
    return false;
}

// 复杂的括号匹配，多种(, [, {, }, ], )

// 辅助函数，栈顶左括号和当前的右括号是不是匹配
bool can_match(char left, char right)
{
    if (left == '(')
    {
        if (right == ')') return true;
        else return false;
    }
    else if (left == '{')
    {
        if (right == '}') return true;
        else return false;
    }
    else
    {
        if (right == ']') return true;
        else return false;
    }
}

// 解决的思路是外部放一个匹配的数组，看每次的右括号和栈顶的左括号是不是匹配
bool match2(string str_test)
{
    if (str_test == "") return true;
    // normal
    // 初始化栈
    stack<char> s;
    // 遍历字符串的每一个字符
    for (int i = 0; i < str_test.length(); i ++)
    {
        // 左括号进栈
        if (str_test[i] == '(' || str_test[i] == '{' || str_test[i] == '[' )
        {
            s.push(str_test[i]);
        }
        // 右括号判断
        if (str_test[i] == ')' || str_test[i] == '}' || str_test[i] == ']' )
        {
            // 判断栈顶的括号是不是可以和当前的右括号配对
            if (can_match(s.top(), str_test[i]))
            {
                s.pop(); // 可以配对, 栈顶弹栈
            } 
            else return false;
        }
    }
    if (s.empty()) return true;
    return false; // 栈不空失败
}


int main()
{
    string s;
    cin >> s;
    if (match(s)) cout << "成功" << endl;
    else cout << "失败" << endl;
    string s2;
    cin >> s2;
    if (match2(s2)) cout << "成功" << endl;
    else cout << "失败" << endl;
}