parser

c

#include "parser.h"

char* substring(char *src, int start, int length) {
	char* res = (char *)malloc(sizeof(char) * (length + 1));
	if (res == NULL)
	{
		return NULL;
	}

	memcpy(res, src + start, length);
	res[length] = 0;

	return res;
}

result* createResult(double acc, char* rest) {
	result *res = (result*)malloc(sizeof(result));
	if (res == NULL)
	{
		return NULL;
	}

	res->acc = acc;
	res->rest = rest;

	return res;
}

variable createVariable(char* name, double value) {
	variable var;
	var.name = name;
	var.value = value;

	return var;
}

item* createItem(variable var) {
	item* it = (item*)malloc(sizeof(item));
	it->var = var;
	it->next = NULL;

	return it;
}

void createVariablesList(void) {
	variable e = createVariable("e", M_E);
	variable pi = createVariable("pi", M_PI);

	item* eItem = createItem(e);
	item* piItem = createItem(pi);

	eItem->next = piItem;
	variables = eItem;
}

void clearVariablesList(void) {
	item *p;

	while (variables) {
		p = variables;
		variables = variables->next;

		free(p);
	}
}

int getVariable(char* name, double* r) {
	item* p = variables;
	while (p != NULL && strcmp(p->var.name, name)) {
		p = p->next;
	}

	if (p) {
		*r = p->var.value;

		return 0;
	}
	else {
		return UNKNOWN_VARIABLE;
	}
}

void setVariable(char* name, double value) {
	item* p = variables;
	while (p->next != NULL) {
		p = p->next;
	}

	p->next = createItem(createVariable(name, value));
}

void unsetVariable(char* name) {
	item* p = variables;
	item* q = variables;

	while (p != NULL && strcmp(p->var.name, name)) {
		if (p->next != NULL) {
			q = p;
		}

		p = p->next;
	}

	if (p) {
		q->next = p->next;
		free(p);
	}
}

char* skipSpaces(char* s) {
	int i = 0;
	int len = (int)strlen(s) + 1;
	char *end;
	char *result;

	// trim leading space
	while (isspace(*s)) {
		--len;
		s++;
	}

	if (*s != 0) {
		// trim trailing space
		end = s + (int)strlen(s) - 1;
		while (end > s && isspace(*end)) {
			++i;
			end--;
		}

		len -= i;
	}

	result = (char*)malloc(sizeof(char) * len);
	if (result == NULL) {
		return NULL;
	}
	for (i = 0; i != len - 1; ++i) {
		result[i] = s[i];
	}
	result[len - 1] = 0;

	return result;
}

int processDoubleFunction(char* func, double acc, result* res, result *r) {
	if (!strcmp(func, "log")) {
		if (res->acc <= 0 || acc <= 0) {
			return ILLEGAL_LOG_ARG;
		}

		r->acc = log(res->acc) / log(acc);
		r->rest = res->rest;

		return 0;
	}
	else {
		return UNKNOWN_FUNCTION;
	}
}

int processSingleFunction(char* func, result* res, result* r) {
	if (!strcmp(func, "sin")) {
		r->acc = sin(res->acc);
	}
	else if (!strcmp(func, "cos")) {
		r->acc = cos(res->acc);
	}
	else if (!strcmp(func, "tg")) {
		if (fabs(cos(res->acc)) < 0.0001) {
			return ILLEGAL_TG_ARG;
		}

		r->acc = tan(res->acc);
	}
	else if (!strcmp(func, "ctg")) {
		if (fabs(sin(res->acc)) < 0.0001) {
			return ILLEGAL_CTG_ARG;
		}

		r->acc = 1.0 / tan(res->acc);
	}
	else if (!strcmp(func, "arcsin")) {
		if (res->acc < -1 || res->acc > 1) {
			return ILLEGAL_ASIN_ARG;
		}

		r->acc = asin(res->acc);
	}
	else if (!strcmp(func, "arccos")) {
		if (res->acc < -1 || res->acc > 1) {
			return ILLEGAL_ACOS_ARG;
		}

		r->acc = acos(res->acc);
	}
	else if (!strcmp(func, "arctg")) {
		r->acc = atan(res->acc);
	}
	else if (!strcmp(func, "ln")) {
		if (res->acc <= 0) {
			return ILLEGAL_LOG_ARG;
		}

		r->acc = log(res->acc);
	}
	else if (!strcmp(func, "sqrt")) {
		if (res->acc < 0) {
			return ILLEGAL_SQRT_ARG;
		}

		r->acc = sqrt(res->acc);
	}
	else if (!strcmp(func, "floor")) {
		r->acc = floor(res->acc);
	}
	else if (!strcmp(func, "ceil")) {
		r->acc = ceil(res->acc);
	}
	else {
		return UNKNOWN_FUNCTION;
	}

	r->rest = res->rest;

	return 0;
}

