在文字处理软件或编译程序设计时，常常需要检查一个字符串或一个表达式中的括号是否相匹配?算法代码

下面是使用堆栈实现括号匹配的算法代码（使用 Python 语言实现）：

def is_match(expr):
    stack = []  # 创建一个空堆栈
    left_parentheses = "([{"
    right_parentheses = ")]}"
    for ch in expr:
        if ch in left_parentheses:
            stack.append(ch)  # 如果是左括号，将其压入堆栈中
        elif ch in right_parentheses:
            if not stack:  # 如果堆栈为空，说明没有左括号和右括号匹配
                return False
            top = stack.pop()  # 弹出堆栈顶部的元素
            if left_parentheses.index(top) != right_parentheses.index(ch):
                return False  # 如果左右括号不匹配，返回 False
    return not stack  # 如果堆栈为空，说明所有左括号和右括号都匹配，返回 True；否则返回 False

该算法的时间复杂度是 O(n)，其中 n 是字符串或表达式的长度。

相关问题

Python代码括号匹配问题 在文字处理软件或编译程序设计时，常常需要检查一个字符串或一个表达式中的括号是否相匹配?

以下是Python代码实现括号匹配问题的算法：

def is_matched(expression):
    stack = []
    for char in expression:
        if char in "({[":
            stack.append(char)
        elif char in ")}]":
            if not stack:
                return False
            current_char = stack.pop()
            if current_char == "(" and char != ")":
                return False
            if current_char == "[" and char != "]":
                return False
            if current_char == "{" and char != "}":
                return False
    return not stack

# 测试样例
print(is_matched("(){}[]")) # True
print(is_matched("{[()]}")) # True
print(is_matched("{[()]}(")) # False

该算法使用了栈的数据结构来实现括号匹配。时间复杂度为O(n)，其中n为字符串的长度。

在DevC++或VisualC++中，如何使用链式存储结构实现一个栈，并利用它来检查表达式中的括号是否匹配？

要使用链式存储结构在DevC++或VisualC++中实现一个栈，并检查表达式中的括号匹配问题，你需要按照以下步骤进行：

参考资源链接：[数据结构实验：栈与队列的应用及算法实现](https://wenku.csdn.net/doc/25ezvokohp?spm=1055.2569.3001.10343)

首先，你需要定义栈的节点结构和栈的结构。节点结构通常包含数据域和指向下一个节点的指针。栈结构则包含指向栈顶节点的指针和一个表示栈大小的整数。

typedef struct Node {
    char data;
    struct Node* next;
} Node;

typedef struct Stack {
    Node* top;
    int size;
} Stack;

接下来，编写栈的基本操作函数，包括初始化栈（InitStack）、入栈（Push）、出栈（Pop）、查看栈顶元素（GetTop）和判断栈是否为空（IsEmpty）。

void InitStack(Stack* s) {
    s->top = NULL;
    s->size = 0;
}

void Push(Stack* s, char element) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        exit(EXIT_FAILURE); // 分配内存失败，退出程序
    }
    newNode->data = element;
    newNode->next = s->top;
    s->top = newNode;
    s->size++;
}

char Pop(Stack* s) {
    if (IsEmpty(s)) {
        exit(EXIT_FAILURE); // 栈为空，退出程序
    }
    Node* temp = s->top;
    char element = temp->data;
    s->top = temp->next;
    free(temp);
    s->size--;
    return element;
}

char GetTop(Stack* s) {
    if (IsEmpty(s)) {
        exit(EXIT_FAILURE); // 栈为空，退出程序
    }
    return s->top->data;
}

int IsEmpty(Stack* s) {
    return s->size == 0;
}

最后，编写一个函数来检查给定表达式中括号是否匹配。遍历表达式字符串，对于每个字符，如果是左括号就入栈，如果是右括号就尝试从栈顶弹出一个左括号并与之匹配。如果在任何时候右括号无法与左括号匹配，或者遍历结束后栈不为空，则表示括号不匹配。

int IsBracketsMatched(const char* expression) {
    Stack s;
    InitStack(&s);
    int i = 0;
    char c;

    while ((c = expression[i++]) != '\0') {
        if (c == '(') {
            Push(&s, c);
        } else if (c == ')') {
            if (IsEmpty(&s) || Pop(&s) != '(') {
                return 0; // 括号不匹配
            }
        }
    }
    return IsEmpty(&s); // 如果栈为空，则括号匹配；否则不匹配
}

在DevC++或VisualC++中编译和运行上述代码，就可以检查任意给定表达式中的括号是否正确匹配了。这个实现利用了链式存储结构的栈，展示了其在括号匹配问题中的应用。

参考资源链接：[数据结构实验：栈与队列的应用及算法实现](https://wenku.csdn.net/doc/25ezvokohp?spm=1055.2569.3001.10343)