/*
  Copyright 2010-2016 Grégory Soutadé

  This file is part of KissCount.

  KissCount is free software: you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation, either version 3 of the License, or
  (at your option) any later version.

  KissCount is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with KissCount.  If not, see <http://www.gnu.org/licenses/>.
*/

#include <string.h>
#include <stdio.h>
#include <iostream>

#include "ParseExp.hpp"

/*
  Algorithm
  The idea of this parser is very simple : Create a binary tree with an operator, a left and a right operand.
  Leafs are constants to be computed. This structure is more flexbile than a simple stack and very easy to parse
  (for resultat computation).
  A simple expression (3+4) will be represented by :
    +
  3   4
  Another example (3+4+5) :
    +
  3   +
    4   5
  
  If an operator is less prioritary than his father we have to do a transformation.
  Example with 3*4+5.
  in first instance we may have this tree :
   *
 3   +
   4   5
  So we must reverse the tree into something like :
       +
     *   5
   3  4
   
  At each step the parser must read one operand and one operator,
  fill a node with the operator and left operand and recurse on right
  operand. Finally we stop with a constant (a leaf).
  Operations in parenthesis must be computed separatly and filled into
  the tree like constants.
 */

/* Less to most prioritary */
enum {CST, ADD, SUB, MUL, DIV, MOD, EXP};

enum {DOUBLE_POINTED=1, INVALID_CHAR, INVALID_PARENTHESIS, INVALID_OPERATION};


#ifdef DEBUG
#define P(x) x
#else
#define P(x)
#endif

static double atof(char* s, int size)
{
    int neg = 0;
    double res = 0;

    for (; size--; s++)
    {
	if (*s == '.')
	{
	    neg = 10;
	    continue;
	}

	if (neg > 0)
	{
	    res += (double) (*s - '0') / (double)neg;
	    neg *= 10;
	}
	else
	{
	    res *= 10;
	    res += *s - '0';
	}
    }

    return res;
}

void ParseExp::ParseExp(char** expr, struct parse_opt* root, bool needParenthesis)
{
    char* temp;
    bool pointed = false;
    struct parse_opt* l, *r, *op, *op_tmp;
    char type = -1;
    bool negative = false, number = false;
    l = r = op = op_tmp = 0;

    if (!**expr) return;

    for (temp=*expr; **expr; (*expr)++)
    {
	if (**expr == '(')
	{
	    op_tmp = new struct parse_opt;
	    op_tmp->type = CST;
	    op_tmp->root = root;
	    op_tmp->l = op_tmp->r = 0;
	    (*expr)++;
	    ParseExp(expr, op_tmp, true);
	    l = op_tmp;
	    root->l = l;
	    continue;
	}

	if (**expr == ')')
	{
	    if (!needParenthesis)
		throw INVALID_PARENTHESIS;

	    if ((*expr-temp) == 0)
		throw INVALID_OPERATION;
	    break;
	}

	if (**expr >= '0' && **expr <= '9')
	    continue;

	if (**expr == '.')
	{
	    if (!pointed)
		pointed = true;
	    else
		throw DOUBLE_POINTED;

	    continue;
	}

	if (type != -1)
	    throw INVALID_OPERATION;

	switch(**expr)
	{
	case '+':
	    type = ADD;
	    break;
	case '-':
	    if (temp == *expr)
	    {
		if (negative)
		    throw INVALID_OPERATION;
		temp++;
		negative = true;
		continue;
	    }
	    type = SUB;
	    break;
	case '/':
	    type = DIV;
	    break;
	case '*':
	    type = MUL;
	    break;
	// case '%':
	//     type = MOD;
	//     break;
	default:
	    throw INVALID_CHAR;
	}

	number= true;

	if (!l)
	{
	    if ((*expr-temp) == 0)
		throw INVALID_OPERATION;
	    l = new struct parse_opt;
	    l->type = CST;
	    l->root = root;
	    l->l = 0; l->r = 0;
	    l->value = atof(temp, *expr-temp);
	    if (negative)
		l->value *= -1.0;
	    root->l = l;
	}

	// Here [temp..expr] must be left operand + operator
	if (root->root && root->root->type >= type)
	{
	    // Reverse tree
	    op = new parse_opt;
	    op->root = root->root;
	    op->type = root->root->type;
	    op->r = l;
	    op->l = root->root->l;
	    op->l->root = op;
	    root->root->l = op;
	    root->root->type = type;

	    root->type = CST;
	    root->value = 0.0;
	    root->l = 0 ; root->r = 0;

	    (*expr)++;
	    ParseExp(expr, root, needParenthesis);
	    break;
	    temp=*expr;
	}
	else
	{
	    // Recurse on right operand
	    root->type = type;
	    // atof
	    r = new struct parse_opt;
	    r->type = CST;
	    r->root = root;
	    r->l = 0; r->r = 0;
	    r->value = 0.0;
	    root->r = r;

	    (*expr)++;
	    ParseExp(expr, r, needParenthesis);
	    break;
	    temp=*expr;
	}

    }

    if (needParenthesis && **expr != ')')
    	throw INVALID_PARENTHESIS;

    if (!number)
    {
	if ((*expr-temp) == 0)
	    throw INVALID_OPERATION;

	if (op_tmp)
	    *root = *op_tmp;
	else
	{
	    root->type = CST;
	    root->l = 0; root->r = 0;
	    root->value = atof(temp, *expr-temp);
	    if (negative)
		root->value *= -1.0;
	}
    }

    return ;
}

