[calc.git] / parser.c

#include <malloc.h>
#include <math.h>
#include <stdlib.h>

#include "debug.h"
#include "fdprintf.h"

#include "parser.h"

/* compare codes */

int codecmp (char *ref, char *str)
{
    int sig;

    while (*ref != '\0') {
        if (*ref == '\t') {
             sig = (*str == '.') ? -1 : ((*str >= '0') && (*str <= '9'));
        } else {
            sig = *str - *ref;
        }
        if (sig != 0) {
            return (sig > 0) ? 1 : -1;
        }
        str++;
        ref++;
    }

    return 0;
}

/* allocate new element */

element_t *newelement (func_t function, int nbops, int prio)
{
    element_t *new = (element_t *) calloc (1, sizeof (element_t));
    if (new == NULL) {
        VERBOSE (ERROR, fdprintf (stdfderr, "can't allocate memory\n"));
        return NULL;
    }
    new->func = function;
    new->nbops = nbops;
    new->prio = prio;

    return new;
}

/* functions */

#define NB_OPERATORS 5

keyword_t operators[NB_OPERATORS] = {
    { "+\t", Add, 2, 1, 1},
    { "-\t", Sub, 2, 1, 1},
    { "*",   Mul, 2, 1, 2},
    { "/",   Div, 2, 1, 2},
    { "^",   Pow, 2, 1, 3}
};

#define NB_FUNCTIONS 7
keyword_t functions[NB_FUNCTIONS] = {
    { "sqrt", Sqr, 1, 4, 4},
    { "pow",  Pow, 2, 3, 4},
    { "cos",  Cos, 1, 3, 4},
    { "sin",  Sin, 1, 3, 4},
    { "atan", Atn, 1, 4, 4},
    { "exp",  Exp, 1, 3, 4},
    { "log",  Log, 1, 3, 4}
};

/* parser function */

