括号匹配问题数据结构c语言

括号匹配问题，也称为括号平衡问题，通常涉及检查给定字符串中的括号是否配对。这种问题在计算机科学中常用于评估算法效率，特别是在处理表达式解析、语法分析等场景。在C语言中，我们可以使用栈（stack）作为基本的数据结构来解决这个问题。

以下是简单的步骤：

1. 创建一个空栈（通常是字符数组或链表节点）。
2. 遍历输入字符串中的每个字符：
- 如果遇到左括号（如'('），将其压入栈中。
- 如果遇到右括号（如')'）：
- 如果栈为空，说明匹配失败。
- 否则，弹出栈顶元素（上一个遇到的左括号），并与当前右括号比较。如果不匹配，同样表示失败。
3. 如果遍历完所有字符，栈为空，那么括号是匹配的；否则，不匹配。

#include <stdbool.h>
#include <stdio.h>

bool isParenthesesMatched(char str[]) {
    stack<char> s;
    for (int i = 0; str[i]; ++i) {
        if (str[i] == '(' || str[i] == '[' || str[i] == '{')
            s.push(str[i]);
        else if (!s.empty() && ((str[i] == ')' && s.top() == '(') ||
                                (str[i] == ']' && s.top() == '[') ||
                                (str[i] == '}' && s.top() == '{')))
            s.pop();
        else
            return false;
    }
    return s.empty(); // 如果遍历完还剩括号在栈里，则不匹配
}

int main() {
    char input[] = "({[()]})";
    if (isParenthesesMatched(input))
        printf("括号匹配。\n");
    else
        printf("括号不匹配。\n");
    return 0;
}