B
Ben Bacarisse
Kaz Kylheku said:
I missed that message. I saw your Lisp solution, bit not a C one.
Can you post a link, please? (I can't find it but Google groups is
unreliable or I may just be missing the obvious.)
Woah there! How can you conclude that no one knew how to solve it?
The reason I did not post a solution is that it seemed to be one of
those problems that is better solved in a high-level language. I saw
no reason to post another non-C solution and I don't much care for C
programs that are "translated down" for HLL solutions (though
sometimes that is the best we can do).
'Gene' has posted a C solution that emulates these high-level
structures in C. It has the expression backwards so it does not find
solutions to the problem as posted, but that is trivial to change. I
don't want to detract from that fine solution, but it not "natural" C.
Your fighting talk and my nagging feeling that there might be a simple
solution in C lead me the code posted below. I doubt is anything like
the best way to do this in C and, being un-commented, it is rather
cryptic but I am happy with it. It counts the possible trees using
mixed-base counter. These are mapped into tree shapes that can
evaluated (or printed) using a set of assignments for the values and
the operators.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <math.h>
#include <float.h>
typedef struct tree {
struct tree *arg[2];
} tree;
bool next_tree(int n, int *sum)
{
int p = 1;
while (p < n && sum[p] == n - p) p++;
if (p == n)
return false;
int d = sum[p] + 1;
while (p) sum[p--] = d;
return true;
}
tree *tree_make(int nops, int *counter, tree *nodes)
{
tree *stack[nops + 1], **sp = stack, *next_node = nodes;
*sp++ = 0;
for (int i = nops; i > 0; i--) {
*sp++ = 0;
int shift = counter[i-1] - counter;
while (shift--) {
tree *n = next_node++;
sp -= 2;
n->arg[0] = sp[0];
n->arg[1] = sp[1];
*sp++ = n;
}
}
return stack[0];
}
double tree_eval_aux(tree *e, double **args, char **ops)
{
if (e) {
double a = tree_eval_aux(e->arg[0], args, ops);
char op = *(*ops)++;
double b = tree_eval_aux(e->arg[1], args, ops);
switch (op) {
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
case '/': return a / b;
}
return NAN;
}
else return *(*args)++;
}
void tree_print_aux(tree *e, double **args, char **ops)
{
if (e) {
putchar('(');
tree_print_aux(e->arg[0], args, ops);
putchar(*(*ops)++);
tree_print_aux(e->arg[1], args, ops);
putchar(')');
}
else printf("%g", *(*args)++);
}
void tree_print(int nops, int *counter, double *args, char *ops)
{
tree nodes[nops];
tree_print_aux(tree_make(nops, counter, nodes), &args, &ops);
}
double tree_eval(int nops, int *counter, double *args, char *ops)
{
tree nodes[nops];
return tree_eval_aux(tree_make(nops, counter, nodes), &args, &ops);
}
double find_max_tree(int nops, double *args, char *ops, int *best)
{
int tree_number[nops + 1];
memset(tree_number, 0, sizeof tree_number);
tree_number[0] = nops;
double max = -DBL_MAX;
do {
double r = tree_eval(nops, tree_number, args, ops);
if (isfinite(r) && r > max) {
max = r;
memcpy(best, tree_number, sizeof tree_number);
}
} while (next_tree(nops, tree_number));
return max;
}
int main(void)
{
double values[] = {2, 2, 3, 3, 4, 4, 5, 5};
char operators[] = "/-/-/-/";
int n = strlen(operators);
int best[n + 1];
double max_value = find_max_tree(n, values, operators, best);
tree_print(n, best, values, operators);
printf(" = %g\n", max_value);
return 0;
}
)))