使用栈实现字符串中括号匹配的C++程序

引言

在《数据结构基础》（C语言版，第二版），作者Ellis Horowitz和译者朱仲涛的指导下，我们探讨了如何使用栈来验证字符串中的括号匹配问题。本文将详细介绍这一过程，并提供完整的C++代码示例。

一、题目描述

给定一个包含括号的字符串，编写一个程序来检查这些括号是否正确配对。括号包括圆括号（()）、方括号（[]）和花括号（{}）。如果所有类型的括号都正确闭合且嵌套正确，则返回true；否则返回false。

二、C++代码实现

1. 顺序栈实现

顺序栈是一种基于数组的栈结构，具有固定的容量。以下是使用顺序栈实现括号匹配的代码：

#include 
using namespace std;
#define MaxSize 100
typedef char datatype;
typedef struct {
    datatype data[MaxSize];
    int top;
} seq_stack;

void InitStack(seq_stack *&s) {
    s = (seq_stack *)malloc(sizeof(seq_stack));
    s->top = -1;
}

void DestoryStack(seq_stack *s) {
    free(s);
}

bool StackEmpty(seq_stack *s) {
    return s->top == -1;
}

void Push(seq_stack *&s, datatype e) {
    if (s->top == MaxSize - 1)
        printf("栈满！\n");
    else {
        s->top++;
        s->data[s->top] = e;
    }
}

datatype Pop(seq_stack *s) {
    if (s->top == -1) {
        printf("栈空！\n");
        return '\0';
    } else
        return s->data[s->top--];
}

datatype GetTop(seq_stack *s) {
    if (s->top == -1) {
        printf("栈空！\n");
        return '\0';
    } else
        return s->data[s->top];
}

bool is_match(const char *c) {
    datatype e;
    seq_stack *s;
    InitStack(s);
    int i = 0;
    bool match = true;
    while (c[i] != '\0' && match) {
        switch (c[i]) {
            case '(': Push(s, c[i]); break;
            case ')': match = GetTop(s) == '(' ? (Pop(s), true) : false; break;
            case '[': Push(s, c[i]); break;
            case ']': match = GetTop(s) == '[' ? (Pop(s), true) : false; break;
            case '{': Push(s, c[i]); break;
            case '}': match = GetTop(s) == '{' ? (Pop(s), true) : false; break;
        }
        i++;
    }
    if (!StackEmpty(s))
        match = false;
    DestoryStack(s);
    return match;
}

int main() {
    const char *s = "s{a(jfi)fjiasj[hfuah]}";
    if (is_match(s))
        printf("%s 该字符串中括号匹配！\n", s);
    else
        printf("%s 该字符串中括号不匹配！\n", s);
    return 0;
}

2. 链栈实现

链栈是基于链表的栈结构，没有固定容量限制。以下是使用链栈实现括号匹配的代码：

#include 
using namespace std;
typedef char datatype;
typedef struct link_stack {
    datatype data;
    struct link_stack *link;
} link_stack;

void InitStack(link_stack *&s) {
    s = new link_stack;
    s->link = NULL;
}

void clear_stack(link_stack *s) {
    link_stack *p = s->link, *r;
    s->link = NULL;
    while (p != NULL) {
        r = p;
        p = p->link;
        free(r);
    }
}

bool StackEmpty(link_stack *s) {
    return s->link == NULL;
}

int stack_len(link_stack *s) {
    int len = 0;
    link_stack *temp = s->link;
    while (temp != NULL) {
        len++;
        temp = temp->link;
    }
    return len;
}

datatype GetTop(link_stack *s) {
    return s->link == NULL ? '\0' : s->link->data;
}

void Push(link_stack *s, datatype e) {
    link_stack *temp = new link_stack;
    temp->data = e;
    temp->link = s->link;
    s->link = temp;
}

datatype Pop(link_stack *s) {
    if (s->link == NULL)
        return '\0';
    datatype e = s->link->data;
    link_stack *temp = s->link;
    s->link = temp->link;
    free(temp);
    return e;
}

bool is_match(const char *c) {
    datatype e;
    link_stack *s;
    InitStack(s);
    int i = 0;
    bool match = true;
    while (c[i] != '\0' && match) {
        switch (c[i]) {
            case '(': Push(s, c[i]); break;
            case ')': match = GetTop(s) == '(' ? (Pop(s), true) : false; break;
            case '[': Push(s, c[i]); break;
            case ']': match = GetTop(s) == '[' ? (Pop(s), true) : false; break;
            case '{': Push(s, c[i]); break;
            case '}': match = GetTop(s) == '{' ? (Pop(s), true) : false; break;
        }
        i++;
    }
    if (!StackEmpty(s))
        match = false;
    clear_stack(s);
    return match;
}

int main() {
    const char *s = "s{a(jfi)fjiasj[hfuah]}";
    if (is_match(s))
        printf("%s 该字符串中括号匹配！\n", s);
    else
        printf("%s 该字符串中括号不匹配！\n", s);
    return 0;
}

总结

通过上述两种栈的实现方式，我们可以有效地判断字符串中的括号是否匹配。顺序栈适用于已知最大长度的情况，而链栈则更适合动态变化的数据。理解这两种实现方法有助于更好地掌握栈这一重要的数据结构。