element_t *parser (char *str, char **next, int prio)
{
    element_t *root = NULL;
    int i;

    VERBOSE (DEBUG, PRINTOUT ("Starting parsing\n"));

    /* main loop */
    while (*str != '\0') {
        int found = 0;
        element_t *new = NULL;
        VERBOSE (INFO, PRINTOUT ("Processing: %s\n", str));

        /* skip spaces and tabs */

        if ((*str == ' ') || (*str == '\t')) {
            str++;
            continue;
        }

        /* check for open bracket */

        if (*str == '(') {
            VERBOSE (DEBUG, PRINTOUT ("start processing bracket\n"));
            if (root) {
                do {
                    found = 0;
                    new = parser (str + 1, &str, 0);
                    if (new == ERROR_OP) {
                        return ERROR_OP;
                    }
                    for (i = 0; i < root->nbops; i++) {
                        if (root->ops[i] == NULL) {
                            root->ops[i] = new;
                            found = 1;
                            break;
                        }
                    }
                    if (!found) {
                        return ERROR_OP;
                    }
                } while (*str == ',');
            } else {
                root = newelement (Val, 1, 4);
                if (root == NULL) {
                    return ERROR_OP;
                }
                new = parser (str + 1, &str, 0);
                if ((new == ERROR_OP) || (*str == ',')) {
                    return ERROR_OP;
                }
                root->ops[0] = new;
            }
            str++;
            VERBOSE (DEBUG, PRINTOUT ("stop processing bracket\n"));
            continue;
        }

        /* check for closing bracket or koma */

        if ((*str == ')') || (*str == ',')) {
            if (next != NULL) {
                *next = str;
            }
            return root;
        }

        /* look for operators */

        for (i = 0; i < NB_OPERATORS; i++) {
            keyword_t *operator = operators + i;
            if (codecmp (operator->keyword, str) == 0) {
                VERBOSE (DEBUG, PRINTOUT ("start processing operator\n"));
                if (root) {
                    if ((prio) && (prio > operator->prio)) {
                        VERBOSE (DEBUG, PRINTOUT ("stop processing operator because operator priority\n"));
                        *next = str;
                        return root;
                    }
                    str += operator->offset;
                    VERBOSE (INFO, PRINTOUT ("Oper: %d\n", operator->func));
                    new = newelement (operator->func, operator->nbops, operator->prio);
                    if (new == NULL) {
                        return ERROR_OP;
                    }
                    new->ops[0] = root;
                    new->ops[1] = parser (str, &str, new->prio);
                    if (new->ops[1] == ERROR_OP) {
                        return ERROR_OP;
                    }
                    root = newelement (Val, 1, 4);
                    if (root == ERROR_OP) {
                        return ERROR_OP;
                    }
                    root->ops[0] = new;
                } else {
                    return ERROR_OP;
                }
                found = 1;
                VERBOSE (DEBUG, PRINTOUT ("stop processing operator\n"));
                break;
            }
        }
        if (found) {
            continue;
        }

        /* look for functions */

        for (i = 0; i < NB_FUNCTIONS; i++) {
            keyword_t *function = functions + i;
            if (codecmp (function->keyword, str) == 0) {
                VERBOSE (DEBUG, PRINTOUT ("start processing function\n"));
                if (root == NULL) {
                    VERBOSE (INFO, PRINTOUT ("Func: %d\n", function->func));
                    new = newelement (function->func, function->nbops, function->prio);
                    if (new == NULL) {
                        return ERROR_OP;
                    }
                    root = new;
                 } else {
                    return ERROR_OP;
                }
                str += function->offset;
                found = 1;
                VERBOSE (DEBUG, PRINTOUT ("stop processing function\n"));
                break;
            }
        }
        if (found) {
            continue;
        }

        /* look for number */

        if (((*str >= '0') && (*str <= '9')) ||
            (*str == '.') || (*str == '+') || (*str == '-')) {
            VERBOSE (DEBUG, PRINTOUT ("start processing value\n"));
            char *pt;
            float value = strtof (str, &pt);
            VERBOSE (INFO, PRINTOUT ("Value: %f\n", value));
            if (str != pt) {
                new = newelement (Val, 1, 4);
                if (new == NULL) {
                    return ERROR_OP;
                }
                new->value = value;
                if (root == NULL) {
                    root = new;
                } else if (root->func == Val) {
                    if ((*str == '+') || (*str == '-')) {
                        element_t *add = newelement (Add, 2, 1);
                        if (add == NULL) {
                            return ERROR_OP;
                        }
                        add->ops[0] = root;
                        add->ops[1] = new;
                        root = add;
                    } else {
                        return ERROR_OP;
                    }
                } else {
                    return ERROR_OP;
                }
                str = pt;
                found = 1;
            }
            VERBOSE (DEBUG, PRINTOUT ("stop processing value\n"));
        }

        /* error */

        if (!found) {
            return ERROR_OP;
        }

    }

    if (next != NULL) {
        *next = str;
    }
    return root;
}

/* print element tree */

void print_element (element_t *root, int level)
{
    char *func = NULL;
    int i;

    if ((root == NULL) || (root == ERROR_OP)) {
        return;
    }

    for (i = 0; i < level; i++) {
        PRINTOUT (" ");
    }

    switch (root->func) {
    case Val: func = "Value"; break;
    case Add: func = "Addition"; break;
    case Sub: func = "Subtraction"; break;
    case Mul: func = "Multiplication"; break;
    case Div: func = "Division"; break;
    case Pow: func = "Power"; break;
    case Sqr: func = "Square Root"; break;
    case Cos: func = "Cosine"; break;
    case Sin: func = "Sine"; break;
    case Atn: func = "Arc Tangent"; break;
    case Log: func = "Logarithm"; break;
    case Exp: func = "Exponantial"; break;
    }

    PRINTOUT ("Function: %s\n", func);

    if ((root->func == Val) && (root->ops[0] == NULL)) {
        for (i = 0; i < level; i++) {
            PRINTOUT (" ");
        }
        PRINTOUT ("value: %f\n", root->value);
    } else {
        for (i = 0; i < root->nbops; i++) {
            print_element (root->ops[i], level + 1);
        }
    }
}

