题目描述 编一个程序，读入先序遍历字符串，根据此字符串建立一棵二叉树（以指针方式存储），请注意的是，我们保证该树一定是表达式树（见教材5.2 5.8）。 例如下面的先序遍历字符串： + 13 # # * 5 # # 9 # # 运算符只可能是加减乘除，数值为小于等于100，各结点用空格分开，其中“#”代表空树。 建立起此二叉树以后，再按要求输出二叉树。 输入 输入由多组测试数据组成。 每组数据包含一行字符串，即表达式树的先序遍历序列，字符串长度大于0且不超过100。 输出 对于每组数据，输出一行，内容是该表达式树的全括号表达式，见示例。 样例输入 Copy + 13 # # * 5 # # 9 # # * + 13 # # 5 # # 9 # # 样例输出 Copy (13+(5*9)) ((13+5)*9)

下面是一份 C++ 代码实现：

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

typedef struct TreeNode {
    char data;
    TreeNode* left;
    TreeNode* right;
} TreeNode, *BiTree;

// 根据先序遍历序列建立二叉树
void CreateBiTree(BiTree& root) {
    char ch;
    cin >> ch;
    if (ch == '#') {
        root = NULL;
    } else {
        root = new TreeNode;
        root->data = ch;
        CreateBiTree(root->left);
        CreateBiTree(root->right);
    }
}

// 判断是否是运算符
bool IsOperator(char ch) {
    return ch == '+' || ch == '-' || ch == '*' || ch == '/';
}

// 计算表达式的值
int Calculate(int a, int b, char op) {
    switch (op) {
        case '+':
            return a + b;
        case '-':
            return a - b;
        case '*':
            return a * b;
        case '/':
            return a / b;
        default:
            return 0;
    }
}

// 将表达式树转换为全括号表达式
void Expression(BiTree root) {
    if (root == NULL) {
        return;
    }
    if (!IsOperator(root->data)) {
        cout << root->data;
    } else {
        cout << "(";
        Expression(root->left);
        cout << root->data;
        Expression(root->right);
        cout << ")";
    }
}

int main() {
    string s;
    while (cin >> s) {
        // 创建二叉树
        BiTree root = NULL;
        CreateBiTree(root);

        // 计算表达式值
        stack<int> stk;
        stack<char> ops;
        for (int i = s.size() - 1; i >= 0; i--) {
            char ch = s[i];
            if (!IsOperator(ch)) {
                stk.push(ch - '0');
            } else {
                int a = stk.top();
                stk.pop();
                int b = stk.top();
                stk.pop();
                stk.push(Calculate(a, b, ch));
            }
        }
        int result = stk.top();

        // 输出全括号表达式
        Expression(root);
        cout << "=" << result << endl;
    }
    return 0;
}

该代码首先根据先序遍历序列建立二叉树，然后利用栈来计算表达式的值，最后将表达式树转换为全括号表达式输出，并输出表达式的值。