#include <stdio.h>  /* printf */
#include <stdlib.h> /* malloc, free*/
#include <assert.h> /* assert */
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include "scanner.h"
#include "recognizeExp.h"
#include "evalExp.h"
#include "prefixExp.h"
#include "infixExp.h"

struct infix
{
    char target[100] ;
    char stack[100] ;
    char *s ,*t;
    int top, l ;
} ;


void initinfix ( struct infix * ) ;
void setexpr ( struct infix *, char * ) ;
void push ( struct infix *, char ) ;
char pop ( struct infix * ) ;
void convert ( struct infix * ) ;
int priority ( char c ) ;
List getPrefixlist ( struct infix ) ;


// simple function to reverse a string since linux has problems with strrev
void reverse(char *str1)
{
    // declare variable
    int i, len, temp;
    len = strlen(str1); // use strlen() to get the length of str string

    // use for loop to iterate the string
    for (i = 0; i < len/2; i++)
    {
        // temp variable use to temporary hold the string
        temp = str1[i];
        str1[i] = str1[len - i - 1];
        str1[len - i - 1] = temp;
    }
}


/* The function treeExpression tries to build a tree from the tokens in the token list
 * (its first argument) and makes its second argument point to the tree.
 * The return value indicates whether the action is successful.
 * Observe that we use ordinary recursion, not mutual recursion.
 */

int TreePrefixEx(List *lp, ExpTree *tp) {
  double w;
  char *s;
  char c;
  Token t;
  ExpTree tL, tR;
  if ( valueNumber(lp,&w) ) {
    t.number = (int)w;
    *tp = newExpTreeNode(Number, t, NULL, NULL);
    return 1;
  }
  if ( valueIdentifier(lp,&s) ) {
    t.identifier = s;
    *tp = newExpTreeNode(Identifier, t, NULL, NULL);
    return 1;
  }
  if ( valueOperator(lp,&c) && TreePrefixEx(lp,&tL) ) {
    if ( TreePrefixEx(lp,&tR) ) {
      t.symbol = c;
      *tp = newExpTreeNode(Symbol, t, tL, tR);
      return 1;
    } else { /* withuot 'else' the program works fine, but there is a memory leak */
      freeExpTree(tL);
      return 0;
    }
  }
  return 0;
}
void initinfix ( struct infix *pq )
{
    pq -> top = -1 ;
    strcpy ( pq -> target, "" ) ;
    strcpy ( pq -> stack, "" ) ;
    pq -> l = 0 ;
}
/* reverses the given expression */
void setexpr ( struct infix *pq, char *str )
{
    pq -> s = str ;
    reverse ( pq -> s ) ;
    pq -> l = strlen ( pq -> s ) ;
    *( pq -> target + pq -> l ) = '\0' ;
    pq -> t = pq -> target + ( pq -> l - 1 ) ;
}
/* adds operator to the stack */
void push ( struct infix *pq, char c )
{
    if ( pq -> top == 10 - 1 )
        printf ( "\nStack is full.\n" ) ;
    else
    {
        pq -> top++ ;
        pq -> stack[pq -> top] = c ;
    }
}
/* pops an operator from the stack */
char pop ( struct infix *pq )
{
    if ( pq -> top == -1 )
    {
        printf ( "Stack is empty\n" ) ;
        return -1 ;
    }
    else
    {
        char item = pq -> stack[pq -> top] ;
        pq -> top-- ;
        return item ;
    }
}
/* converts the infix expr. to prefix form */
void convert ( struct infix *pq )
{
    char opr ;
    while ( *( pq -> s ) )
    {
        if ( *( pq -> s ) == ' ' || *( pq -> s ) == '\t' )
        {
            pq -> s++ ;
            continue ;
        }
        if ( isdigit ( *( pq -> s ) ) || isalpha ( *( pq -> s ) ) )
        {
            while ( isdigit ( *( pq -> s ) ) || isalpha ( *( pq -> s ) ) )
            {
                *( pq -> t ) = *( pq -> s ) ;
                pq -> s++ ;
                pq -> t-- ;
            }
        }
        if ( *( pq -> s ) == ')' )
        {
            push ( pq, *( pq -> s ) ) ;
            pq -> s++ ;
        }
        if ( *( pq -> s ) == '*' || *( pq -> s ) == '+' || *( pq -> s ) == '/' || *( pq -> s ) == '%' || *( pq -> s ) == '-' || *( pq -> s ) == '$' )
        {
            if ( pq -> top != -1 )
            {
                opr = pop ( pq ) ;
                while ( priority ( opr ) > priority ( *( pq -> s ) ) )
                {
                    *( pq -> t ) = opr ;
                    pq -> t-- ;
                    opr = pop ( pq ) ;
                }
                push ( pq, opr ) ;
                push ( pq, *( pq -> s ) ) ;
            }
            else
                push ( pq, *( pq -> s ) ) ;
                pq -> s++ ;
        }
        if ( *( pq -> s ) == '(' )
        {
            opr = pop ( pq ) ;
            while ( opr != ')' )
            {
                *( pq -> t ) = opr ;
                pq -> t-- ;
                opr = pop ( pq ) ;
            }
            pq -> s++ ;
        }
    }
    while ( pq -> top != -1 )
    {
        opr = pop ( pq ) ;
        *( pq -> t ) = opr ;
        pq -> t-- ;
    }
    pq -> t++ ;
}
/* returns the priotity of the operator */
int priority ( char c )
{
    if ( c == '$' )
        return 3 ;
    if ( c == '*' || c == '/' || c == '%' )
        return 2 ;
    else
    {
        if ( c == '+' || c == '-' )
            return 1 ;
        else
            return 0 ;
    }
}
/* displays the prefix form of given expr. */
List getPrefixlist ( struct infix pq )
{
    char* ar = malloc(sizeof(*ar));
    int i=0;
    List tl;
    while ( *( pq.t ) )
    {
        ar[i]=*( pq.t );
        pq.t++ ;
    }
    tl= tokenList(ar);
    free(ar);
    return tl;
}
// the main conversion function , calling it should return the expression in prefix form
List Conv( )
{
    struct infix q ;
    char *ar ;
    List tl;
    ar = readInput();
    initinfix ( &q ) ;
    setexpr ( &q, ar ) ;
    convert ( &q ) ;
    tl = getPrefixlist ( q ) ;
    return tl;
}
/* the function prefExpressionExpTrees performs a dialogue with the user and tries
 * to recognize the input as a prefix expression. When it is a numerical prefix
 * expression, its value is computed and printed.
 */

void prefExpTr() {
  char *ar;
  List tl, tl1;
  ExpTree t = NULL;
  printf("give an expression: ");
  ar = readInput();
  while (ar[0] != '!') {
    tl = tokenList(ar);
    printList(tl);
    tl=Conv();
    tl1 = tl;
    if ( TreePrefixEx(&tl1,&t) && tl1 == NULL ) {
         /* there should be no tokens left */
      printf("in infix notation: ");
      printExpTreeInfix(t);
      printf("\n");
      if ( isNumerical(t) ) {
        printf("the value is %g\n",valueExpTree(t));
      } else {
        printf("this is not a numerical expression\n");
      }
    } else {
      printf("this is not an expression\n");
    }
    freeExpTree(t);
    t = NULL;
    freeTokenList(tl);
    free(ar);
    printf("\ngive an expression: ");
    ar = readInput();
  }
  free(ar);
  printf("good bye\n");
}