/* Mathematics Parser
 * By Richard Ye
 * Group members: Theodor Belair, Bence Meszaros
 *
 * Given a mathematical expression as a string, this will find the answer
 * to the expression as an numerical value.
 * 
 * KNOWN BUG: multiple divisions in a row, like 5/5/5/5, gives unexpected results.
 * 
 * Written on May 5, 2010. Public Domain.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#define MAX_INPUT_LENGTH 250
using namespace std;

typedef struct frac {
    int num;    //Numerator
    int den;    //Denominator
};

typedef struct term {
    char op; //Opeator
    int num;    //Numerator
    int den;    //Denominator
    term * next; //Pointer to next term
};

typedef struct expressionlog {
    char input[MAX_INPUT_LENGTH];
    frac answer;
    expressionlog *next;
};

bool isNumber(char character) {
    return (character > 47 && character < 58);
}

bool isOperator(int character) {
    return (character == '*' || character == '/' || character == '+' || character == '-');
}

int ctoi(char character) {
    return (character - '0');
}

template <class T>
inline T ABS (T a) { return a < 0 ? -a : a; }

int GCD(int a, int b) {
    int t;
    while (b) {
        t=a;
        a=b;
        b=t%b;
    }    
    return ABS(a);
}

inline int LCM(int a, int b) {
    return ABS(a*b) / GCD(a, b);
}

void printTerms(term * firstterm) {
    term * currterm = firstterm;
    do {
        printf("num: %i ", currterm->num);
        printf("den: %i ", currterm->den);
        printf("op: %c \n", currterm->op);
        currterm = currterm->next;
    } while(currterm != '\0');
}

void printFrac(frac * outFrac) {
    printf("%i/%i",outFrac->num, outFrac->den);
}

frac simplifyFrac(frac input) {
    int gcd = GCD(input.num, input.den);
    frac output;
    output.num = input.num / gcd;
    output.den = input.den / gcd;
    return output;
}

frac evalMathList(term *firstterm) {
    term * currterm = firstterm;
    term * lastterm = '\0';
    int fgcl, flcm;
    frac answer;
    answer.den = 1;
    answer.num = 0;
    frac eanswer;
    eanswer.den = -1;
    //We shall now iterate through the linked list, evaluating the results of the terms
    
    //Following order of operations; division and multiplication is done first
    do {
        if(currterm->den == 0) {
            printf("Error: cannot divide by zero.\n");
            return eanswer;
        }
        if(currterm->op == '*') {
            currterm->num *= lastterm->num;
            currterm->den *= lastterm->den;
            currterm->op = '+';
            lastterm->num = 0;
            lastterm->den = 1;
        }
        else if(currterm->op == '/') {
            if(currterm->num == 0) {
                printf("Error: cannot divide by zero.\n");
                return eanswer; 
            }
            currterm->num *= lastterm->den;
            currterm->den *= lastterm->num;
            currterm->op = '+';
            lastterm->num = 0;
            lastterm->den = 1;
        }
        lastterm = currterm;
        currterm = currterm->next;
    } while(currterm != '\0');
    
    currterm = firstterm;
    lastterm = '\0';
    
    //Do addition and subtraction
    do {
        if(currterm->op == '-') {
            flcm = LCM(answer.den, currterm->den);
            answer.num *= flcm / answer.den;
            currterm->num *= flcm / currterm->den;
            currterm->den = answer.den = flcm;
            answer.num -= currterm->num;
        }
        else if(currterm->op == '+') {
            flcm = LCM(answer.den, currterm->den);
            answer.num *= flcm / answer.den;
            currterm->num *= flcm / currterm->den;
            currterm->den = answer.den = flcm;
            answer.num += currterm->num;
        }
        lastterm = currterm;
        currterm = currterm->next;
    } while(currterm != '\0');
    
    return simplifyFrac(answer);
}

frac mathEval(char * input, int roffset) {
    //printf("Evaluating %s... \n", input);
    
    int inputlen = strlen(input);
    int numterms = 1;
    int bracketdepth = 0;
    /*
    character codes:
        1 = number
        2 = operator
        3 = (
        4 = )
    */
    int lastchartype = 2;
    
    term terms; //Terms linked list
    terms.next = '\0';
    terms.op = '+';
    terms.num = 0;
    terms.den = 0;
    term *currterm = &terms;    //Pointer to current term
    term *firstterm = &terms;   //Pointer to first term
    
    bool useden = false;    //Whether to add to numerator or denominator
    bool isneg = false;     //Whether the current term is negative or not
    bool bracket = false;   //Whether brackets are used in the expression
    char bstring[MAX_INPUT_LENGTH]; //The parser is recursive; this is the string inside brackets
    int bstart = 0; //Starting position of outer-most bracket
    frac bracketresult;     //Answer of bracket recursion
    frac bfrac; //The error return value
    bfrac.den = -1;
    
    for(int i = 0; i < inputlen; i++) {
        if(isNumber(input[i])) {
            if(bracketdepth == 0) {
                if(lastchartype == 4) {
                    //Last character is a close bracket. Assume multiplication; create a new term
                    if(useden == false)
                        currterm->den = 1;
                    
                    useden = false;
                    isneg = false;
                    currterm->next = new term;
                    currterm = currterm->next;
                    currterm->num = 0;
                    currterm->den = 0;
                    currterm->op = '*';
                    currterm->next = '\0';
                }
                else if(lastchartype != 2 && lastchartype != 1 && lastchartype != 3) {
                    printf("Error: Unexpected number '%c' at position %i.\n", input[i], i+roffset);
                    return bfrac;
                }
                
                //This code mathematically appends an integer to a number
                if(useden == true) {
                    currterm->den *= 10;
                    if(isneg == true) {
                        currterm->den -= ctoi(input[i]);
                    }
                    else {
                        currterm->den += ctoi(input[i]);
                    }
                }
                else {
                    currterm->num *= 10;
                    if(isneg == true) {
                        currterm->num -= ctoi(input[i]);
                    }
                    else {
                        currterm->num += ctoi(input[i]);
                    }
                }
                
                //Toggle negativity
                if((isneg == true && currterm->num > 0) || (isneg == false && currterm->num < 0))
                    currterm->num *= -1;
                
                lastchartype = 1;
            }
        }
        else if(isOperator(input[i])) {
            if(bracketdepth == 0) {
                //Negative sign enountered
                if(lastchartype == 2 && input[i] == '-') {
                    isneg = !isneg;
                    continue;
                }
                else if(lastchartype != 1 && lastchartype != 4) {
                    printf("Error: Unexpected operator '%c' at position %i.\n", input[i], i+roffset);
                    return bfrac;
                }
                
                if(input[i] == '/' && useden == false) {
                    //Slash means a fraction
                    useden = true;
                }
                
                else {
                    if(useden == false)
                        currterm->den = 1;
                    
                    //New term created, create new node
                    useden = false;
                    isneg = false;
                    currterm->next = new term;
                    currterm = currterm->next;
                    currterm->num = 0;
                    currterm->den = 0;
                    currterm->op = input[i];
                    currterm->next = '\0';
                }
                
                lastchartype = 2;
            }
        }
        else if(input[i] == '(') {
            if((lastchartype == 1 || lastchartype == 4) && bracketdepth == 0) {
                if(useden == false)
                    currterm->den = 1;
                
                //Assuming nultiplcation for a number followed by a bracket; create a new term
                useden = false;
                isneg = false;
                currterm->next = new term;
                currterm = currterm->next;
                currterm->num = 0;
                currterm->den = 0;
                currterm->op = '*';
                currterm->next = '\0';
            }
            
            bracket = true;
            bracketdepth++;
            
            if(bracketdepth == 1)
                bstart = i;
            
            lastchartype = 3;
        }
        else if(input[i] == ')') {
            if(bracketdepth <= 0) {
                printf("Error: Unexpected bracket ')' at position %i.\n", i+roffset);
                return bfrac;
            }
            lastchartype = 4;
            bracketdepth--;
            
            if(bracketdepth == 0) {
                strncpy(bstring, input+bstart+1, i-bstart-1);
                bstring[i-bstart-1] = '\0';
                bfrac = mathEval(bstring, bstart+2);
                //printFrac(&bfrac);
                if(useden == true) {
                    currterm->den = bfrac.num;
                    currterm->num *= bfrac.den;
                }
                else {
                    currterm->den = bfrac.den;
                    currterm->num = bfrac.num;
                }
            }
        }
        else if(bracketdepth <= 0) {
            printf("Warning: Unknown character '%c' at position %i.\n", input[i], i+roffset);
        }
    }
    if(useden == false) {
        currterm->den = 1;
    }
    
    //if(roffset == 0)
    //    printTerms(firstterm);
    
    //printf("done.\n");
    return evalMathList(firstterm);
}