/* evaluate element tree */

double evaluate_element (element_t *root)
{
    double op0 = 0, op1 = 0;

    if ((root == NULL) || (root == ERROR_OP)) {
        VERBOSE (WARNING, PRINTOUT ("error while evaluating\n"));
        return 0;
    }

    switch (root->func) {
    case Val:
        if (root->ops[0]) {
            return evaluate_element (root->ops[0]);
        } else {
            return root->value;
        }
        break;
    case Add:
    case Sub:
    case Mul:
    case Div:
    case Pow:
        if (root->ops[1]) {
            op1 = evaluate_element (root->ops[1]);
        } else {
            VERBOSE (WARNING, PRINTOUT ("error while evaluating (op[1])\n"));
            return 0;
        }
        /* fallthrough */
    case Sqr:
    case Cos:
    case Sin:
    case Atn:
    case Log:
    case Exp:
        if (root->ops[0]) {
            op0 = evaluate_element (root->ops[0]);
        } else {
            VERBOSE (WARNING, PRINTOUT ("error while evaluating (op[0])\n"));
            return 0;
        }
    }

    switch (root->func) {
    case Add: return op0 + op1;
    case Sub: return op0 - op1;
    case Mul: return op0 * op1;
    case Div: return op0 / op1;
    case Pow: return pow (op0, op1);
    case Sqr: return sqrt (op0);
    case Cos: return cos (op0);
    case Sin: return sin (op0);
    case Atn: return atan (op0);
    case Log: return log (op0);
    case Exp: return exp (op0);
    default: break;
    }

    return 0;
}

/* vim: set ts=4 sw=4 et: */
Commit	Line	Data
bc97a989	1	#include <malloc.h>
f2927108	2	#include <math.h>
bc97a989 LM	3	#include <stdlib.h>
	4
	5	#include "debug.h"
	6	#include "fdprintf.h"
	7
	8	#include "parser.h"
	9
	10	/* compare codes */
	11
	12	int codecmp (char ref, char str)
	13	{
	14	int sig;
	15
	16	while (*ref != '\0') {
0b9cc9b0 LM	17	if (*ref == '\t') {
	18	sig = (str == '.') ? -1 : ((str >= '0') && (*str <= '9'));
	19	} else {
	20	sig = str - ref;
	21	}
bc97a989 LM	22	if (sig != 0) {
	23	return (sig > 0) ? 1 : -1;
	24	}
0b9cc9b0 LM	25	str++;
0b9cc9b0 LM	26	ref++;
bc97a989 LM	27	}
	28
	29	return 0;
	30	}
	31
	32	/* allocate new element */
	33
11cda8d7	34	element_t *newelement (func_t function, int nbops, int prio)
bc97a989 LM	35	{
	36	element_t new = (element_t ) calloc (1, sizeof (element_t));
	37	if (new == NULL) {
	38	VERBOSE (ERROR, fdprintf (stdfderr, "can't allocate memory\n"));
	39	return NULL;
	40	}
	41	new->func = function;
	42	new->nbops = nbops;
11cda8d7	43	new->prio = prio;
bc97a989 LM	44
	45	return new;
	46	}
	47
	48	/* functions */
	49