int num(char* s, result* r) {
	int i = 0;
	char* t = NULL;
	int len = (int)strlen(s);
	int dotsCount = 0;
	int expsCount = 0;
	int negative = 0;

	// number can be started from minus sign
	if (s[0] == '-') {
		if (isspace(s[1])) {
			t = skipSpaces(s);
			if (t == NULL) {
				return MEMORY_ERROR;
			}
		}
		else {
			t = substring(s, 0, (int)strlen(s));
			if (t == NULL) {
				return MEMORY_ERROR;
			}
		}

		// single minus as operation
		if (t[1] == '(') {
			r->acc = 0;
			r->rest = t;

			return 0;
		}
		else {
			free(t);
			negative = 1;
			*s++;
		}
	}

	// allows only ., single numbers or e/E
	while (i < len && (
		isdigit(s[i]) || s[i] == '.' || s[i] == 'e' || s[i] == 'E' || (
		i != 0 && s[i] == '-' && (
		s[i - 1] == 'e' || s[i - 1] == 'E'
		)
		)
		)) {
		// only one point
		if (s[i] == '.' && ++dotsCount > 1) {
			return ILLEGAL_NUMBER;
		}
		// and only one exp
		if ((s[i] == 'e' || s[i] == 'E') && ++expsCount > 1) {
			return ILLEGAL_NUMBER;
		}
		i++;
	}
	if (i == 0) {
		// we didn't find any numbers
		return ILLEGAL_NUMBER;
	}

	t = substring(s, 0, i);
	if (t == NULL) {
		return MEMORY_ERROR;
	}

	double n = atof(t);
	if (negative) {
		n = -n;
	}

	free(t);
	t = substring(s, i, len - i);
	if (t == NULL) {
		return MEMORY_ERROR;
	}

	r->acc = n;
	r->rest = t;

	return 0;
}

int closeBracket(result* res, result *r) {
	int len = (int)strlen(res->rest);
	char *t = NULL;

	if (strcmp(res->rest, "") && res->rest[0] == ')') {
		t = substring(res->rest, 1, len - 1);
		if (t == NULL) {
			return MEMORY_ERROR;
		}

		free(res->rest);
		res->rest = t;
	}
	else {
		return NO_CLOSING_BRACKET;
	}

	r->acc = res->acc;
	r->rest = res->rest;

	return 0;
}

