class Node
attr_accessor :left, :right
def initialize(v)
@value = v
end
def evaluate()
@left.evaluate().send(@value, @right.evaluate()) rescue @value
end
end
tree = Node.new(:-)
tree.right = Node.new(6)
tree.left = Node.new(:+)
tree.left.right = Node.new(7)
tree.left.left = Node.new(13)
puts tree.evaluate()
tree = Node.new(:join)
tree.right = Node.new(" and ")
tree.left = Node.new([1, "two", :three])
puts tree.evaluate()
#include <stdlib.h>
#include <stdio.h>
typedef enum element_type element_type;
enum element_type {
type_integer,
type_add,
type_subtract
};
typedef struct ast ast;
struct ast {
element_type type;
int element; /* only have ints; could be union of types */
ast *left;
ast *right;
};
static int stack[40];
static int pos;
void execute(ast *node)
{
int lhs, rhs;
/* Perform a postorder traversal */
if (node->left) execute(node->left);
if (node->right) execute(node->right);
/* All branches are executed, now execute this node*/
switch (node->type)
{
case type_integer :
printf("PUSH %d\n", node->element);
stack[pos++] = node->element;
break;
case type_add :
printf("ADD\n");
rhs = stack[–pos];
printf(" –> POP %d\n", rhs);
lhs = stack[–pos];
printf(" –> POP %d\n", lhs);
printf(" –> PUSH %d\n", lhs + rhs);
stack[pos++] = lhs + rhs;
break;
case type_subtract :
printf("SUB\n");
rhs = stack[–pos];
printf(" –> POP %d\n", rhs);
lhs = stack[–pos];
printf(" –> POP %d\n", lhs);
printf(" –> PUSH %d\n", lhs - rhs);
stack[pos++] = lhs - rhs;
break;
}
}
ast *create_node(element_type type, int value)
{
ast *node = malloc(sizeof (*node));
node->type = type;
node->element = value;
node->left = NULL;
node->right = NULL;
}
int main()
{
/* simulate some grammar being parsed */
ast *tree = create_node(type_subtract, 0);
tree->left = create_node(type_add, 0);
tree->left->left = create_node(type_integer, 13);
tree->left->right = create_node(type_integer, 7);
tree->right = create_node(type_integer, 6);
execute(tree);
printf("Stack[0] = %d\n", stack[0]);
return 0;
}
helpful to study up stacks and trees. After understanding reverse polish
notation (RPN), it makes much more sense to me. Now that I understand the
nature of computation on a virtual stack, I understand the order in which
the AST nodes are generated. I'm curious though how tree traversal would
work.
Assuming all we have to deal with so far is mathmatic expressions, consider
the following:
To build this tree, you could use a stack for basic operations:
This makes sense for both building the tree, and later traversal. I'm not sure
how you would start from the bottom of the tree, pre-order perhaps?
A token stream is easy for me to understand because it is just a linear list of tokens. I'm afraid I'm not certain about tree traversal. If you start at the root node
in this case '-' and start operations you would be going backwards.
Would it make more sense to start from the bottom up? Could someone provide a clear
example of how this is done? Thanks.