用栈实现括号匹配算法

栈是实现括号匹配算法的重要数据结构。具体实现步骤如下：
1. 遍历传入的算术组，剔除其他数字，只比较左右括号。
2. 将左括号压入栈中。
3. 遍历右括号，如果右括号和栈顶的左括号匹配，则将栈顶的左括号弹出栈。
4. 如果在遍历右括号的过程中，发现右括号和栈顶的左括号不匹配，则说明左右括号匹配次序不正确。
5. 如果在遍历完传入的算术组后，栈中还有左括号，则说明左括号多于右括号。
6. 如果在遍历完传入的算术组后，栈为空，则说明左括号少于右括号，匹配成功。

相关问题

c 用栈实现括号匹配算法

括号匹配算法是指检查给定字符串中的括号是否匹配的算法。其中，栈是实现该算法的常用数据结构。在遍历字符串时，我们可以将左括号入栈，当遇到右括号时，再将栈顶元素弹出。如果弹出的左括号与当前右括号不匹配，或者栈已空而遇到右括号，则说明括号不匹配。

以下是使用 C 语言实现括号匹配算法的代码：

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

#define MAX_SIZE 100

// 定义栈结构体
typedef struct {
    char data[MAX_SIZE];
    int top;
} Stack;

// 初始化栈
void initStack(Stack* s) {
    s->top = -1;
}

// 判断栈是否为空
bool isEmpty(Stack* s) {
    return s->top == -1;
}

// 判断栈是否已满
bool isFull(Stack* s) {
    return s->top == MAX_SIZE - 1;
}

// 入栈
void push(Stack* s, char c) {
    if (isFull(s)) {
        fprintf(stderr, "Stack is full!\n");
        exit(EXIT_FAILURE);
    }
    s->data[++s->top] = c;
}

// 出栈
char pop(Stack* s) {
    if (isEmpty(s)) {
        fprintf(stderr, "Stack is empty!\n");
        exit(EXIT_FAILURE);
    }
    return s->data[s->top--];
}

// 括号匹配算法
bool checkBrackets(char* str) {
    Stack s;
    initStack(&s);

    for (int i = 0; str[i] != '\0'; i++) {
        if (str[i] == '(' || str[i] == '[' || str[i] == '{') {
            push(&s, str[i]);
        } else if (str[i] == ')' || str[i] == ']' || str[i] == '}') {
            if (isEmpty(&s)) {
                return false;
            }
            char c = pop(&s);
            if ((str[i] == ')' && c != '(') || (str[i] == ']' && c != '[') || (str[i] == '}' && c != '{')) {
                return false;
            }
        }
    }

    return isEmpty(&s);
}

// 测试括号匹配算法
int main() {
    char str[MAX_SIZE];
    printf("Enter a string with brackets: ");
    scanf("%s", str);

    if (checkBrackets(str)) {
        printf("Brackets are matched!\n");
    } else {
        printf("Brackets are not matched!\n");
    }

    return 0;
}

在上面的代码中，我们首先定义了一个栈结构体，包含一个字符数组和一个栈顶指针。然后，我们定义了几个用于操作栈的函数，包括初始化栈、入栈、出栈、判断栈是否为空或已满等。最后，我们实现了括号匹配算法，使用栈来判断字符串中的括号是否匹配。在 main 函数中，我们通过用户输入一个字符串来测试括号匹配算法的正确性。

在python中用栈实现括号匹配算法

答案：

可以通过栈的特性来判断括号是否匹配。具体实现如下：

1. 新建一个空栈。

2. 遍历字符串中的每个字符，对于每个字符：

a. 如果是左括号，将其压入栈中。

b. 如果是右括号，弹出栈顶元素，如果栈顶元素不是相应的左括号，则说明括号不匹配。

3. 遍历结束后，如果栈为空，则说明括号匹配，否则说明有左括号没有右括号与之匹配。

下面是一个使用栈实现括号匹配的示例代码：

def bracket_match(s):
    stack = []
    left_brackets = ['(', '[', '{']
    right_brackets = [')', ']', '}']
    for c in s:
        if c in left_brackets:
            stack.append(c)
        elif c in right_brackets:
            if not stack:
                return False
            if left_brackets.index(stack.pop()) != right_brackets.index(c):
                return False
    return not stack

s = "{[()]}"
print(bracket_match(s))  # Output: True
s = "{[(])}"
print(bracket_match(s))  # Output: False
s = "()[]{}"
print(bracket_match(s))  # Output: True