[C++知识库]C语言栈的应用——括号匹配问题

算法思路

1. 使用一个字符串数组保存括号式。
2. 从左向右读取括号式，如果遇到左括号即'(','[','{'就压入栈中，如果遇到右括号即')',']','}'就对栈顶的元素进行对比，如果匹配成功就将栈顶元素弹出。

算法实现

// 括号匹配
_Bool parChecker()
{
    int length, i;  // 定义括号匹配长度
    LiStack L;
    L = initStack();    // 初始化栈;
    char symbolString[100]; // 使用char类型数组来保存括号式
    printf("请输入括号式:\n");
    scanf("%s", symbolString);
    getchar();  // 使用getchar消除输入时最后产生的回车
    length = (int) strlen(symbolString);    // 将括号式的长度保存给length

    // 主循环
    for (i = 0; i < length; i++)
    {
        // 如果是左括号，直接压栈
        if (symbolString[i] == '(' || symbolString[i] == '[' || symbolString[i] == '{')
        {
            push(L, symbolString[i]);
        }
        // 如果是右括号,首先按照优先级从高到低依次判断
        else
        {
            if (symbolString[i] == ')')
            {
                // 如果栈顶元素是'('则表明匹配成功
                if (top(L) == '(')
                {
                    pop(L); // 将匹配成功的括号弹出
                }
                else
                {
                    return false;
                }
            }
            else if (symbolString[i] == ']')
            {
                if (top(L) == '[')
                {
                    pop(L);
                }
                else
                {
                    return false;
                }
            }
            else
            {
                if (top(L) == '{')
                {
                    pop(L);
                }
                else
                {
                    return false;
                }
            }
        }
    }
    // 如果所有括号都匹配完，栈空则匹配成功
    if (stackEmpty(L))
    {
        return true;
    }
    else
    {
        return false;
    }

}