Problems

请编写程序将表达式树按中缀表达式输出，并填加必要的括号，要求括号不能冗余，即保证正确运算次序所需的最少括号。如 a∗(b+c) 和 a+(b−c) 中的括号是必要的，而 a+(b∗c) 的括号则是冗余的。假定表达式树中的运算均为二元运算，只涉及加、减、乘、除运算。

输入格式:

输入为一行字符串，表示带空指针信息的表达式树先根序列，空指针信息用 # 表示，操作数为 a - z 的小写字母，运算符为+、-、$*$、/。

输出格式:

输出为一行字符串，表示填加必要括号后的中缀表达式。

输入样例1:

*a##+b##c##

输出样例1:

a*(b+c)

输入样例2:

+a##*b##c##

输出样例2:

a+b*c

Solutions

先序表达式建树

这个 so easy 咯。

输出表达式并添加合适的括号

法一？思路一

只是输出表达式的话中序遍历即可，要加上括号，那么我在中序遍历的时候判断一下，如果当前是运算符并且运算符优先级大于孩子节点优先级的话，就加上括号，很好，想法是可行的，就差代码实现了。
这是我当时的代码无修，写法有错误鸭！而且很混乱，该骂！居然还过了一个测试点！

void inOrder(node root) {
    if (root) {
        inOrder(root->lc);
        cout << root->data;
        bool fg = false;
        if (root->data >= 'a' && root->data <= 'z') {
        } else {
            if (root->lc && root->rc) {
                char lc = root->lc->data;
                char rc = root->rc->data;
                char sub;
                if (!(lc >= 'a' && lc <= 'z')) {
                    sub = lc;
                } else if (!(rc >= 'a' && rc <= 'z')) {
                    sub = rc;
                } else {
                    sub = 'a';
                }
                if (sub != 'a') {
                    if (mp[sub] <= mp[root->data]) {
                        fg = true;
                    }
                }
            }
        }
        if (fg) {
            cout << "(";
        }
        inOrder(root->rc);
        if (fg) {
            cout << ")";
        }
    }
}

思路一代码实现纠正

我自己又改了一遍，我觉得这样写是没有问题的。

void inOrder(node root) {
    if (root) {
        bool fgl = false, fgr = false;
        if (root->data == '*' || root->data == '/') {
            if (root->lc && (root->lc->data == '+' || root->lc->data == '-')) {
                fgl = true;
            }
            if (root->rc && (root->rc->data == '+' || root->rc->data == '-')) {
                fgr = true;
            }
        }
        if (fgl) cout << "(";
        inOrder(root->lc);
        if (fgl) cout << ")";
        cout << root->data;
        if (fgr) cout << "(";
        inOrder(root->rc);
        if (fgr) cout << ")";
    }
}

换一种有返回值的递归方式

这个想法来源于 ChatGPT，对于递归到底应该怎么写我还是不够清楚，或者说在紧急时刻我写不好。
==函数的作用即实现题目的要求，实现表达式树的带括号中缀表达式，参数是一棵树，返回值是一个字符串==，我们当然可以假设已经实现了左右子树的带括号序列，再来处理当前节点，在已经有左右字串的基础上加括号就很好理解了。

string to_infix(node root) {
    if (!root) return "";
    string str_left = to_infix(root->lc);
    string str_right = to_infix(root->rc);
    string value_str(1, root->data);
    if (root->data == '*' || root->data == '/') {
        if (root->lc && (root->lc->data == '+' || root->lc->data == '-')) {
            str_left = "(" + str_left + ")";
        }
        if (root->rc && (root->rc->data == '+' || root->rc->data == '-')) {
            str_right = "(" + str_right + ")";
        }
    }
    return str_left + value_str + str_right;
}