C++利用栈结构解决括号字符串匹配问题

核心逻辑与准备条件

要实现括号匹配的判断，首先需要构建一个能够存储字符的栈。栈需要支持以下基本操作：

• 初始化：设置栈顶指针为 -1，表示空栈。
• 入栈 (Push)：当栈未饱和时，将字符存入栈顶并增加索引。
• 出栈 (Pop)：当栈非空时，取出栈顶字符并减少索引。
• 判空：检查栈顶指针是否为 -1。

第1步：定义栈结构体及初始化

目的：确立数据存储结构和初始状态。

操作：定义一个包含字符数组和整型栈顶指针的结构体，并编写初始化函数将栈顶设为 -1。

#define stacksize 100
struct stack {
    char strstack[stacksize];
    int top;
};

void InitStack(stack &s) {
    s.top = -1;
}

第2步：实现入栈与出栈操作

目的：确保数据存取时的边界安全，防止栈溢出或下溢。

入口：调用 Push 和 Pop 函数。

动作： - Push：检查 top == stacksize - 1 若为真则返回失败，否则递增 top 并赋值。
- Pop：检查 top == -1 若为真则返回失败，否则保存当前栈顶值，递减 top 并返回。

char Push(stack &s, char a) {
    if (s.top == stacksize - 1) return 0;
    s.top++;
    s.strstack[s.top] = a;
    return a;
}

char Pop(stack &s) {
    if (s.top == -1) return 0;
    char a = s.strstack[s.top];
    s.top--;
    return a;
}

第3步：主校验逻辑 Check 函数

目的：遍历字符串，执行匹配算法。

入口：Check(char *str)。

重要参数：输入字符串指针 str。

动作：

1. 初始化栈实例 s 并调用 InitStack(s)。
2. 获取字符串长度 strlen(str)，循环遍历每个字符。
3. 使用 switch 语句判断字符类型：

• 若为左括号 (、[、{，调用 Push(s, a) 入栈。
• 若为右括号 )，调用 Pop(s)，若返回值不等于对应的左括号 (，则返回 0（不匹配）。
• 同理处理 ] 和 } 的情况。

以下是完整的校验函数实现：

int Check(char *str) {
    stack s;
    InitStack(s);
    int strn = strlen(str);
    for (int i = 0; i < strn; i++) {
        char a = str[i];
        switch (a) {
        case '(':
        case '[':
        case '{':
            Push(s, a);
            break;
        case ')':
            if (Pop(s) != '(') return 0;
            break;
        case ']':
            if (Pop(s) != '[') return 0;
            break;
        case '}':
            if (Pop(s) != '{') return 0;
            break;
        }
    }
    // 判断栈是否为空
    if (s.top == -1) return 1;
    else return 0;
}

完整运行代码

为了便于测试，以下是包含标准库引入、用户交互及上述所有功能的完整 C++ 代码。该代码可直接编译运行，用于输入字符串并输出匹配结果。

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

#define stacksize 100

struct stack {
    char strstack[stacksize];
    int top;
};

void InitStack(stack &s) {
    s.top = -1;
}

char Push(stack &s, char a) {
    if (s.top == stacksize - 1) return 0;
    s.top++;
    s.strstack[s.top] = a;
    return a;
}

char Pop(stack &s) {
    if (s.top == -1) return 0;
    char a = s.strstack[s.top];
    s.top--;
    return a;
}

int Empty(stack &s) {
    if (s.top == -1) return 1;
    else return 0;
}

int Check(char *str) {
    stack s;
    InitStack(s);
    int strn = strlen(str);
    for (int i = 0; i < strn; i++) {
        char a = str[i];
        switch (a) {
        case '(':
        case '[':
        case '{':
            Push(s, a);
            break;
        case ')':
            if (Pop(s) != '(') return 0;
            break;
        case ']':
            if (Pop(s) != '[') return 0;
            break;
        case '}':
            if (Pop(s) != '{') return 0;
            break;
        }
    }
    if (Empty(s)) return 1;
    else return 0;
}

int main() {
    char str[100];
    cout << "请输入一个长度小于100的字符串:" << endl;
    cin >> str;
    int re = Check(str);
    if (re == 1) {
        cout << "你输入的字符串括号完全匹配！" << endl;
    } else {
        cout << "你输入的字符串括号不匹配！" << endl;
    }
    return 0;
}

以上就是C++中使用栈来判断括号字符串匹配问题的详细内容，更多关于C++算法设计与数据结构学习资料的关注请关注本站其它相关文章！