题目描述 读入表达式树的先序遍历字符串，求其值。运算符只可能是加减乘除，保证输入的每个子表达式树的结果都是整数值且可以用C语言的int类型表达。 输入 输入由多组测试数据组成。 每组数据包含一行字符串，即表达式树的先序遍历序列，字符串长度大于0且不超过100。 输出 见样例。 样例输入 Copy + 13 # # * 5 # # 9 # # * + 13 # # 5 # # 9 # # 样例输出 Copy (13+(5*9))=58 ((13+5)*9)=162代码实现

以下是C++的代码实现：

#include <iostream>
#include <stack>
#include <string>
using namespace std;

// 定义二叉树节点
struct TreeNode {
    char val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char x) : val(x), left(NULL), right(NULL) {}
};

// 建立表达式树
TreeNode* buildTree(string& s, int& pos) {
    if (pos >= s.size()) {
        return NULL;
    }
    char c = s[pos];
    if (c == '#' || c == '+' || c == '-' || c == '*' || c == '/') {
        pos++;
        TreeNode* node = new TreeNode(c);
        node->left = buildTree(s, pos);
        node->right = buildTree(s, pos);
        return node;
    } else {
        pos++;
        return new TreeNode(c - '0');
    }
}

// 计算表达式树的值
int evalTree(TreeNode* root) {
    if (root->val == '#') {
        return 0;
    } else if (root->val >= '0' && root->val <= '9') {
        return root->val - '0';
    } else {
        int left_val = evalTree(root->left);
        int right_val = evalTree(root->right);
        if (root->val == '+') {
            return left_val + right_val;
        } else if (root->val == '-') {
            return left_val - right_val;
        } else if (root->val == '*') {
            return left_val * right_val;
        } else if (root->val == '/') {
            return left_val / right_val;
        }
    }
    return 0;
}

int main() {
    string s;
    while (getline(cin, s)) {
        int pos = 0;
        TreeNode* root = buildTree(s, pos);
        int res = evalTree(root);
        cout << "(" << s << ")=" << res << endl;
    }
    return 0;
}

思路解析：

1. 定义二叉树节点`TreeNode`，包括节点的值`val`和左右子树指针`left`、`right`。
2. 建立表达式树：根据先序遍历字符串的顺序，递归地建立表达式树。如果当前字符是操作符（`+`、`-`、`*`、`/`），则新建一个节点，其值为该操作符，节点的左右子树分别为递归建立的左右子树；如果当前字符是操作数（`0`~`9`），则新建一个节点，其值为该操作数，节点的左右子树均为`NULL`；如果当前字符是`#`，则返回`NULL`。
3. 计算表达式树的值：递归地计算左子树和右子树的值，根据当前节点的操作符，计算出当前子树的值。
4. 在主函数中读入先序遍历字符串，建立表达式树，计算表达式树的值并输出。

时间复杂度：$O(n)$，其中$n$为先序遍历字符串的长度。因为需要遍历整个字符串，建立表达式树和计算表达式树的值均需要$O(n)$的时间复杂度。