//---------------------------------------------------
// Recursive Parser of Ariphmetic Formulas
//
// Formula may include 4 ariphmetic operations,
// the exponentiation operation ^ or **,
// integer and double constants, and
// variables x, y, z.
//
// The parser converts a formula to
// Reverse Polish Notation. The RPN is used to
// calculate a value of a formula for given x, y, z.
//---------------------------------------------------

/*

The initial grammar is:
S -> F $                                // Formula with end of line marker
F -> T | F + T | F - T                  // Formula
T -> M | T * M | T / M                  // Term
M -> E | E ^ M                          // Multiplier
E -> number | x | y | z | func | ( F )  // Elementary formula
Func -> name ( Args )                   // Function call
Args -> eps | ArgList                   // Arguments of a function
ArgList -> F | ArgList, F               // non-empty list of arguments

This grammar is not LL(1).
We transform it to the recursive form for LL(1)-parsing:

S -> F $                // S is a Formula with the end of line marker
F -> T FTail            // Formula is a Term and a Tail of Formula
FTail -> eps | + T FTail | - T FTail        // Tail of Formula
T -> M TTail            // Term is a Multiplier and a Tail of Term
TTail -> eps | * M TTail | / M TTail        // Tail of Term
M -> E MTail            // Multiplier is Elementary formula and a Tail of Multiplier
MTail -> eps | ^ M                          // Tail of Multiplier
E -> number | x | y | z | Func | ( F )      // Elementary formula
Func -> name ( Args )                       // Function call
Args -> eps | ArgList                       // Args of function
ArgList -> F ArgListTail                    // non-empty ArgList
ArgListTail -> eps | , F ArgListTail        // Tail of argument list

*/

#include <cstdio>
#include <cstring>
#include <cassert>
#include <cmath>
#include <string>
#include <deque>
#include "rparser.h"
#include "lextypes.h"

using namespace std;

static const char* TOKEN_NAMES[] = {
    "NUMBER",           // 0
    "NAME",             // 1
    "PLUS",             // 2
    "MINUS",            // 3
    "MUL",              // 4
    "DIV",              // 5
    "POW",              // 6
    "LPAR",             // 7
    "RPAR",             // 8
    "CM",               // 9
    "X",                // 10
    "Y",                // 11
    "Z",                // 12
    "ENDLINE",          // 13
    "ENDSTREAM",        // 14
    "UNDEFINED"         // 15
};

const char* Token::tokenName() const {
    return TOKEN_NAMES[token];
}

string Token::toString() const {
    char line[256];
    char txt[64];
    sprintf(line, "(%s, ", tokenName());
    if (token == Token::NAME) {
        strcat(line, "\"");
        strcat(line, text.c_str());
        strcat(line, "\"");
    } else {
        strcat(line, "\"\"");
    }
    strcat(line, ", ");
    if (token == Token::NUMBER) {
        sprintf(txt, "%g", value);
        strcat(line, txt);
    } else {
        strcat(line, "0");
    }
    strcat(line, ")");
    return string(line);
}

class ParserException {
    const char *txt;
public:
    ParserException(const char *str = ""):
        txt(str)
    {}
    
    const char* what() const {
        return txt;
    }
};

// S -> F $
bool RParser::parse() {
    try {
        processF();
        skipToken(Token::ENDLINE);
        return true;
    } catch (const ParserException& e) {
        return false;
    }
}

void RParser::skipToken(int tokenType /* = (-1) */) {
    Token t = peekToken();
    if (tokenType >= 0 && t.token != tokenType) {
        throw ParserException("Syntax error at the end of line");
    }
    popToken();
}

// F -> T FTail
void RParser::processF() {
    // printf("Process Formula\n");
    processT();
    processFTail();
}

// FTail -> eps | + T FTail | - T FTail
void RParser::processFTail() {  // Process Tail of formula
    // printf("Process Tail of Formula\n");
    Token t = peekToken();
    if (t.token == Token::PLUS) {
        skipToken();
        processT();
        rpn.push_back(t);
        processFTail();
    } else if (t.token == Token::MINUS) {
        skipToken();
        processT();
        rpn.push_back(t);
        processFTail();
    }
}

// T -> M TTail
void RParser::processT() {  // Process term
    // printf("Process Term\n");
    processM();
    processTTail();
}

// TTail -> eps | * M TTail | / M TTail  
void RParser::processTTail() {  // Process Tail of Term
    // printf("Process Tail of Term\n");
    Token t = peekToken();
    if (t.token == Token::MUL) {
        skipToken();
        processM();
        rpn.push_back(t);
        processTTail();
    } else if (t.token == Token::DIV) {
        skipToken();
        processM();
        rpn.push_back(t);
        processTTail();
    }
}

// M -> E MTail
void RParser::processM() {  
    processE();
    processMTail();
}        
        
// MTail -> eps | ^ M
void RParser::processMTail() {
    Token t = peekToken();
    if (t.token == Token::POW) {
        skipToken();
        processM();
        rpn.push_back(Token::POW);
    }
}