int functionVariable(char *s, result* r) {
	int i = 0;
	int len = (int)strlen(s);
	char *f = (char*)malloc(sizeof(char) * (len + 1));
	result *res = NULL;
	result *res2 = NULL;
	double acc;
	double newVariable;
	int error;
	char *t = NULL;

	if (f == NULL)
	{
		return MEMORY_ERROR;
	}

	res = createResult(0, NULL);
	if (res == NULL) {
		free(f);
		return MEMORY_ERROR;
	}

	res2 = createResult(0, NULL);
	if (res2 == NULL) {
		free(res);
		free(f);
		return MEMORY_ERROR;
	}

	for (i = 0; i != len + 1; ++i) {
		f[i] = 0;
	}

	// try to find function name of variable
	i = 0;
	while (i < len && (isalpha(s[i]) || (isdigit(s[i]) && i > 0))) {
		f[i] = s[i];
		i++;
	}

	if (strcmp(f, "")) {
		// if we found something
		if (len > i && s[i] == '(') {
			// next symbol ( - it's function
			t = substring(s, (int)strlen(f) + 1, len);

			if (t == NULL) {
				free(res);
				free(res2);
				free(f);
				return MEMORY_ERROR;
			}

			error = binaryFunc(t, res);
			if (error) {
				free(res);
				free(res2);
				free(t);
				free(f);
				return error;
			}

			if (strcmp(res->rest, "") && res->rest[0] == ',') {
				// if function with two parameters
				acc = res->acc;
				free(t);
				t = substring(res->rest, 1, (int)strlen(res->rest) - 1);
				if (t == NULL) {
					free(res);
					free(res2);
					free(f);
					free(t);
					return MEMORY_ERROR;
				}

				free(res->rest);
				error = binaryFunc(t, res2);
				if (error) {
					free(res);
					free(res2);
					free(f);
					free(t);
					return error;
				}

				error = closeBracket(res2, res2);
				if (error) {
					free(res);
					free(res2);
					free(f);
					free(t);
					return error;
				}

				error = processDoubleFunction(f, acc, res2, r);
				if (error) {
					free(res);
					free(res2);
					free(f);
					free(t);
					return error;
				}

				free(res);
				free(res2);
				free(f);
				free(t);
				return 0;
			}
			else {
				error = closeBracket(res, res);
				if (error) {
					free(res);
					free(res2);
					free(f);
					free(t);
					return error;
				}

				error = processSingleFunction(f, res, r);
				if (error) {
					free(res->rest);
					free(res);
					free(res2->rest);
					free(res2);
					free(f);
					free(t);
					return error;
				}

				free(res);
				free(res2->rest);
				free(res2);
				free(f);
				free(t);
				return 0;
			}
		}
		else {
			// otherwise - it's variable
			if (len > (int)strlen(f) && s[(int)strlen(f)] == '=') {
				// it's variable define
				t = substring(s, 0, (int)strlen(f) + 1);
				if (t == NULL) {
					free(res);
					free(res2);
					free(f);
					return MEMORY_ERROR;
				}

				error = parse(t, &newVariable);
				if (error) {
					free(res);
					free(res2);
					free(t);
					free(f);
					return error;
				}

				setVariable(f, newVariable);

				free(f);

				r->acc = newVariable;
				r->rest = NULL;

				return 0;
			}
			else {
				error = getVariable(f, &newVariable);
				if (error) {
					free(res);
					free(res2);
					free(f);
					return error;
				}

				r->acc = newVariable;

				free(t);
				t = substring(s, (int)strlen(f), len - (int)strlen(f));

				free(f);
				if (t == NULL) {
					free(res);
					free(res2);
					return MEMORY_ERROR;
				}

				r->rest = t;

				free(res);
				free(res2->rest);
				free(res2);
				return 0;
			}
		}
	}

	error = num(s, r);
	if (error) {
		free(res);
		free(res2);
		free(f);
		return error;
	}

	free(res);
	free(res2->rest);
	free(res2);
	free(f);
	return 0;
}

int bracket(char* s, result* r) {
	char zeroChar;
	int len;
	int error;
	result *res = NULL;
	char *t = NULL;
	char *t2 = NULL;

	t = skipSpaces(s);
	if (t == NULL) {
		return MEMORY_ERROR;
	}

	zeroChar = t[0];
	len = (int)strlen(t);
	res = createResult(0, NULL);

	if (res == NULL) {
		free(t);
		return MEMORY_ERROR;
	}

	if (zeroChar == '(') {
		t2 = substring(t, 1, len - 1);
		free(t);

		if (t2 == NULL) {
			free(res);
			return MEMORY_ERROR;
		}

		error = binaryFunc(t2, res);
		if (error) {
			free(t2);
			free(res);
			return error;
		}

		if (strcmp(res->rest, "")) {
			free(t2);
			t2 = substring(res->rest, 1, len - 1);
			if (t2 == NULL) {
				free(res);
				return MEMORY_ERROR;
			}

			free(res->rest);
			res->rest = t2;
		}
		else {
			free(res);
			return NO_CLOSING_BRACKET;
		}

		r->acc = res->acc;
		r->rest = res->rest;

		free(res);
		return 0;
	}

	error = functionVariable(t, r);
	if (error) {
		free(res);
		free(t);
		return error;
	}

	free(res);
	free(t);
	return 0;
}

int exponentiation(char* s, result* r) {
	result* cur = createResult(0, NULL);
	result* right = NULL;
	char *t;
	int error;

	if (cur == NULL) {
		return MEMORY_ERROR;
	}

	error = bracket(s, cur);
	if (error) {
		free(cur);
		return error;
	}

	t = skipSpaces(cur->rest);
	if (t == NULL) {
		return MEMORY_ERROR;
	}

	free(cur->rest);
	cur->rest = t;

	for (;;) {
		if ((int)strlen(cur->rest) == 0) {
			r->acc = cur->acc;
			r->rest = cur->rest;

			free(cur);
			return 0;
		}

		if (cur->rest[0] != '^') {
			break;
		}

		t = substring(cur->rest, 1, (int)strlen(cur->rest) - 1);
		if (t == NULL) {
			return MEMORY_ERROR;
		}

		right = createResult(0, NULL);
		if (right == NULL) {
			free(cur);
			free(t);
			return MEMORY_ERROR;
		}

		error = plusMinus(t, right);
		if (error) {
			free(right);
			if (cur->rest != NULL) {
				free(cur->rest);
			}
			free(cur);
			return error;
		}

		free(cur->rest);
		free(t);
		
		cur->acc = pow(cur->acc, right->acc);
		cur->rest = right->rest;

		free(right);
	}

	r->acc = cur->acc;
	r->rest = cur->rest;

	free(cur);
	return 0;
}

