在C++中使用双向链表进行括号匹配

Question

我正在尝试使用 C++ 中的双向链表制作括号匹配程序当我单独尝试 Dlink class 时，我确认我的 Dlink class 确实有效。然而，当我在我的括号 mactching class 中创建一个 Dlink 对象时，该字符似乎不在双向链表中。我找不到我弄乱代码的地方。

代码如下：

#include "stdafx.h"
#include <iostream> 
#include <cstdlib>
using namespace std;

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


class Dlink {
private:
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();
    int n;
private:
    DNode * head;
    DNode *tail;
};


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() {
    cout << front() << endl;
}

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

parenthesis::parenthesis(char str[], int size) {
    str = str;
    i = size;
}

parenthesis::~parenthesis() {}

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

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

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

bool parenthesis::domatch() {
    if (isclose(str[j])) {
        return false;
    }
    else if (isopen(str[j])) {
        d.addfront(str[j]);
        flag = 1;
        j++;
    }
    if (flag == 1) {
        for (j; j < i; j++)
        {
            if (isopen(str[j])) {
                d.addfront(str[j]);
            }                     
            else if (isclose(str[j])) {                                     
                if (type(d.front()) == type(str[j])) d.removefront();   
                else {
                    return false;
                }
            }
        }
        if (!d.empty()) return false;
        else return true;
    }
}

int main() {
    char str[20];
    cout << "enter string" << endl;
    cin >> str;
    parenthesis p1 = parenthesis(str, strlen(str));
    return p1.domatch();
}

Answer 1

您的 DLink class 经历了 rule of 3 漏洞。它负责节点链。

 parenthesis p1 = parenthesis(str, strlen(str));

这个初始化是行不通的，因为 DLink 没有合适的复制构造函数。在 parenthesis 和 DLink 的临时实例被销毁后，指针将悬空。

简单的解决方法是在DLink中使用智能指针，遵循All or Nothing规则，而智能指针只有在不再使用时才会销毁列表。或者创建复制或移动构造函数，如果分配不允许使用库 classes.

仅仅为了赋值，你完全可以避免使用时间对象，但你应该意识到这个陷阱。

在C++中使用双向链表进行括号匹配

parenthesis matching using doubly linked list in c++

c++

parentheses

doubly-linked-list