带括号的中序树遍历 [英] Inorder tree traversal with parentheses

问题描述

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

I've decided to try to teach myself how to program and am working my way through the Python version of "How to think like a computer scientist". Have tried to hold off asking questions about the exercises (since the whole point is to solve them myself) but this one has me stumped.

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

In chapter 20, after introducing Inorder traversal (working with the expression 1+2*3) and a function to traverse the tree and print each node, it then asks: "modify printTreeInorder so that it puts parentheses round every operator and pair of operands". I'm thus assuming the output should look like (1+(2)*3).

我一般都在为递归函数而苦恼，并且正在为此苦苦挣扎.我尝试在左右调用之前和之后插入括号，但没有用，现在我认为函数堆栈将有五个深 - 不知道我是如何得到两对括号的.

I struggle with recursive functions in general and am struggling with this. I tried inserting parentheses before and after the left and right calls, which didn't work, and now I'm thinking that the function stack will be five deep - don't see how I get to two pairs of parentheses out of that.

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

Feels like a cop-out asking, but can anyone put me on the right track with this?

谢谢，

比利.

推荐答案

在每个运算符和一对操作数周围加上括号".因此我假设输出应该看起来像 (1+(2)*3).

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

I don't think this should be the output. I think output should be: (1+(2*3))

对我来说，最简单的查看方法是通过面向对象的方法.

For me the easiest way to view this is through object oriented approach.

让抽象类 Node有抽象方法 GetExpressionString()和field令牌.

让 class Operand 从 Node 继承并实现 GetExpressionString() 使其返回 Token.(例如 '1' 或 '2' 或 '3').

Let class Operand inherit from Node and implement GetExpressionString() so that it returns Token. (for example '1' or '2' or '3').

让 class Operator 从 Node 继承，有 fields Left 和 Right 类型 Node 并实现 GetExpressionString() 使其返回 '(' + Left.GetExpressionString() + Token + Right.GetExpressionString() + ')'.例如，如果 Left = '2'、Right = '3' 和 Token = '*'，则结果为 '(2*3)'.

Let class Operator inherit from Node, has fields Left and Right of type Node and implement GetExpressionString() so that it returns '(' + Left.GetExpressionString() + Token + Right.GetExpressionString() + ')'. For example if Left = '2', Right = '3' and Token = '*', then result is '(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))'.

这篇关于带括号的中序树遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！