int mulDiv(char* s, result* r) {
	result* cur = NULL;
	result* right = NULL;
	char *t = NULL;
	int error;
	double acc;
	char sign;

	cur = createResult(0, NULL);
	if (cur == NULL) {
		return MEMORY_ERROR;
	}

	right = createResult(0, NULL);
	if (right == NULL) {
		free(cur);
		return MEMORY_ERROR;
	}

	error = exponentiation(s, cur);
	if (error) {
		free(cur);
		free(right);
		return error;
	}

	acc = cur->acc;

	t = skipSpaces(cur->rest);
	if (t == NULL) {
		return MEMORY_ERROR;
	}

	free(cur->rest);
	cur->rest = t;

	for (;;) {
		if ((int)strlen(cur->rest) == 0) {
			r->acc = cur->acc;
			r->rest = cur->rest;

			free(right);
			free(cur);
			return 0;
		}

		sign = cur->rest[0];
		if (sign != '*' && sign != '/') {
			r->acc = cur->acc;
			r->rest = cur->rest;

			free(right);
			free(cur);
			return 0;
		}

		t = substring(cur->rest, 1, (int)strlen(cur->rest) - 1);
		if (t == NULL) {
			free(cur);
			free(right);
			return MEMORY_ERROR;
		}

		error = exponentiation(t, right);
		if (error) {
			free(cur);
			free(right);
			return error;
		}

		switch (sign) {
		case '*':
			acc *= right->acc;
			break;
		case '/':
			if (fabs(right->acc) < 0.0001) {
				free(cur);
				free(right);
				return DIVISION_BY_ZERO;
			}
			acc /= right->acc;
			break;
		}

		cur->acc = acc;

		free(cur->rest);
		free(t);

		cur->rest = right->rest;
	}
}

int plusMinus(char* s, result* r) {
	result* cur = createResult(0, NULL);
	char *t = NULL;
	int len = 0;
	int error;
	double acc;
	char sign;

	if (cur == NULL) {
		return MEMORY_ERROR;
	}

	// handle single minus
	if ((int)strlen(s) > 0 && s[0] == '-') {

	}

	error = mulDiv(s, cur);
	if (error) {
		free(cur);
		return error;
	}

	acc = cur->acc;

	t = skipSpaces(cur->rest);
	if (t == NULL) {
		free(cur);
		return MEMORY_ERROR;
	}

	free(cur->rest);
	cur->rest = t;

	len = (int)strlen(cur->rest);
	while (len > 0) {
		if (!(cur->rest[0] == '+' || cur->rest[0] == '-')) {
			break;
		}

		sign = cur->rest[0];

		t = substring(cur->rest, 1, len - 1);
		if (t == NULL) {
			free(cur);
			return MEMORY_ERROR;
		}

		free(cur->rest);
		error = mulDiv(t, cur);

		if (error) {
			free(t);
			free(cur);
			return error;
		}

		if (sign == '+') {
			acc += cur->acc;
		}
		else {
			acc -= cur->acc;
		}

		len = (int)strlen(cur->rest);
		free(t);
	}

	r->acc = acc;
	r->rest = cur->rest;

	free(cur);
	return 0;
}

int binaryFunc(char* s, result* r) {
	result* cur = createResult(0, NULL);
	char *t;
	int error;
	double acc;

	if (cur == NULL) {
		return MEMORY_ERROR;
	}

	error = plusMinus(s, cur);
	if (error) {
		free(cur);
		return error;
	}

	acc = cur->acc;

	t = skipSpaces(cur->rest);
	if (t == NULL) {
		return MEMORY_ERROR;
	}

	free(cur->rest);
	cur->rest = t;

	r->acc = acc;
	r->rest = cur->rest;

	free(cur);
	return 0;
}

int parse(char* s, double *r) {
	result* res = createResult(0, NULL);
	if (res == NULL) {
		return MEMORY_ERROR;
	}

	int error = binaryFunc(s, res);

	if (res->rest != NULL && strcmp(res->rest, "")) {
		free(res);
		return CANNOT_PARSE;
	}

	*r = res->acc;

	if (res->rest != NULL) {
		free(res->rest);
	}

	free(res);
	return error;
}