143 lines
4.3 KiB
C
143 lines
4.3 KiB
C
#include <time.h>
|
|
|
|
#define MAXINPUT (10) /* max numbers as input */
|
|
#define ALLOCSIZE (1024) /* # of elements to alloc */
|
|
|
|
#define MIN(a,b) (((a)<(b))?(a):(b))
|
|
#define MAX(a,b) (((a)>(b))?(a):(b))
|
|
#define ABS(a) (((a)<0)?-(a):(a))
|
|
|
|
#define NANOSEC 1000000000.0
|
|
#define MILLISEC 1000
|
|
|
|
typedef enum {
|
|
Nop='N',
|
|
Add='+',
|
|
Sub='-',
|
|
Mul='*',
|
|
Div='/',
|
|
End='\0' /* Only for "printf" */
|
|
} OPER;
|
|
|
|
typedef struct stack {
|
|
char name[80];
|
|
int size;
|
|
int last;
|
|
struct stack *next;
|
|
int stack[MAXINPUT+1];
|
|
} STACK;
|
|
|
|
#define TREE_UNDEF (-1) /* should not happen */
|
|
#define TREE_LEAF 0
|
|
#define TREE_NODE 1
|
|
#define TREE_LEFT 'L'
|
|
#define TREE_RIGHT 'R'
|
|
#define TREE_TOP 'T'
|
|
|
|
#define EMPTY -1
|
|
|
|
typedef struct node {
|
|
int type; /* TREE_LEAF or TREE_NODE */
|
|
int op; /* operator (nodes only) */
|
|
int val; /* value (leafs only) */
|
|
int eval; /* eval (unused) */
|
|
int prof; /* max left/right profs */
|
|
int left_prof;
|
|
struct node *left;
|
|
int right_prof;
|
|
struct node *right;
|
|
struct node *next; /* for transv walk and free nodes */
|
|
} NODE;
|
|
|
|
typedef struct tree {
|
|
char name[80];
|
|
NODE *head;
|
|
struct tree *next;
|
|
int nodes; /* number of nodes */
|
|
int leaves; /* number of leaves */
|
|
int depth; /* max depth */
|
|
} TREE;
|
|
|
|
typedef struct best {
|
|
int res;
|
|
int diff;
|
|
int nops;
|
|
char *oper;
|
|
NODE *root;
|
|
int *values;
|
|
struct timespec timer;
|
|
} BEST;
|
|
|
|
/* lceb.c */
|
|
extern void print_results();
|
|
|
|
/* signal.c */
|
|
extern void set_intr();
|
|
extern int stopped();
|
|
extern void set_alarm(int ms);
|
|
|
|
/* tree.c */
|
|
extern NODE *get_node();
|
|
extern int free_node(NODE *node);
|
|
extern int compare_nodes(NODE *node1, NODE *node2, int depth);
|
|
extern void print_node(NODE *node, char side, int depth, int details);
|
|
extern void print_tree(TREE *tree, int details);
|
|
extern void print_trees(int details);
|
|
extern TREE *new_tree(char *name);
|
|
extern NODE *dup_node(NODE *src);
|
|
//extern NODE *build_tree(int *desc, int size);
|
|
extern NODE *build_tree(char *desc, int size);
|
|
//extern void gen_tree(int *seq, int n, int nb1, int nb0);
|
|
extern void gen_reduced_trees(int n);
|
|
extern void gen_tree(char *seq, int n, int nb1, int nb0, int reduced);
|
|
extern TREE *nth_tree(int n);
|
|
extern int n_trees();
|
|
|
|
/* stack.c */
|
|
extern void print_stack(STACK *stack, int details);
|
|
extern void print_stacks();
|
|
//extern int keep_stack(STACK *stack);
|
|
//extern STACK *new_stack(int size, char *name, int keep);
|
|
extern STACK *new_stack(int size, char *name, int keep);
|
|
extern int *push_stack(STACK *stack, int val);
|
|
extern int *pop_stack(STACK *stack);
|
|
extern STACK *dup_stack(STACK *stack, char *name);
|
|
extern void swap_stack(int *elts, int i, int j);
|
|
extern int permute_stack(int *array, int n);
|
|
extern void gen_stacks(STACK *stack);
|
|
extern void mergesort_stack(int *array, int left, int right);
|
|
extern STACK *nth_stack(int n);
|
|
extern int n_stacks();
|
|
// extern STACKELT *set_op_stack(STACK *stack, int pos, OPER op);
|
|
// extern STACKELT *set_ops_stack(STACK *stack, char *ops);
|
|
|
|
/* oper.c */
|
|
extern void print_comb(int n);
|
|
extern void print_combs();
|
|
//extern unsigned n_combine(int nops, int len);
|
|
//extern char *combine(char *ops, int len, int n);
|
|
extern void gen_combinations(int nops);
|
|
extern int n_combs();
|
|
extern char *nth_comb(int n);
|
|
|
|
/* eval.c */
|
|
/* stack version */
|
|
//extern int eval_cell(STACKELT *pos);
|
|
//extern int eval_stack(STACK *stack);
|
|
/* tree version */
|
|
extern int eval_node(NODE *node, int depth, int *pvals, char *pops, int *ncalcs);
|
|
extern int get_totnodes();
|
|
extern int get_totleaves();
|
|
|
|
/* best.c */
|
|
extern void set_target (int n);
|
|
extern int check_best(int res, int nops, NODE *node, int *values, char *ops);
|
|
extern void print_best(NODE *node, int *values, char *pops, int depth);
|
|
extern void print_bests();
|
|
|
|
/* timer.c */
|
|
extern int sigint_received;
|
|
extern void start_timer();
|
|
extern void set_timer(struct timespec *timer);
|
|
extern double get_timer(struct timespec timer);
|