// Expression = Term | Term + Expression
// Term ::= Number | Number * Term
// The above two grammar defines a right to left associativity

// vc2010, cl expressionParsingAndEvaluation.cpp
// G++4.8.1, g++ expressionParsingAndEvaluation.cpp -o expressionParsingAndEvaluation.exe

#include <stdio.h>
#include <stdlib.h>

enum TNodeType {Expression=0, Term, Number};

struct TNode
{
    TNodeType type;
    float param;
    struct TNode *left, *right;
};

int processExpression(struct TNode **expression);
int processTerm(struct TNode **term);
int processNumber(struct TNode **number);

struct TNode *allocTNode(TNodeType type);
void printNode(struct TNode *node);
void inorderPrint(struct TNode *node);
void printTree(struct TNode *node);
void freeTree(struct TNode *node);


int main()
{
    float value;
    struct TNode *expression;

    value = processExpression(&expression);
    printf("The result is %f\n", value);
    printTree(expression);
    freeTree(expression);

    return 0;
}


int processExpression(struct TNode **expression)
{
    float leftValue, rightValue;
    char oper = ' ';

    *expression = allocTNode(Expression);
    leftValue = processTerm(&(*expression)->left);
    while (oper == ' ')
        oper = getchar();
    if (oper == '+')
        rightValue = processExpression(&(*expression)->right);
    else // oper == '\n'
        rightValue = 0;

    return leftValue + rightValue;
}


int processTerm(struct TNode **term)
{
    float leftValue, rightValue;
    char oper = ' ';

    *term = allocTNode(Term);
    leftValue = processNumber(&(*term)->left);
    while (oper == ' ')
        oper = getchar();
    if (oper == '*')
        rightValue = processTerm(&(*term)->right);
    else // oper == '+' or oper == '\n'
    {
        rightValue = 1;
        ungetc(oper, stdin);
    }

    return leftValue * rightValue;
}


int processNumber(struct TNode **number)
{
    *number = allocTNode(Number);
    scanf("%f", &(*number)->param);
    return (*number)->param;
}


struct TNode *allocTNode(TNodeType type)
{
    struct TNode *ptr = (struct TNode *) malloc(sizeof(struct TNode));
    ptr->type = type;
    ptr->left = ptr->right = 0;
    return ptr;
}


void printNode(struct TNode *node)
{
    static int order=0;
    const char *nodeLabels[] = {"Expression", "Term", "Number %.2f"};
    if (order++ > 0)
        printf(", ");
    if (order%5 == 0)
        printf("\n   ");
    printf(nodeLabels[node->type], node->param);
}


void inorderPrint(struct TNode *node)
{
    if (node->left)
        inorderPrint(node->left);
    printNode(node);
    if (node->right)
        inorderPrint(node->right);
}


void printTree(struct TNode *node)
{
    printf("\nInorder: ");
    inorderPrint(node);
    printf("\n");
}


void freeTree(struct TNode *node)
{
    if (node->left)
        freeTree(node->left);
    if (node->right)
        freeTree(node->right);
    free(node);
}


/*

3*4*5+6*7+8+9*10
The result is 200.000000

Inorder: Number 3.00, Term, Number 4.00, Term,
   Number 5.00, Term, Expression, Number 6.00, Term,
   Number 7.00, Term, Expression, Number 8.00, Term,
   Expression, Number 9.00, Term, Number 10.00, Term,
   Expression



3 * 4 * 5 + 6 * 7 + 8 + 9
The result is 119.000000

Inorder: Number 3.00, Term, Number 4.00, Term,
   Number 5.00, Term, Expression, Number 6.00, Term,
   Number 7.00, Term, Expression, Number 8.00, Term,
   Expression, Number 9.00, Term, Expression

*/