C++ 实现广义表：存储字符和小数

C++ 实现广义表：存储字符和小数

本文提供 C++ 代码实现广义表，支持存储字符和小数，并演示了如何解析字符串创建广义表以及打印输出。

#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Node {
public:
    bool is_num;
    union {
        char c;
        double d;
    } val;
    vector<Node*> children;

    Node() {}
    Node(char c) : is_num(false) { val.c = c; }
    Node(double d) : is_num(true) { val.d = d; }
};

class GeneralizedList {
public:
    Node *root;

    GeneralizedList() {
        root = nullptr;
    }

    GeneralizedList(string s) {
        int pos = 0;
        root = parse(s, pos);
    }

    ~GeneralizedList() {
        clear(root);
    }

    void clear(Node *node) {
        if (node == nullptr) {
            return;
        }
        for (auto child : node->children) {
            clear(child);
        }
        delete node;
    }

    Node* parse(string s, int &pos) {
        if (s[pos] == '(') {
            ++pos; // consume '('
            Node *node = new Node();
            while (s[pos] != ')') {
                if (s[pos] == '(') {
                    node->children.push_back(parse(s, pos));
                } else if (isdigit(s[pos]) || s[pos] == '-') {
                    int start = pos;
                    while (pos < s.size() && (isdigit(s[pos]) || s[pos] == '.' || s[pos] == '-')) {
                        ++pos;
                    }
                    string num_str = s.substr(start, pos - start);
                    if (num_str.find('.') != string::npos) {
                        node->children.push_back(new Node(stod(num_str)));
                    } else {
                        node->children.push_back(new Node(num_str[0]));
                    }
                } else {
                    ++pos; // consume ','
                }
            }
            ++pos; // consume ')'
            return node;
        } else {
            int start = pos;
            while (pos < s.size() && s[pos] != ',' && s[pos] != ')') {
                ++pos;
            }
            string str = s.substr(start, pos - start);
            if (str.find('.') != string::npos) {
                return new Node(stod(str));
            } else {
                return new Node(str[0]);
            }
        }
    }

    void print() {
        print(root);
        cout << endl;
    }

    void print(Node *node) {
        if (node == nullptr) {
            return;
        }
        if (node->is_num) {
            cout << node->val.d;
        } else {
            cout << node->val.c;
        }
        if (!node->children.empty()) {
            cout << '(';
            for (int i = 0; i < node->children.size(); ++i) {
                print(node->children[i]);
                if (i != node->children.size() - 1) {
                    cout << ',';
                }
            }
            cout << ')';
        }
    }
};

int main() {
    GeneralizedList gl('(a,1.2,(b,3.4))');
    gl.print(); // expected output: a1.2(b3.4)
    return 0;
}

代码使用 Node 类表示广义表节点，其中 is_num 表示节点是否为数字，val 存储节点值。由于一个节点可以有多个子节点，使用 vector<Node*> 存储子节点。

广义表类 GeneralizedList 使用 parse 函数解析输入字符串，使用 print 函数打印广义表。

通过解析字符串 '(a,1.2,(b,3.4))'，代码创建了对应的广义表，并成功打印输出 a1.2(b3.4)。

代码实现了基本的功能，可以根据需要进行扩展，例如添加新的操作函数或修改解析规则等。