4

我的 MIPS 汇编课程要求我将未知大小的表达式读入解析树。我从来不用处理树，所以这就是我存储值的方式：

假设用户输入了表达式 1 + 3 - 4（每个操作数只能是数字 1-9）

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

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

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

我的下一个任务是递归地遍历树并以中缀/前缀/后缀表示法输出值。

考虑到我是如何构建树的，中缀遍历没有问题。

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

当我在前缀中输出我们的表达式 (1 + 3 - 4) 时，它应该出现 - + 1 3 4 吗？我无法按照在线示例进行操作。

您还认为我的树构造正确吗？我的意思是，我无法从当前节点转到前一个节点，这意味着我总是必须从最左边的子节点开始遍历，尽管我的 TA 说这是要走的路，但本能地听起来并不正确。

感谢您的任何帮助。

4

4 回答 4

4

您的解析树应如下所示：

        '-'
         |
     +---+---+
     | |
    '+' '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);
}

You would call the traverse method with the root node of your tree.

Your Node data structure would need three members:

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

The leaves of the tree would contain null pointers for leftChild and rightChild.

Sometimes it helps to write this stuff in a higher level language (whatever you feel comfortable with) to understand the problem and then "translate" this code to assembler. I remember programming a blocks world simulation in MIPS assembler like this.

于 2009-02-07T15:51:54.227 回答
3

一般来说，您应该以这样一种方式构造一棵树，即所有叶节点（没有子节点的节点）都是操作数，而内部节点（其他所有节点）都是运算符。这应该使得操作符节点的子节点是它的操作数，或者本身就是具有操作数的操作符。如果你可以用这种方式构造一棵树，那么形成各种符号（前缀、后缀、中缀）就相当简单——你只需遵循树的前序、后序和中序遍历，这有众所周知的算法。

据我所知，您不是在构建树，而是在构建链表，这对您没有好处。你有 2 个不同的实体——操作数和运算符——你必须区别对待它们。

于 2009-02-07T15:43:34.117 回答
0

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

于 2009-02-07T15:51:13.383 回答
0

This is an instance of the general problem of compiling, which is a solved problem. If you do a google on compiling techniques, you will find out all kinds of information relating to your problem.

Your library should have a copy of Compilers: Principles, Techniques, and Tools by Aho, Sethi, and Ullman. If it doesn't have it, request it for purchase(it's the Standard Work in the field). The first part of it should help you.

Third edition link

于 2009-02-07T15:59:35.973 回答