tree - 带括号的中序树遍历

Question

我决定尝试自学如何编程，并正在学习 Python 版本的“如何像计算机科学家一样思考”。我试图推迟询问有关练习的问题(因为重点是我自己解决它们)，但这一个让我难住了。

在第 20 章中，在介绍了中序遍历(使用表达式 1+2*3)和遍历树并打印每个节点的函数之后，它会询问:“修改 printTreeInorder，以便它在每个运算符周围加上括号，并且操作数对”。因此，我假设输出应类似于 (1+(2)*3)。

我一般都在递归函数上挣扎，并且正在为此挣扎。我尝试在左右调用之前和之后插入括号，但这不起作用，现在我认为函数堆栈将是五个深 - 不明白我如何从中得到两对括号。

感觉像是在逃避问题，但有人能让我走上正轨吗？

谢谢

比利。

Answer 1

puts parentheses round every operator and pair of operands". I'm thus assuming the output should look like (1+(2)*3).

我认为这不应该是输出。我认为输出应该是: (1+(2*3))

对我来说，查看此问题的最简单方法是通过面向对象的方法。

让抽象类 Node有抽象方法 GetExpressionString()和字段 token 。

让类 Operand继承自Node并实现GetExpressionString()，以便它返回Token 。 (例如 '1' 或 '2' 或 '3')。

让类 Operator继承自Node，具有字段 Left和Right 类型为 Node 并实现 GetExpressionString()，以便返回 '(' + Left.GetExpressionString() + Token + Right。 GetExpressionString() + ')'。例如，如果 Left = '2'、Right = '3' 和 Token = '*'，则结果为 '( 2*3)'。

然后对于

expression = new Operator(
               Token='+',
               Left=new Operand(Token='1'),
               Right=new Operator(
                       Token='*',
                       Left=new Operand(Token='2'),
                       Right=new Operand(Token='3')))

调用expression.GetExpressionString()会返回'(1+(2*3))'。