栈的应用--括号匹配问题

     在编程世界中，数据结构是构建高效算法的基石。栈（Stack）是一种特别重要的数据结构，它遵循后进先出（LIFO）的原则。今天，我们将探索如何利用栈的强大功能来解决一个非常普遍的问题——括号匹配。这个问题在编译器设计、文本编辑器和许多其他场合中都非常常见。

 1. 括号匹配问题概述

     括号匹配问题要求我们确定给定字符串中的括号是否正确匹配。常见的括号类型包括圆括号 `()`, 方括号 `[]` 和花括号 `{}`。正确的匹配意味着每个开括号都有一个对应的闭括号，并且括号的顺序也是正确的。

例如，字符串 `"(a+b)*[c-d]"` 是正确的匹配，而 `"(a+b)*[c-d"` 和 `"[a+b]*(c-d)"` 都不是正确的匹配。

2. 栈的引入

为了解决这个问题，我们可以使用栈来跟踪括号的匹配情况。每当我们遇到一个开括号，我们就将其推入栈中。当我们遇到一个闭括号时，我们检查栈顶的元素是否与之匹配。如果匹配，则弹出栈顶元素；如果不匹配或栈已空，则表示括号不匹配。

 3. 解决方案实现

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

bool isMatched(const char *str) {
    char stack[100];
    int top = -1;

    for (int i = 0; str[i] != '\0'; i++) {
        char ch = str[i];
        if (ch == '(' || ch == '[' || ch == '{') {
            stack[++top] = ch;
        } else if (ch == ')' || ch == ']' || ch == '}') {
            if (top == -1) {
                return false;
            }
            char left = stack[top--];
            if ((ch == ')' && left != '(') || (ch == ']' && left != '[') || (ch == '}' && left != '{')) {
                return false;
            }
        }
    }

    return top == -1;
}

int main() {
    const char *str = "{[()]}";
    if (isMatched(str)) {
        printf("括号匹配
");
    } else {
        printf("括号不匹配
");
    }
    return 0;
}

4. 算法解析

    这个算法的时间复杂度是 O(n)，其中 n 是表达式的长度。因为我们只遍历了一次字符串，每个字符只被推入栈一次或从栈中弹出一次。

空间复杂度是 O(n)，因为在最坏的情况下，整个字符串都是开括号，我们需要将它们全部推入栈中。

 5. 总结

    通过栈这一数据结构，我们能够优雅地解决括号匹配问题。这个例子展示了栈在处理具有特定顺序要求的问题时的实用性。无论是在学术还是工业领域，理解并能够应用这样的数据结构和算法，对于编写高效的代码来说都是非常重要的。