关于树和前缀（波兰语）符号？

我的MIPS Assembly类需要我将未知大小的表达式读入分析树。我从来没有对付树木，所以我这是怎么绕到存储值：关于树和前缀（波兰语）符号？

比方说，用户输入表达式1 + 3 - 4（每个操作数只能是数字1-9）

我最左边的子节点将是起点，包含2个数据

1. The operand 
2. Pointer to the next node (operator)

的我这是怎么构建的树。我会从操作数指向运算符，直到下一个运算符指向下一个运算符，直到没有更多值要读入为止。

我的下一个任务是递归遍历树并以infix/prefix/postfix表示法输出值。

考虑到我如何构建树，Infix遍历不成问题。

我被困在前缀上。首先，我不完全理解它。

当我输出我们的表达式（1 + 3 - 4）在前缀应该出来 - + 1 3 4？遵循在线示例我遇到了麻烦。

你也认为我的树构建正确吗？我的意思是，我无法前往当前节点的前一个节点，这意味着我总是必须从最左侧的子节点开始遍历，即使我的TA说这是一条路，本能地听起来不正确。

谢谢你的帮助。

来源

2009-02-07 VeePee

您解析树应该是这个样子：

 
     '-' 
     | 
    +---+---+ 
    |  | 
    '+'  '4' 
    | 
+---+---+ 
|  | 
'1'  '3'

每个节点有两个指针。一个给左边的孩子，一个给右边的孩子。使用递归遍历时，不需要指向父节点的指针。

下面是一些伪代码：

遍历中间符号：

void traverse(Node *node) { 
    if (node->leftChild != 0) { 
     traverse(node->leftChild); 
    } 

    print(node->value); 

    if (node->rightChild != 0) { 
     traverse(node->rightChild); 
    } 
}

遍历前缀符号：

void traverse(Node *node) { 
    print(node->value); 

    if (node->leftChild != 0) { 
     traverse(node->leftChild); 
    } 

    if (node->rightChild != 0) { 
     traverse(node->rightChild); 
    } 
}

遍历后缀符号：

void traverse(Node *node) { 
    if (node->leftChild != 0) { 
     traverse(node->leftChild); 
    } 

    if (node->rightChild != 0) { 
     traverse(node->rightChild); 
    } 

    print(node->value); 
}

您可以使用树的根节点调用traverse方法。

你Node数据结构需要三个成员：

struct Node { 
    char value; 
    Node *leftChild; 
    Node *rightChild; 
}

树的叶子将包含空指针leftChild和rightChild。

有时候可以用更高级的语言编写这些东西（不管你觉得舒服些什么）来理解问题，然后把这段代码“翻译”成汇编程序。我记得像这样在MIPS汇编程序中编写了一个blocks world模拟。

来源

2009-02-07 15:51:54 gclj5

一般而言，您应该构建一棵树，使得所有叶节点（没有子节点的）都是操作数，内部节点（其他所有节点）都是操作符。这应该是这样的，一个运算符节点的孩子是它的操作数，或者是它们自己的操作符。如果你可以用这种方式构造一棵树，形成各种符号（前缀，后缀，中缀）是相当简单的 - 你只需按照前序，后序和树的顺序遍历，这里有众所周知的算法。

据我所知，你不是构建一棵树，而是一个链表，而这不会为你服务。你有两个不同的实体 - 操作数和操作符 - 你必须以不同的方式对待它们。

来源

2009-02-07 15:43:34 sykora

这就是我正要给的答案。谢谢sykora！ – Niyaz 2009-02-07 15:46:39

我同意sykora说的。我想补充一点，在这种情况下你也可以使用堆栈。如果你的任务需要你专门使用一棵树，那么sykora的建议将效果最好。但是，对于简单表达式评估，堆栈可能更易于编程。

来源

2009-02-07 15:51:13 batbrat

这是编译的一般问题的一个实例，这是一个解决的问题。如果你在编译技术上做了谷歌搜索，你会发现有关你的问题的各种信息。

您的图书馆应该有一份Aho，Sethi和Ullman的编译器：原理，技术和工具。如果没有，请申请购买（这是该领域的标准工作）。它的第一部分应该可以帮到你。

Third edition link

来源

2009-02-07 15:59:35

关于树和前缀（波兰语）符号？

回答

相关问题