/* eval.c */

/*
  this program:
  - reads lines from standard input, each line represents an
    infix expression consisting of non-negative real numbers and
    valid operators; each line sould not contain more than 79
    characters
  - converts an infix expression into a postfix expression
  - evaluates a postfix expression
  - for each line of input, prints the original input string
    and the result of evaluation
*/

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <ctype.h>
#include <string.h>
#include "stacku.h"

#define SIZEIN     80       /* max size of input line (infix expression) */
#define SIZEPOST  256       /* max size of postfix expression            */

int isoperator(char);
int precedence (char);
char* in2post(char*, char*);
double evalpost(char*);
double apply(char oper, double opnd1, double opnd2);


main() {
	char in[SIZEIN], post[SIZEPOST], *r;

	r = fgets(in, SIZEIN, stdin);
	while (r != NULL) {
		assert(in[strlen(in)-1] == '\n');
		in[strlen(in)-1] = '\0';
		fprintf(stdout, "%s", in);
		fprintf(stdout, " = %.2f\n", evalpost(in2post(in, post)));
		r = fgets(in, SIZEIN, stdin);
	}

	return 0;

} /* end main */



/* functions to convert and evaluate an expression */

/* converts an infix expression into postfix, returns a pointer to
   a postfix expression */
char * in2post(char *infix, char *postfix) {

	Stack *s;
	char *p = postfix;
	Type curr_oper, old_oper;

	s = stack_new();

	while (*infix) {
		while (isspace(*infix))
			infix++;
		if (!*infix) break;
		if (isdigit(*infix) || *infix == '.') {
			while (isdigit(*infix) || *infix == '.')
				*postfix++ = *infix++;
			*postfix++ = ' ';
		}
		else {
			assert(isoperator(*infix));
			curr_oper.item.cval = *infix;
			infix ++;
			if (curr_oper.item.cval == '(') {
				curr_oper.tag = CHAR;
				stack_push(s, curr_oper);
			}
			else if (curr_oper.item.cval == ')') {
				old_oper = stack_pop(s);
				assert(old_oper.tag == CHAR);
				while (old_oper.item.cval != '(') {
					*postfix++ = old_oper.item.cval;
					*postfix++ = ' ';
					old_oper = stack_pop(s);
					assert(old_oper.tag == CHAR);
				}
			}
			else {
				while (!stack_isempty(*s) &&
						 precedence(stack_top(*s).item.cval) >= precedence(curr_oper.item.cval)) {
					old_oper = stack_pop(s);
					assert(old_oper.tag == CHAR);
					*postfix++ = old_oper.item.cval;
					*postfix++ = ' ';
				}  /* end while */
				curr_oper.tag = CHAR;
				stack_push(s, curr_oper);
			} /* end else */
		}	/* end else */
	}   /* end while */

	while (!stack_isempty(*s)) {
		old_oper = stack_pop(s);
		assert(old_oper.tag == CHAR);
		*postfix++ = old_oper.item.cval;
		*postfix++ = ' ';
	}

	*postfix = '\0';

	return p;
}

/* evaluates a postfix expression and returns the result */
double evalpost (char *postfix) {
	Type opnd1, opnd2, result;
	Stack opndst;

	assert(postfix);

	stack_init(&opndst);

	while (*postfix) {
		while (isspace(*postfix))
			postfix++;
		if (!*postfix) break;
		if (isdigit(*postfix)) {
			opnd1.item.dval = strtod(postfix, &postfix);
			opnd1.tag = DOUBLE;
			stack_push(&opndst, opnd1);
		}
		else {
			assert(isoperator(*postfix));
			opnd2 = stack_pop(&opndst);
			assert(opnd2.tag == DOUBLE);
			opnd1 = stack_pop(&opndst);
			assert(opnd1.tag == DOUBLE);
			result.item.dval = apply(*postfix, opnd1.item.dval, opnd2.item.dval);
			result.tag = DOUBLE;
			stack_push(&opndst, result);
			postfix++;
		}
	}
	result = stack_pop(&opndst);
	assert(result.tag == DOUBLE);
	assert(stack_isempty(opndst));
	return result.item.dval;
}

/* returns true if oper is a valid operator, otherwise returns false */
int isoperator(char oper) {

	return oper == '+' || oper == '-' ||
			 oper == '*' || oper == '/' ||
			 oper == '(' || oper == ')';
}

/* returns a number that characterized precedence of an operator:
   the bigger the number, the higher precedence */
int precedence(char oper) {
	if (oper == '+' || oper == '-')
		return 1;
	else if (oper == '*' || oper =='/')
		return 2;
	else if (oper == '(')
		return 0;
}

/* returns the result of the operation oper on the opnd1 and opnd2 */
double apply(char oper, double opnd1, double opnd2) {

	if (oper == '+')
		return opnd1 + opnd2;
	if (oper == '-')
		return opnd1 - opnd2;
	if (oper == '*')
		return opnd1 * opnd2;
	if (oper == '/') {
		assert(opnd2);
		return opnd1/opnd2;
	}
}