C++中基于双向链表的括号匹配程序代码问题求助

我帮你排查了代码里的几个关键问题，这些问题直接导致了括号匹配类里的双向链表无法正确存储字符，咱们一个个拆解来看：

1. 构造函数中字符串拷贝完全无效 #

你的parenthesis类构造函数里写的str = str;是典型的无效操作——这里只是把参数的指针赋值给了成员数组名（数组名退化为指针后，这样的赋值并不会拷贝字符串内容），导致成员变量str根本没拿到用户输入的括号字符串。后面domatch函数访问str[j]时，拿到的都是未初始化的垃圾值，自然没法把正确的括号存入链表。

修正方法：用strcpy（需要额外包含<cstring>头文件）把传入的字符串拷贝到成员数组里：

parenthesis::parenthesis(char str[], int size) {
    strcpy(this->str, str); // 替换原来的str = str;
    i = size;
    flag = 0; // 顺便初始化flag，避免随机值干扰逻辑
    j = 0;
}

2. 未初始化的成员变量引发逻辑混乱 #

parenthesis类里的flag没有初始化，默认是随机值，会导致domatch函数的分支判断混乱（比如可能直接跳过核心的匹配循环）。必须在构造函数里把它初始化为0。

3. 右括号匹配时的边界检查缺失 #

当遇到右括号时，你没有先检查链表是否为空。如果链表为空（比如前面没有对应的左括号），直接调用d.front()会访问tail节点的data（空链表时head->next指向tail），而tail的data从未被赋值，这会导致程序崩溃或者错误结果。

修正方法：处理右括号前先判断链表是否为空：

else if (isclose(str[j])) {
    if (d.empty()) { // 新增：链表为空，说明没有对应的左括号
        return false;
    }
    if (type(d.front()) == type(str[j])) 
        d.removefront();
    else {
        return false;
    }
}

4. type函数缺少默认返回值 #

如果传入的字符不是括号，type函数没有返回值，会返回随机值，可能导致匹配逻辑错误。需要添加默认返回值：

int parenthesis::type(char a) {
    if (a == ')' || a == '(') return 1;
    else if (a == '}' || a == '{') return 2;
    else if (a == ']' || a == '[') return 3;
    return 0; // 新增：默认返回值，处理非括号字符
}

5. 辅助函数的调试优化 #

你的Dlink::print函数只输出第一个元素，不利于调试。可以修改为遍历整个链表输出所有元素：

void Dlink::print() {
    DNode* current = head->next;
    while (current != tail) {
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;
}

6. main函数的输出与返回值优化 #

main函数直接返回domatch()的bool值虽然可以，但不如直接输出匹配结果更直观：

int main() {
    char str[20];
    cout << "enter string" << endl;
    cin >> str;
    parenthesis p1(str, strlen(str)); // 这里不需要用赋值构造，直接初始化即可
    if (p1.domatch()) {
        cout << "括号匹配成功！" << endl;
    } else {
        cout << "括号匹配失败！" << endl;
    }
    return 0;
}

修正后的完整代码 #

#include "stdafx.h" 
#include <iostream> 
#include <cstdlib>
#include <cstring> // 新增：用于strcpy
using namespace std; 

class DNode {
private:
    char data;
    DNode *next;
    DNode *prev;
    friend class Dlink;
};

class Dlink {
private:
    DNode * head;
    DNode *tail;
    int n;
public:
    Dlink();
    ~Dlink();
    bool empty() const;
    void addfront(char);
    void removefront();
    void addback(char);
    void removeback();
    void add(DNode*, const char);
    void remove(DNode *);
    const char& front() const;
    const char& back() const;
    int size();
    void print();
};

Dlink::Dlink() {
    head = new DNode;
    tail = new DNode;
    head->next = tail;
    tail->prev = head;
    n = 0;
}

Dlink::~Dlink() {
    while (!empty()) removefront();
    delete head;
    delete tail;
}

void Dlink::add(DNode *v, const char e) {
    DNode *u = new DNode;
    u->data = e;
    u->next = v;
    u->prev = v->prev;
    v->prev->next = u;
    v->prev = u;
    n++;
}

void Dlink::addfront(const char e) {
    add(head->next, e);
}

void Dlink::addback(const char e) {
    add(tail, e);
}

void Dlink::remove(DNode *v) {
    DNode *u = v->prev;
    DNode *w = v->next;
    u->next = w;
    w->prev = u;
    delete v;
    n--;
}

void Dlink::removefront() {
    remove(head->next);
}

void Dlink::removeback() {
    remove(tail->prev);
}

bool Dlink::empty() const {
    return (head->next == tail);
}

const char& Dlink::front() const {
    return head->next->data;
}

const char& Dlink::back() const {
    return tail->prev->data;
}

int Dlink::size() {
    return n;
}

void Dlink::print() {
    DNode* current = head->next;
    while (current != tail) {
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;
}

class parenthesis {
private:
    Dlink d;
    char str[20];
    int i;
    int flag;
    int j;
public:
    parenthesis(char[], int);
    ~parenthesis();
    bool domatch();
    bool isopen(char);
    bool isclose(char);
    int type(char);
};

parenthesis::parenthesis(char str[], int size) {
    strcpy(this->str, str);
    i = size;
    flag = 0;
    j = 0;
}

parenthesis::~parenthesis() {}

bool parenthesis::isopen(char a) {
    return (a == '(' || a == '{' || a == '[');
}

bool parenthesis::isclose(char a) {
    return (a == ')' || a == '}' || a == ']');
}

int parenthesis::type(char a) {
    if (a == ')' || a == '(') return 1;
    else if (a == '}' || a == '{') return 2;
    else if (a == ']' || a == '[') return 3;
    return 0;
}

bool parenthesis::domatch() {
    // 处理第一个字符是右括号的情况
    if (j < i && isclose(str[j])) {
        return false;
    }
    // 遍历所有字符
    while (j < i) {
        if (isopen(str[j])) {
            d.addfront(str[j]);
        } else if (isclose(str[j])) {
            if (d.empty()) {
                return false;
            }
            if (type(d.front()) == type(str[j])) {
                d.removefront();
            } else {
                return false;
            }
        }
        j++;
    }
    // 最后检查链表是否为空
    return d.empty();
}

int main() {
    char str[20];
    cout << "enter string" << endl;
    cin >> str;
    parenthesis p1(str, strlen(str));
    if (p1.domatch()) {
        cout << "括号匹配成功！" << endl;
    } else {
        cout << "括号匹配失败！" << endl;
    }
    return 0;
}

现在测试这个代码，输入{[()]}会输出匹配成功，输入{[(])}会输出失败，输入(()也会失败，完全符合预期。

内容的提问来源于stack exchange，提问作者鞙れ頃�,c++;doubly-linked-list;parentheses"