0b9cc9b0	50	#define NB_OPERATORS 5
bc97a989 LM	51
bc97a989 LM	52	keyword_t operators[NB_OPERATORS] = {
11cda8d7 LM	53	{ "+\t", Add, 2, 1, 1},
	54	{ "-\t", Sub, 2, 1, 1},
	55	{ "*", Mul, 2, 1, 2},
	56	{ "/", Div, 2, 1, 2},
	57	{ "^", Pow, 2, 1, 3}
bc97a989 LM	58	};
	59
	60	#define NB_FUNCTIONS 7
	61	keyword_t functions[NB_FUNCTIONS] = {
11cda8d7 LM	62	{ "sqrt", Sqr, 1, 4, 4},
	63	{ "pow", Pow, 2, 3, 4},
	64	{ "cos", Cos, 1, 3, 4},
	65	{ "sin", Sin, 1, 3, 4},
	66	{ "atan", Atn, 1, 4, 4},
	67	{ "exp", Exp, 1, 3, 4},
	68	{ "log", Log, 1, 3, 4}
bc97a989 LM	69	};
	70
	71	/* parser function */
	72
ef37d966	73	element_t parser (char str, char **next, int prio)
0b489a77	74	{
bc97a989	75	element_t *root = NULL;
85b4a72c	76	int i;
bc97a989	77
49223129 LM	78	VERBOSE (DEBUG, PRINTOUT ("Starting parsing\n"));
49223129 LM	79
bc97a989 LM	80	/* main loop */
	81	while (*str != '\0') {
	82	int found = 0;
	83	element_t *new = NULL;
49223129	84	VERBOSE (INFO, PRINTOUT ("Processing: %s\n", str));
bc97a989 LM	85
	86	/* skip spaces and tabs */
	87
	88	if ((str == ' ') \|\| (str == '\t')) {
	89	str++;
	90	continue;
	91	}
	92
85b4a72c	93	/* check for open bracket */
0b489a77	94
0b489a77	95	if (*str == '(') {
49223129	96	VERBOSE (DEBUG, PRINTOUT ("start processing bracket\n"));
0b489a77	97	if (root) {
85b4a72c LM	98	do {
85b4a72c LM	99	found = 0;
ef37d966	100	new = parser (str + 1, &str, 0);
85b4a72c LM	101	if (new == ERROR_OP) {
	102	return ERROR_OP;
	103	}
	104	for (i = 0; i < root->nbops; i++) {
	105	if (root->ops[i] == NULL) {
0b489a77 LM	106	root->ops[i] = new;
	107	found = 1;
	108	break;
	109	}
	110	}
85b4a72c LM	111	if (!found) {
	112	return ERROR_OP;
	113	}
	114	} while (*str == ',');
	115	} else {
11cda8d7	116	root = newelement (Val, 1, 4);
85b4a72c	117	if (root == NULL) {
0b489a77 LM	118	return ERROR_OP;
0b489a77 LM	119	}
ef37d966	120	new = parser (str + 1, &str, 0);
85b4a72c	121	if ((new == ERROR_OP) \|\| (*str == ',')) {
efdfb543 LM	122	return ERROR_OP;
efdfb543 LM	123	}
85b4a72c	124	root->ops[0] = new;
0b489a77	125	}
85b4a72c	126	str++;
49223129	127	VERBOSE (DEBUG, PRINTOUT ("stop processing bracket\n"));
efdfb543	128	continue;
49223129	129	}
85b4a72c LM	130
	131	/* check for closing bracket or koma */
	132
	133	if ((str == ')') \|\| (str == ',')) {
49223129	134	if (next != NULL) {
85b4a72c	135	*next = str;
49223129 LM	136	}
49223129 LM	137	return root;
0b489a77 LM	138	}
0b489a77 LM	139
bc97a989 LM	140	/* look for operators */
	141
	142	for (i = 0; i < NB_OPERATORS; i++) {
	143	keyword_t *operator = operators + i;
	144	if (codecmp (operator->keyword, str) == 0) {
49223129	145	VERBOSE (DEBUG, PRINTOUT ("start processing operator\n"));
11cda8d7	146	if (root) {
ef37d966 LM	147	if ((prio) && (prio > operator->prio)) {
	148	VERBOSE (DEBUG, PRINTOUT ("stop processing operator because operator priority\n"));
	149	*next = str;
	150	return root;
	151	}
	152	str += operator->offset;
49223129	153	VERBOSE (INFO, PRINTOUT ("Oper: %d\n", operator->func));
11cda8d7	154	new = newelement (operator->func, operator->nbops, operator->prio);
bc97a989	155	if (new == NULL) {
0b489a77	156	return ERROR_OP;
bc97a989	157	}
ef37d966 LM	158	new->ops[0] = root;
	159	new->ops[1] = parser (str, &str, new->prio);
	160	if (new->ops[1] == ERROR_OP) {
49223129 LM	161	return ERROR_OP;
49223129 LM	162	}
ef37d966 LM	163	root = newelement (Val, 1, 4);
	164	if (root == ERROR_OP) {
	165	return ERROR_OP;
11cda8d7	166	}
ef37d966	167	root->ops[0] = new;
49223129	168	} else {
0b489a77	169	return ERROR_OP;
bc97a989	170	}
bc97a989	171	found = 1;
49223129	172	VERBOSE (DEBUG, PRINTOUT ("stop processing operator\n"));
bc97a989 LM	173	break;
	174	}
	175	}
	176	if (found) {
bc97a989 LM	177	continue;
bc97a989 LM	178	}
49223129	179
bc97a989 LM	180	/* look for functions */
	181
	182	for (i = 0; i < NB_FUNCTIONS; i++) {
	183	keyword_t *function = functions + i;
	184	if (codecmp (function->keyword, str) == 0) {
49223129	185	VERBOSE (DEBUG, PRINTOUT ("start processing function\n"));
bc97a989	186	if (root == NULL) {
49223129	187	VERBOSE (INFO, PRINTOUT ("Func: %d\n", function->func));
11cda8d7	188	new = newelement (function->func, function->nbops, function->prio);
bc97a989	189	if (new == NULL) {
0b489a77	190	return ERROR_OP;
bc97a989 LM	191	}
	192	root = new;
	193	} else {
0b489a77	194	return ERROR_OP;
bc97a989 LM	195	}
	196	str += function->offset;
	197	found = 1;
49223129	198	VERBOSE (DEBUG, PRINTOUT ("stop processing function\n"));
bc97a989 LM	199	break;
	200	}
	201	}
	202	if (found) {
bc97a989 LM	203	continue;
	204	}
	205
bc97a989 LM	206	/* look for number */
bc97a989 LM	207
0b9cc9b0 LM	208	if (((str >= '0') && (str <= '9')) \|\|
0b9cc9b0 LM	209	(str == '.') \|\| (str == '+') \|\| (*str == '-')) {
49223129	210	VERBOSE (DEBUG, PRINTOUT ("start processing value\n"));
bc97a989 LM	211	char *pt;
bc97a989 LM	212	float value = strtof (str, &pt);
49223129	213	VERBOSE (INFO, PRINTOUT ("Value: %f\n", value));
bc97a989	214	if (str != pt) {
11cda8d7	215	new = newelement (Val, 1, 4);
bc97a989	216	if (new == NULL) {
0b489a77	217	return ERROR_OP;
bc97a989	218	}
49223129	219	new->value = value;
bc97a989 LM	220	if (root == NULL) {
bc97a989 LM	221	root = new;
0b9cc9b0 LM	222	} else if (root->func == Val) {
0b9cc9b0 LM	223	if ((str == '+') \|\| (str == '-')) {
11cda8d7	224	element_t *add = newelement (Add, 2, 1);
0b9cc9b0	225	if (add == NULL) {
0b489a77 LM	226	return ERROR_OP;
0b489a77 LM	227	}
0b9cc9b0 LM	228	add->ops[0] = root;
	229	add->ops[1] = new;
	230	root = add;
	231	} else {
0b489a77	232	return ERROR_OP;
bc97a989	233	}
0b9cc9b0 LM	234	} else {
0b9cc9b0 LM	235	return ERROR_OP;
bc97a989 LM	236	}
	237	str = pt;
	238	found = 1;
	239	}
49223129	240	VERBOSE (DEBUG, PRINTOUT ("stop processing value\n"));
bc97a989 LM	241	}
	242
	243	/* error */
	244
	245	if (!found) {
0b489a77	246	return ERROR_OP;
bc97a989 LM	247	}
	248
	249	}
	250
49223129 LM	251	if (next != NULL) {
	252	*next = str;
	253	}
bc97a989 LM	254	return root;
	255	}
	256
	257	/* print element tree */
	258
	259	void print_element (element_t *root, int level)
	260	{
	261	char *func = NULL;
	262	int i;
	263
49223129	264	if ((root == NULL) \|\| (root == ERROR_OP)) {
bc97a989	265	return;
49223129 LM	266	}
49223129 LM	267
bc97a989 LM	268	for (i = 0; i < level; i++) {
	269	PRINTOUT (" ");
	270	}
	271
	272	switch (root->func) {
	273	case Val: func = "Value"; break;
	274	case Add: func = "Addition"; break;
	275	case Sub: func = "Subtraction"; break;
	276	case Mul: func = "Multiplication"; break;
	277	case Div: func = "Division"; break;
	278	case Pow: func = "Power"; break;
	279	case Sqr: func = "Square Root"; break;
	280	case Cos: func = "Cosine"; break;
	281	case Sin: func = "Sine"; break;
	282	case Atn: func = "Arc Tangent"; break;
	283	case Log: func = "Logarithm"; break;
	284	case Exp: func = "Exponantial"; break;
	285	}
	286
	287	PRINTOUT ("Function: %s\n", func);
	288
85b4a72c	289	if ((root->func == Val) && (root->ops[0] == NULL)) {
bc97a989 LM	290	for (i = 0; i < level; i++) {
	291	PRINTOUT (" ");
	292	}
	293	PRINTOUT ("value: %f\n", root->value);
	294	} else {
	295	for (i = 0; i < root->nbops; i++) {
	296	print_element (root->ops[i], level + 1);
	297	}
	298	}
	299	}
	300
