138 lines
3.7 KiB
C
138 lines
3.7 KiB
C
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include "lceb.h"
|
|
|
|
|
|
static int nodes_calc; /* total nodes evaluated */
|
|
static int leaves_calc; /* total leaves evaluated */
|
|
int firstonly=0;
|
|
|
|
int eval_node(node, depth, pvals, pops, ncalcs)
|
|
NODE *node;
|
|
int depth;
|
|
int *pvals;
|
|
char *pops;
|
|
int *ncalcs;
|
|
{
|
|
static int *vals, *val_zero;
|
|
static char *ops, *ops_zero;
|
|
static int totcalc;
|
|
int val1, val2, op, res=-1, lcalcs, rcalcs, diff;
|
|
|
|
if (depth == 0) {
|
|
val_zero=vals=pvals;
|
|
ops_zero=ops=pops;
|
|
totcalc=0;
|
|
}
|
|
# ifdef DEBUG_EVAL
|
|
for (i=0; i<=depth; ++i)
|
|
printf(" ");
|
|
printf("eval : depth=%d : ncalcs=%d ", depth, *ncalcs);
|
|
if (node->type == TREE_NODE) {
|
|
printf("node(%c)\n", *ops);
|
|
print_node(node, TREE_TOP, 0, 0);
|
|
|
|
} else {
|
|
printf("leaf(%d)\n", *vals);
|
|
}
|
|
# endif
|
|
if (node->type == TREE_LEAF) {
|
|
leaves_calc++;
|
|
node->val=*vals;
|
|
res=*vals;
|
|
vals++;
|
|
*ncalcs=0;
|
|
//printf("leaf=%d\n", res);
|
|
} else {
|
|
nodes_calc++;
|
|
op=*ops;
|
|
node->op=*ops;
|
|
ops++;
|
|
totcalc++;
|
|
val1=eval_node(node->left, depth+1, pvals, ops, &lcalcs);
|
|
if (val1 <= 0)
|
|
return val1;
|
|
val2=eval_node(node->right, depth+1, pvals, ops, &rcalcs);
|
|
if (val2 <= 0)
|
|
return val2;
|
|
switch (op) {
|
|
case Add:
|
|
res=val1+val2;
|
|
break;
|
|
case Mul:
|
|
if (val1 > 1 && val2 > 1) /* we avoid "x*1" */
|
|
res=val1*val2;
|
|
break;
|
|
case Sub:
|
|
if (val1<val2) {
|
|
NODE *tmp=node->left;
|
|
# ifdef DEBUG_EVAL2
|
|
printf("eval: Sub: swapping val1=%d val2=%d\n", val1, val2);
|
|
# endif
|
|
node->left=node->right;
|
|
node->right=tmp;
|
|
}
|
|
if (val1 != val2) {
|
|
res=val1-val2;
|
|
}
|
|
if (res == val2) /* already found in subtree */
|
|
res=-1;
|
|
break;
|
|
case Div:
|
|
if (val1<val2) {
|
|
NODE *tmp=node->left;
|
|
# ifdef DEBUG_EVAL2
|
|
printf("eval: Div: swapping val1=%d val2=%d\n", val1, val2);
|
|
# endif
|
|
node->left=node->right;
|
|
node->right=tmp;
|
|
}
|
|
if (val2 != 1 && (val1 % val2 == 0))
|
|
res=val1/val2;
|
|
if (res == val2) /* already found in subtree */
|
|
res=-1;
|
|
break;
|
|
case Nop:
|
|
case End:
|
|
fprintf(stderr, "Fatal: bad op [%d] in eval\n", op);
|
|
exit(1);
|
|
break;
|
|
}
|
|
*ncalcs=lcalcs+rcalcs+1;
|
|
}
|
|
if (res > 0) {
|
|
diff=check_best(res, *ncalcs, node, val_zero, ops_zero);
|
|
//printf("eval=%d firstonly=%d\n", eval, firstonly);
|
|
if (diff == 0) { /* exact result, we stop here */
|
|
# ifdef DEBUG_EVAL3
|
|
printf("EXACT eval=%d\n", diff);
|
|
# endif
|
|
if (firstonly) {
|
|
print_results();
|
|
exit(0);
|
|
}
|
|
res=0;
|
|
}
|
|
}
|
|
if (sigint_received) {
|
|
print_results();
|
|
exit(1);
|
|
}
|
|
|
|
# ifdef DEBUG_EVAL
|
|
for (i=0; i<=depth; ++i)
|
|
printf(" ");
|
|
printf("res=%d\n", res);
|
|
# endif
|
|
return res;
|
|
}
|
|
|
|
int get_totnodes()
|
|
{
|
|
return nodes_calc;
|
|
}
|
|
int get_totleaves()
|
|
{
|
|
return leaves_calc;
|
|
}
|