C++本科生导师制广义表代码实现

广义表是一种线性结构，它可以包含原子和子表。下面是一个简单的C++实现：

#include<iostream>
using namespace std;

//定义广义表结点
template<typename T>
class GLNode{
public:
    bool tag;//标记，1表示结点是原子，0表示结点是子表
    union{
        T atom;
        GLNode<T> *hp;//指向广义表的表头
    };
    GLNode<T> *tp;//指向广义表的表尾
    GLNode(bool t, T a = 0, GLNode<T> *h = nullptr, GLNode<T> *t2 = nullptr) :tag(t), atom(a), hp(h), tp(t2){}
};

//定义广义表类
template<typename T>
class GList{
public:
    GList(string str);//字符串构造广义表
    void PrintList();//打印广义表
private:
    GLNode<T> *head;//广义表头结点
};

//构造函数
template<typename T>
GList<T>::GList(string str){
    int len = str.length();
    head = nullptr;
    GLNode<T> *p = nullptr, *q = nullptr;
    int k = 0;//记录当前扫描到的位置
    while (k < len){
        char ch = str[k];
        if (ch == '('){//遇到左括号，创建新的子表
            q = new GLNode<T>(0, 0, nullptr, nullptr);
            if (!head) head = q;
            else p->tp = q;
            p = q;
            k++;
        }
        else if (ch == ')'){//遇到右括号，回溯到上一层子表
            p = p->hp;//回到上一层子表
            k++;
        }
        else if (ch == ',') k++;
        else{//读入原子
            string str_atom;
            while (k < len && str[k] != '(' && str[k] != ')' && str[k] != ','){
                str_atom += str[k];
                k++;
            }
            q = new GLNode<T>(1, str_atom, nullptr, nullptr);
            if (!head) head = q;
            else p->tp = q;
        }
    }
}

//打印广义表
template<typename T>
void GList<T>::PrintList(){
    GLNode<T> *p = head;
    cout << "(";
    while (p){
        if (p->tag) cout << p->atom;
        else{
            GList<T> gl(p->hp);
            gl.PrintList();
        }
        if (p->tp) cout << ",";
        p = p->tp;
    }
    cout << ")";
}

int main(){
    string str = "(1,(2,3),4)";
    GList<string> gl(str);
    gl.PrintList();
    cout << endl;
    return 0;
}

使用示例：

输入字符串 `(1,(2,3),4)`，输出结果 `(1,(2,3),4)`