1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
|
#include <stdio.h>
#include <stdlib.h>
enum operator {
OP_MULTIPLY,
OP_DIVIDE,
OP_ADD,
OP_SUBTRACT,
OP_IDENTITY /* marks leaves */
};
struct bnode {
int value;
enum operator operator;
struct bnode *left;
struct bnode *right;
};
char
op_lookup(enum operator op) {
switch (op) {
case OP_MULTIPLY: return '*';
case OP_DIVIDE: return '/';
case OP_ADD: return '+';
case OP_SUBTRACT: return '-';
default:
/* FIXME return this, error out somehow else? */
return '?';
}
}
double
evaluate_op(double left, enum operator op, double right) {
switch(op) {
case OP_MULTIPLY: return left * right;
case OP_DIVIDE: return (double)left / right;
case OP_ADD: return left + right;
case OP_SUBTRACT: return left - right;
default:
/* FIXME return nan */
return -100000;
}
}
double
evaluate(struct bnode* node) {
if (node->operator == OP_IDENTITY)
return node->value;
/* FIXME could/should NULL-check children
* Non-identity node should have two childre, but I might manage to
* screw it up somehow eh */
return evaluate_op(
evaluate(node->left),
node->operator,
evaluate(node->right));
}
void
generate_tree_perms(int depth, int decision_depth, struct bnode *node) {
if (depth == 0) {
node->operator = OP_IDENTITY;
node->value = rand()%20;
return ;
}
/* Hmmm */
struct bnode *children = NULL;
children = malloc(2*sizeof(children[0]));
children[0].left = NULL;
children[0].right = NULL;
children[1].left = NULL;
children[1].right = NULL;
node->left = &children[0];
node->right = &children[1];
node->operator = OP_ADD;
node->right->operator = OP_IDENTITY;
node->right->value = 999;
/* if (depth == 0 || decision_depth == 0) {
node->left->operator = OP_IDENTITY;
node->left->value = rand()%20;
node->right->operator = OP_IDENTITY;
node->right->value = rand()%20;
return;
}*/
if (depth == decision_depth)
generate_tree_perms(0, 0, node->right);
generate_tree_perms(depth-1, decision_depth, node->left);
}
void
dump_tree(struct bnode *node) {
if (node->operator == OP_IDENTITY) {
printf("%d", node->value);
return;
}
printf("(");
if (node->left != NULL)
dump_tree(node->left);
printf(" %c ", op_lookup(node->operator));
if (node->right != NULL)
dump_tree(node->right);
printf(")");
}
int
main(int argc, char **argv) {
/* look, ma! No hands! */
(void)argc;
(void)argv;
struct bnode a,b,c,d,e, o1,o2,o3,o4;
/* ((1+2)/(3*(4-5))) */
a.value = 1; a.operator = OP_IDENTITY; a.left = a.right = NULL;
b.value = 2; b.operator = OP_IDENTITY; b.left = b.right = NULL;
c.value = 3; c.operator = OP_IDENTITY; c.left = c.right = NULL;
d.value = 4; d.operator = OP_IDENTITY; d.left = d.right = NULL;
e.value = 5; e.operator = OP_IDENTITY; e.left = e.right = NULL;
o1.left = &a;
o1.right = &b;
o1.operator = OP_ADD;
o2.left = &d;
o2.right = &e;
o2.operator = OP_SUBTRACT;
o3.left = &c;
o3.right = &o2;
o3.operator = OP_MULTIPLY;
o4.left = &o1;
o4.right = &o3;
o4.operator = OP_DIVIDE;
dump_tree(&o4);
printf("\n = %f\n", evaluate(&o4));
struct bnode t;
t.operator = OP_ADD;
generate_tree_perms(3, 0, &t);
dump_tree(&t);
}
|