double ParseExp::EvaluateExpr(struct parse_opt* root, bool del)
{
    double l, r, res;
    char type;

    type = root->type;

    if (root->type != CST)
    {
	l = EvaluateExpr(root->l, del);
	r = EvaluateExpr(root->r, del);
    }
    else
	l = root->value;

    if (del)
    {
	if (root->l) delete root->l;
	if (root->r) delete root->r;
    }

    switch (type)
    {
    case ADD:
	P(std::cout << "\t" << l << " + " << r << std::endl);
	return l+r;
    case SUB:
	P(std::cout << "\t" << l << " - " << r << std::endl);
	return l-r;
    case MUL:
	P(std::cout << "\t" << l << " * " << r << std::endl);
	return l*r;
    case DIV:
	P(std::cout << "\t" << l << " / " << r << std::endl);
	return l/r;
    // case MOD:
    // 	return EvaluateExpr(root->l) % EvaluateExpr(root->r);
    case EXP:
	P(std::cout << "\t" << l << " ^ " << r << std::endl);
	res = 1;
	while (r--)
	    res *= l;
	return res;
    case CST:
	return l;
    default:
	return 0.0;
    }
}

#ifdef DEBUG
using namespace ParseExp;

static char* e1;
static inline int test(char* expr, double target_result)
{
    struct parse_opt root, *r;
    char* e = e1;
    double res;

    memset(e1, 0, 100);
    strcpy(e1, expr);
    memset(&root, 0, sizeof(root));
    r = &root;

    ParseExp::ParseExp(&e1, r, false);
    res = EvaluateExpr(&root, true);

    res *= 100;
    res = ((long)res)/100.0;

    if (res == target_result)
	std::cout << e << " = " << res << "\n";
    else
    {
	std::cout << e << "(exp) " << target_result << " != " << "(res) " << res << "\n";
	throw "Invalid result !";
    }
}

int main()
{
    e1 = new char[100] ;

    try
    {
	test("4*3", 12);
	test("4*3+5", 17);
	test("3+3+3", 9);
	test("3+3+3+3", 12);
	test("4+3*5", 19);
	test("-4+3*5/2", 3.5);
	test("5+-4", 1);
	test("5--4", 9);
	test("4*(3+2)", 20);
	test("(3+2)*4", 20);
	test("4*(3+2)+5", 25);
	test("5+(3+2)*4", 25);
	test("3+(3+(3+3))", 12);
	test("3+(3+(3+(3+3)))*5", 63);
	test("5+(3/(6+8--5)*9)*4", 10.68);
	test("78.83-(.39+6.46+3.54+.23+1.57)", 66.64);
    }
    catch (int e)
    {
	std::cout << "Error " << e << std::endl;
    }

    return 0;
}

#endif