void printHistory(expressionlog *firstnode) {
    expressionlog *currnode = firstnode;
    if(currnode->next == '\0')
        return;
    printf("Printing history:\n");
    while(currnode->next != '\0') {
        if(currnode->answer.den != 1)
            printf("%s = %i/%i\n", currnode->input, currnode->answer.num, currnode->answer.den);
        else
            printf("%s = %i\n", currnode->input, currnode->answer.num);
        currnode = currnode->next;
    }
}

int main() {
    char userinput[MAX_INPUT_LENGTH] = "";
    expressionlog history;
    expressionlog *currhist = &history; 
    history.next = '\0';
    frac answer;
    
    printf("Mathematics Parser version 0.1, by Richard Ye, Bence Meszaros, Theodor Belaire.\nThis is Richard's version. "
        "Type \\help for help.\nType any valid mathematical expression, using 0-9, +, -, *, /, (, ).\n");
    while(1) {
        printf("> ");
        scanf("%s", &userinput);
        if(!strcmp(userinput, "\\exit"))
            break;
            
        if(!strcmp(userinput, "\\help")) {
            printf("Help:\nThis calculator follows general mathmatical rules, such as order of operations. "
                "Some examples of valid expressions are:\n"
                " - 2-7\n - 6/5+3/2\n - 5+8(7)\n - (7+6)(5+1)\n\nType \\exit to quit the program and print history.\n\n");
            continue;
        }    
        
        answer = mathEval(userinput, 1);
        if(answer.den >= 0) {
            strcpy(currhist->input, userinput);
            currhist->answer.den = answer.den;
            currhist->answer.num = answer.num;
            currhist->next = new expressionlog;
            currhist = currhist->next;
            currhist->next = '\0';
            
            if(answer.den != 1) {
                printf(" =%i/%i\n", answer.num, answer.den);
            }
            else
                printf(" =%i\n", answer.num);
        }
        else
            break;
    }
    
    printHistory(&history);
    
    system("pause");
    
    return 0;
}