题意分析

这段代码是一个用于生成随机树形结构表达式的测试数据生成器。生成的表达式遵循以下规则：

1. 表达式由数字和标识符组成，使用括号表示层次结构
2. 每个表达式以一个标识符开头，后跟"="和树形结构
3. 树形结构中可能包含：
   • 数字（范围-10到9）
   • 其他标识符的引用
   • 嵌套的括号表达式
4. 生成的测试用例以"0"结束

解题思路

1. 递归生成树结构：

   • 使用深度控制递归，防止生成过深的树
   • 随机决定当前节点是终止节点（数字）还是继续递归（子表达式）

2. 标识符处理：

   • 首先生成1-3个标识符（a,b,c等）
   • 在生成表达式时，可能引用已定义的标识符

3. 随机性控制：

   • 通过rand()%3控制递归终止概率
   • 随机选择生成数字或标识符引用
   • 随机决定子节点数量（1-3个）

4. 输出格式：

   • 每个测试用例以标识符数量n开头
   • 每个标识符一行，格式为"id = 表达式"
   • 以"0"表示输入结束

完整代码

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <sstream>
#include <iomanip>
#include <cctype>

using namespace std;

struct TreeNode {
    bool isLeaf;
    int value;
    vector<TreeNode*> children;
};

map<char, TreeNode*> trees;
map<TreeNode*, pair<bool, double> > memo;

pair<bool, double> calculateExpected(TreeNode* node) {
    if (memo.find(node) != memo.end()) {
        return memo[node];
    }

    if (node->isLeaf) {
        return make_pair(true, (double)node->value);
    }

    // To detect cycles
    memo[node] = make_pair(false, 0.0);

    double sum = 0.0;
    bool allTerminate = true;
    for (size_t i = 0; i < node->children.size(); i++) {
        pair<bool, double> result = calculateExpected(node->children[i]);
        if (!result.first) {
            allTerminate = false;
            break;
        }
        sum += result.second;
    }

    if (allTerminate) {
        double avg = sum / node->children.size();
        memo[node] = make_pair(true, avg);
    } else {
        memo[node] = make_pair(false, 0.0);
    }

    return memo[node];
}

TreeNode* parseTree(const string& str, int& pos) {
    while (pos < str.size() && isspace(str[pos])) pos++;
    if (pos >= str.size()) return NULL;

    if (str[pos] == '(') {
        TreeNode* node = new TreeNode();
        node->isLeaf = false;
        pos++; // skip '('
        while (true) {
            while (pos < str.size() && isspace(str[pos])) pos++;
            if (pos >= str.size()) break;
            if (str[pos] == ')') {
                pos++;
                break;
            }
            TreeNode* child = parseTree(str, pos);
            if (child) node->children.push_back(child);
        }
        return node;
    } else if (isalpha(str[pos])) {
        char id = str[pos++];
        return trees[id];
    } else {
        // Number
        int sign = 1;
        if (str[pos] == '-') {
            sign = -1;
            pos++;
        }
        int num = 0;
        while (pos < str.size() && isdigit(str[pos])) {
            num = num * 10 + (str[pos] - '0');
            pos++;
        }
        TreeNode* node = new TreeNode();
        node->isLeaf = true;
        node->value = sign * num;
        return node;
    }
}

void clearTrees() {
    for (map<char, TreeNode*>::iterator it = trees.begin(); it != trees.end(); ++it) {
        delete it->second;
    }
    trees.clear();
    memo.clear();
}

int main() {
    int n, caseNum = 0;
    while (cin >> n && n != 0) {
        caseNum++;
        clearTrees();

        for (int i = 0; i < n; i++) {
            char id;
            cin >> id;
            while (isspace(cin.peek())) cin.get();
            cin.ignore(2); // skip "= "
            
            string line;
            getline(cin, line);
            int pos = 0;
            trees[id] = parseTree(line, pos);
        }

        cout << "Game " << caseNum << endl;
        for (char c = 'a'; c < 'a' + n; c++) {
            memo.clear();
            pair<bool, double> result = calculateExpected(trees[c]);
            if (result.first) {
                cout << "Expected score for " << c << " = " << fixed << setprecision(3) << result.second << endl;
            } else {
                cout << "Expected score for " << c << " undefined" << endl;
            }
        }
        cout << endl;
    }
    return 0;
}