关于树和前缀(波兰语)表示法? [英] About Trees and Prefix (Polish) Notation?
问题描述
我的MIPS Assembly类要求我将未知大小的表达式读入Parse Tree.我从不需要处理树，所以这就是我如何存储值的方法:
假设用户输入了表达式1 + 3-4(每个操作数只能是1-9位数字)
我最左边的子节点将作为起点，并包含2条数据
1. The operand
2. Pointer to the next node (operator)
这就是我构造树的方式.我会从操作数到运算符指向下一个操作数再到下一个运算符，直到没有更多的值可读取.
我的下一个任务是递归遍历树并以infix/prefix/postfix表示法输出值.
考虑到我是如何构造树的，遍历中缀毫无问题.
我被卡在了前缀上.首先，我不太了解.
当我在前缀中输出表达式(1 + 3-4)时，它应该出来-+ 1 3 4吗?我在遵循在线示例时遇到了麻烦.
您还认为我的树构造正确吗?我的意思是，我无法从当前节点转到上一个节点，这意味着我总是必须从最左边的子节点开始遍历，即使我的助教说这是要走的路，本能地听起来也不正确. /p>
谢谢您的帮助.
您的解析树应如下所示:
'-'
|
+---+---+
| |
'+' '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汇编器中编写阻止世界仿真.
My MIPS Assembly class required me to read in an expression of unknown size into a Parse Tree. I've never had to deal with trees, so this is how I went around storing values:
Lets say the user entered the expression 1 + 3 - 4 (each operand could only be a digit 1-9)
My leftmost child node would be the starting point and contain 2 pieces of data
1. The operand
2. Pointer to the next node (operator)
This is how I constructed the tree. I would point from operand to operator to next operand to next operator until there were no more values left to be read in.
My next task was to traverse the tree recursively and output the values in infix/prefix/postfix notation.
Infix traversal was no problem considering how I constructed my tree.
I'm stuck on the prefix. Firstly, I don't fully understand it.
When I output our expression (1 + 3 - 4) in prefix should it come out - + 1 3 4? I'm having trouble following the online examples.
Also do you think my tree is constructed properly? I mean, I have no way to go to a previous node from the current node which means I always have to begin traversal from the leftmost child node which instinctively doesn't sound right even though my TA said that was the way to go.
Thank you for any help.
Your parse tree should look something like this:
'-'
|
+---+---+
| |
'+' '4'
|
+---+---+
| |
'1' '3'
Each node has two pointers. One to its left child and one to its right child. There is no need for pointers to parent nodes, when using recursive traversal.
Here's some pseudocode:
Traversal for infix notation:
void traverse(Node *node) {
if (node->leftChild != 0) {
traverse(node->leftChild);
}
print(node->value);
if (node->rightChild != 0) {
traverse(node->rightChild);
}
}
Traversal for prefix notation:
void traverse(Node *node) {
print(node->value);
if (node->leftChild != 0) {
traverse(node->leftChild);
}
if (node->rightChild != 0) {
traverse(node->rightChild);
}
}
Traversal for postfix notation:
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.
这篇关于关于树和前缀(波兰语)表示法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
