#include	<stdio.h>	/* printf(), etc. */
#include        <math.h>	/* powf(), etc. */
#include	"stk.h"
#include	"mystring.h"
#include	"cal.h"

/*
 * eval:
 *   o evaluates expression string, assuming postfix order!
 *   o returns resultant float value
 */
float eval(char *input)
{
	char	c;
	float	lhs,rhs;
	Stack	stack;

  stk_init(&stack);

  while((c = *input++) != '\0') {
    if(isdigit(c)) {
      input--;
      stk_push(&stack,myatof(&input));
    }
    else {
      switch(c) {
        case '*':
          rhs = stk_pop(&stack);
          lhs = stk_pop(&stack);
          stk_push(&stack,lhs * rhs);
          break;
        case '/':
          rhs = stk_pop(&stack);
          lhs = stk_pop(&stack);
          stk_push(&stack,lhs / rhs);
          break;
        case '+':
          rhs = stk_pop(&stack);
          lhs = stk_pop(&stack);
          stk_push(&stack,lhs + rhs);
          break;
        case '-':
          rhs = stk_pop(&stack);
          lhs = stk_pop(&stack);
          stk_push(&stack,lhs - rhs);
          break;
        case '^':
          rhs = stk_pop(&stack);
          lhs = stk_pop(&stack);
          stk_push(&stack,powf(lhs,rhs));
          break;
        case ' ':
        case '\t':
          /* do nothing - eat white space */
          break;
        default:
          printf(" UNK ");
      }
    }
  }
  return(stk_top(&stack));
}

/*
 * in2post:
 *   o convert infix expression (char array) into postfix
 *   o uses integer stack, where enum int values (operators) are pushed
 *   o operator values are enumerated according to operator precedence
 *     (this facilitates comparison of top operator on stack)
 *   o the algorithm is fairly straightforward:  when parsing,
 *     - operands: output immediately (to output infix string)
 *     - close parenthesis: pop all stack symbols until an open ( is seen
 *     - operator: pop all stack symbols until we see a symbol of lower
 *         precedence or a right associative symbol of equal precedence.
 *         Then push operator.
 *     - end of input: pop all remaining stack symbols.
 *     (algorithm obtained from:
 *       Weiss, Mark Allen, ``Algorithms, data structures, and problem
 *         solving with C++'', Addison-Wesley Longman, Inc., 1996, pp.359-364)
 *   o note1: regarding the operator decision above, what this boils down
 *       is equivalence classes among like operators, e.g., +, -, and *, /,
 *       and operators with themselves, __except__ for ^.  This is because
 *       the exponent is processed right-to-left.
 */
char *in2post(char *infix)
{
	int	nesting=0;
	char	c;
	Stack	stack;
	char	*p,*postfix;

  /* allocate new postfix array */
  if((postfix = (char *)malloc(MAXLINE*sizeof(char)))==NULL) {
    fprintf(stderr,"out of memory\n");
    exit(1);
  }
  /* set pointer to postfix array which to increment as array is filled in */
  p = postfix;

  stk_init(&stack);

  while((c = *infix++) != '\0') {
      switch(c) {
        case '(':
          stk_push(&stack,LPR);
          /* suspend popping until we clear all nested () expressions */
          nesting++;
          break;
        case ')':
          /* pop all operators until we see a ( */
          while( !stk_empty(&stack) && (stk_top(&stack) != LPR) )
            pop2postfix(&p,&stack);
          stk_pop(&stack);
          /* reduce one level of nesting */
          nesting--;
          break;
        case '^':
          /* pop all operators that have higher precedence */
          while( !nesting && !stk_empty(&stack) && (stk_top(&stack) > EXP) )
            pop2postfix(&p,&stack);

          /* push current operator on stack */
          stk_push(&stack,EXP);
          break;
        case '*':
          /* pop all operators that have higher or equal precedence */
          while( !nesting && !stk_empty(&stack) && (stk_top(&stack) >= DIV) )
            pop2postfix(&p,&stack);

          /* push current operator on stack */
          stk_push(&stack,MUL);
          break;
        case '/':
          /* pop all operators that have higher or equal precedence */
          while( !nesting && !stk_empty(&stack) && (stk_top(&stack) >= DIV) )
            pop2postfix(&p,&stack);

          /* push current operator on stack */
          stk_push(&stack,DIV);
          break;
        case '+':
          /* pop all operators that have higher or equal precedence */
          while( !nesting && !stk_empty(&stack) && (stk_top(&stack) >= MNS) )
            pop2postfix(&p,&stack);

          /* push current operator on stack */
          stk_push(&stack,PLS);
          break;
        case '-':
          /* pop all operators that have higher or equal precedence */
          while( !nesting && !stk_empty(&stack) && (stk_top(&stack) >= MNS) )
            pop2postfix(&p,&stack);

          /* push current operator on stack */
          stk_push(&stack,MNS);
          break;
        default:
          /* operand (or white space): simply "output" to postfix string */
          *p++ = c;
    }
  }
  /* pop all remaining operators, then terminate string with \0 character */
  while(!stk_empty(&stack))
    pop2postfix(&p,&stack);
  *p = '\0';

  /* return ptr to first element of postfix array (not p, pointint to end) */
  return(postfix);
}

/*
 * pop2postfix:
 *   o pops element off stack and appends to character array (surrounded by
 *     spaces for readibilty and for subsequent evaluation)
 *   o pointer to (char) pointer is used since we want to advance the array
 *     pointer as we write to the array
 */
void pop2postfix(char **p, Stack *stack)
{
  *(*p)++ = ' ';
  *(*p)++ = token2char((TokenType)(int)stk_pop(stack));
  *(*p)++ = ' ';
}

/*
 * token2char:
 *   o returns character "encoding" of given operator (token)
 */
char token2char(TokenType t)
{
  switch(t) {
      case EXP: return('^');
      case MUL: return('*');
      case DIV: return('/');
      case PLS: return('+');
      case MNS: return('-');
      default:  return(' ');
  }
}