// E -> number | x | y | z | Func | ( F )
void RParser::processE() {  // Process Elementary formula
    // printf("Process Elementary formula\n");
    Token t = peekToken();
    if (
        t.token == Token::NUMBER ||
        t.token == Token::X ||
        t.token == Token::Y ||
        t.token == Token::Z
    ) {
        skipToken();
        rpn.push_back(t);
    } else if (t.token == Token::NAME) {
        processFunc();
    } else if (t.token == Token::LPAR) {
        skipToken();
        processF();
        skipToken(Token::RPAR);
    } else {
        throw ParserException("Syntax error (incorrect elementary formula)");
    }
}

// func -> name ( Args )
void RParser::processFunc() {   // Process function call
    // printf("Process Function\n");
    Token t = peekToken();
    if (t.token != Token::NAME) 
        throw ParserException("Syntax error (incorrect function call)");
    skipToken();
    skipToken(Token::LPAR);
    processArgs();    
    skipToken(Token::RPAR);
    rpn.push_back(t);           // Function call
}

// Args -> eps | ArgList
void RParser::processArgs() {
    // printf("Process Function Args\n");
    Token t = peekToken();
    if (t.token == Token::RPAR)
        return;
    processArgList();
}   

// ArgList -> F ArgListTail
void RParser::processArgList() {
    // printf("Process Function Arg List\n");
    processF();
    processArgListTail();
}

// ArgListTail -> eps | , F ArgListTail
void RParser::processArgListTail() {  // Process tail of arg. list
    // printf("Process Tail of Function Arg List\n");
    Token t = peekToken();
    if (t.token == Token::CM) {
        skipToken();
        processF();
        processArgListTail();
    }
}

void RParser::initialize(const std::string& str) {
    rpn.clear();
    input = str;
    input += "$";
    tokenPos = 0;
    
    const char *txt = input.c_str();
    setInputBuffer(txt);
    
    tokens.clear();
    while (true) {
        int lextype = yylex();
        // printf("Lexeme: %d\n", lextype);
        Token t(lextype, yylval.name, yylval.number);
        tokens.push_back(t);
        if (lextype == Token::ENDLINE)
            break;
    }

    releaseInputBuffer();
}

Token RParser::peekToken() {
    if (tokenPos >= int(tokens.size()))
        throw ParserException("Lexer error");
    return tokens[tokenPos];
}

void RParser::popToken() {
    if (tokenPos >= int(tokens.size()))
        throw ParserException("Lexer error");
    ++tokenPos;
}

// typedef double (FuncPtr*)(double);
// typedef double (FuncPtr2*)(double);

class FuncDef {
public:
    const char* name;
    double (*f1)(double);
    double (*f2)(double, double);
    int numArgs;

    FuncDef(
        const char* n = 0,
        double (*fp1)(double) = 0, 
        double (*fp2)(double, double) = 0,
        int nArgs = 1
    ):
        name(n),
        f1(fp1),
        f2(fp2),
        numArgs(nArgs)
    {}
};

const FuncDef FUNC_TABLE[] = {
    {"sin", &sin, 0, 1},
    {"cos", &cos, 0, 1},
    {"exp", &exp, 0, 1},
    {"log", &log, 0, 1},
    {"pow", 0, &pow, 2},
    {"sqrt", &sqrt, 0, 1},
    {"abs", &fabs, 0, 1},
    {"fabs", &fabs, 0, 1},
    {"atan", &atan, 0, 1},
    {"atan2", 0, &atan2, 2},
    {0, 0, 0, 0}
};

const FuncDef* findFunc(const string& name) {
    const FuncDef* f = FUNC_TABLE;
    while (true) {
        if (strcmp(name.c_str(), f->name) == 0)
            return f;
        ++f;
    }
    return 0;
}

double RParser::evaluate(double x, double y, double z) const {
    deque<double> stack;
    double a, b, c;
    for (size_t i = 0; i < rpn.size(); ++i) {
        const Token& t = rpn[i];
        switch (t.token) {
        case Token::NUMBER:
            stack.push_back(t.value);
            break;
        case Token::X:
            stack.push_back(x);
            break;
        case Token::Y:
            stack.push_back(y);
            break;
        case Token::Z:
            stack.push_back(z);
            break;
        case Token::NAME: 
        {
            const FuncDef* f = findFunc(t.text);
            if (f == 0)
                throw ParserException("Undefined function");
            int n = f->numArgs;
            if (n == 1) {
                a = stack.back(); stack.pop_back();
                b = (*(f->f1))(a);
                stack.push_back(b);
            } else if (n == 2) {
                b = stack.back(); stack.pop_back();
                a = stack.back(); stack.pop_back();
                c = (*(f->f2))(a, b);
                stack.push_back(c);
            } else {
                assert(false);
            }
            break;
        }
        case Token::PLUS:
            b = stack.back(); stack.pop_back();
            a = stack.back(); stack.pop_back();
            stack.push_back(a + b);
            break;
        case Token::MINUS:
            b = stack.back(); stack.pop_back();
            a = stack.back(); stack.pop_back();
            stack.push_back(a - b);
            break;
        case Token::MUL:
            b = stack.back(); stack.pop_back();
            a = stack.back(); stack.pop_back();
            stack.push_back(a * b);
            break;
        case Token::DIV:
            b = stack.back(); stack.pop_back();
            a = stack.back(); stack.pop_back();
            stack.push_back(a / b);
            break;
        case Token::POW:
            b = stack.back(); stack.pop_back();
            a = stack.back(); stack.pop_back();
            stack.push_back(pow(a, b));
            break;
        }
    }
    return stack.back();
}