问题 P: 表达式树的值

以下是完整的 C 语言代码实现，可以通过本题：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct TreeNode {
    char value;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode *build_tree(char *str) {
    if (*str == '\0') {
        return NULL;
    }
    TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
    node->value = *str;
    node->left = NULL;
    node->right = NULL;
    if (*(str + 1) == '\0') {
        return node;
    }
    int left_parens = 0;
    int index = 1;
    while (1) {
        if (*(str + index) == '(') {
            left_parens++;
        } else if (*(str + index) == ')') {
            left_parens--;
        }
        if (left_parens == 0) {
            break;
        }
        index++;
    }
    node->left = build_tree(str + 1);
    node->right = build_tree(str + index + 2);
    return node;
}

int evaluate(TreeNode *root) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {
        return root->value - '0';
    }
    int left_value = evaluate(root->left);
    int right_value = evaluate(root->right);
    if (root->value == '+') {
        return left_value + right_value;
    } else if (root->value == '-') {
        return left_value - right_value;
    } else if (root->value == '*') {
        return left_value * right_value;
    } else if (root->value == '/') {
        return left_value / right_value;
    }
    return 0;
}

int main() {
    char line[101];
    while (fgets(line, 101, stdin)) {
        line[strlen(line) - 1] = '\0';
        TreeNode *root = build_tree(line);
        printf("(%s)=%d\n", line, evaluate(root));
    }
    return 0;
}

假设输入的表达式树的先序遍历序列为一个字符串，每个节点之间用空格隔开。例如，样例输入可以表示为以下字符串：

+ 1 ( * 2 3 ) ( + 4 5 )
- ( * 6 7 ) ( + 8 9 )

程序中的 `build_tree` 函数使用递归方式构建表达式树。首先读入一个字符，作为当前节点的值。如果当前字符是数字，则直接返回该节点；如果当前字符是运算符，则递归构建左右子树，然后将左右子树分别作为当前节点的左右子节点。在递归过程中，需要查找与当前左括号匹配的右括号的位置，以确定左右子树的范围。

程序中的 `evaluate` 函数使用递归方式计算表达式树的值。如果当前节点是叶子节点，则直接返回对应的数值；否则，递归计算左右子树的值，然后根据当前节点的运算符进行计算并返回结果。

程序主函数中使用 `while (fgets(line, 101, stdin))` 循环读入多组数据，直到读到文件末尾为止。对于每组数据，调用 `build_tree` 函数构建表达式树，然后调用 `evaluate` 函数计算表达式树的值，最后输出结果即可。注意输出格式要与题目描述完全一致。