C++ 二进制表达式树 : How do I print an infix expression with appropriate parentheses?

Question

现在我有一个简单的打印算法，可以打印出完美的括号。问题是，括号并不总是必需的，我需要弄清楚如何在不需要时不打印它们。

我当前的功能:

void printIn(Node* t){

if(t!= NULL) {
    if(isleafNode(t))
        cout << t->element;
    else {      
        cout << "(";
        printIn(t->left);
        cout << t->data;
        printIn(t->right);
        cout << ")";
        }
  }

这里的问题是一些后缀表达式，比如 2 50 + 8 + 可以在中缀中打印为 2 + 50 + 8 instad of ((2 + 50) + 8))

这是一个后缀图表，用于固定它的外观。我的只是在整个外部添加圆括号，并且无论如何都添加圆括号。

4 50 6 + +           4 + ( 50 + 6 )
4 50 + 6 +           4 + 50 + 6
4 50 + 6 2 * +       4 + 50 + 6 * 2
4 50 6 + + 2 *       ( 4 + ( 50 + 6 ) ) * 2
a b + c d e + * *    ( a + b ) * ( c * ( d + e ) )

这是我的外观图表:

4 50 6 + +           ( 4 + ( 50 + 6 ))
4 50 + 6 +           ( ( 4 + 50 ) + 6)
4 50 + 6 2 * +       ( ( 4 + 50 ) + ( 6 * 2 ) )
4 50 6 + + 2 *       ( ( 4 + ( 50 + 6 ) ) * 2 )
a b + c d e + * *    ( ( a + b) * ( c * ( d + e ) ) )

如何修复我的算法以消除额外的括号？ p 请记住，我确实有一个 getPrecedence(string) 函数，它为高优先级(* 或/)返回 1，为低优先级(+ 或 -)返回 0

Answer 1

当以中缀形式打印表达式树时，您只需要在子表达式(即子表达式)周围打印括号，其中运算符的优先级低于主(即父)表达式的运算符。

例如，采用以下表达式树(采用后缀表示法)及其中缀形式。

4 5 6 + 7 * +        4 + (5 + 6) * 7

请注意，在 5 + 6 周围需要一个括号，因为子表达式 5 6 + 的运算符的优先级低于主表达式 5 6 + 7 * 的运算符，但子表达式 5 不需要括号6 + 7 * 因为运算符的优先级高于主表达式的运算符 4 5 6 + 7 * +

使用此信息可以很容易地修改问题中的算法以避免在不需要时使用括号。请注意，由于树中没有父指针，因此让父节点检查是否有任何子节点需要括号比让节点在自身周围放置括号更容易。