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

以下是实现该程序的 C++ 代码：

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

struct TreeNode {
    char val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char x) : val(x), left(nullptr), right(nullptr) {}
};

TreeNode* BuildTree(vector<char>& preorder) {
    if (preorder.empty()) {
        return nullptr;
    }
    char root_val = preorder[0];
    preorder.erase(preorder.begin());
    if (root_val == '#') {
        return nullptr;
    }
    TreeNode* root = new TreeNode(root_val);
    root->left = BuildTree(preorder);
    root->right = BuildTree(preorder);
    return root;
}

string TreeToString(TreeNode* root) {
    if (!root) {
        return "";
    }
    if (!root->left && !root->right) {
        return string(1, root->val);
    }
    string left_str = TreeToString(root->left);
    string right_str = TreeToString(root->right);
    if (root->val == '+' || root->val == '-' || root->val == '*' || root->val == '/') {
        return "(" + left_str + root->val + right_str + ")";
    }
    else {
        return left_str + root->val + right_str;
    }
}

int main() {
    string input;
    while (getline(cin, input)) {
        vector<char> preorder;
        for (char c : input) {
            if (c != ' ') {
                preorder.push_back(c);
            }
        }
        TreeNode* root = BuildTree(preorder);
        cout << TreeToString(root) << endl;
    }
    return 0;
}

该程序使用了递归的方法构建二叉树，并且根据题目要求输出了全括号表达式。在输入结束前，程序会一直读入数据并输出相应结果。