f2927108 LM	301	/* evaluate element tree */
	302
	303	double evaluate_element (element_t *root)
	304	{
	305	double op0 = 0, op1 = 0;
	306
	307	if ((root == NULL) \|\| (root == ERROR_OP)) {
	308	VERBOSE (WARNING, PRINTOUT ("error while evaluating\n"));
	309	return 0;
	310	}
	311
	312	switch (root->func) {
	313	case Val:
	314	if (root->ops[0]) {
	315	return evaluate_element (root->ops[0]);
	316	} else {
	317	return root->value;
	318	}
	319	break;
	320	case Add:
	321	case Sub:
	322	case Mul:
	323	case Div:
	324	case Pow:
	325	if (root->ops[1]) {
	326	op1 = evaluate_element (root->ops[1]);
	327	} else {
	328	VERBOSE (WARNING, PRINTOUT ("error while evaluating (op[1])\n"));
	329	return 0;
	330	}
	331	/* fallthrough */
	332	case Sqr:
	333	case Cos:
	334	case Sin:
	335	case Atn:
	336	case Log:
	337	case Exp:
	338	if (root->ops[0]) {
	339	op0 = evaluate_element (root->ops[0]);
	340	} else {
	341	VERBOSE (WARNING, PRINTOUT ("error while evaluating (op[0])\n"));
	342	return 0;
	343	}
	344	}
	345
	346	switch (root->func) {
	347	case Add: return op0 + op1;
	348	case Sub: return op0 - op1;
	349	case Mul: return op0 * op1;
	350	case Div: return op0 / op1;
	351	case Pow: return pow (op0, op1);
	352	case Sqr: return sqrt (op0);
	353	case Cos: return cos (op0);
	354	case Sin: return sin (op0);
	355	case Atn: return atan (op0);
	356	case Log: return log (op0);
	357	case Exp: return exp (op0);
	358	default: break;
	359	}
	360
	361	return 0;
	362	}
	363
bc97a989	364	/* vim: set ts=4 sw=4 et: */