// Arup Guha
// 3/13/2024
// Solution to COP 3502H Exam 2 Question 7

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

typedef struct exprnode {
    double x; // value if value is stored.
    char op; // operator if operator is stored.
    struct exprnode* left;
    struct exprnode* right;
} exprnode;

double eval(exprnode* root);
exprnode* makeNum(double n);
exprnode* makeOp(char ch, exprnode* first, exprnode* second);
void freetree(exprnode* root);

int main() {

    // Build an expression tree!
    exprnode* n1 = makeNum(3.0);
    exprnode* n2 = makeNum(4.0);
    exprnode* n3 = makeNum(5.0);
    exprnode* add = makeOp('+', n1, n2);
    exprnode* mult = makeOp('*', add, n3);
    exprnode* n4 = makeNum(2.0);
    exprnode* top = makeOp('-',mult,n4);
    exprnode* n5 = makeNum(2.5);
    exprnode* n6 = makeNum(2.0);
    exprnode* five = makeOp('*', n5, n6);
    exprnode* root = makeOp('/',top, five);

    // Ta da!
    printf("%lf\n", eval(root));

    freetree(root);
    return 0;
}

// Returns the value of the expression rooted at root.
double eval(exprnode* root) {

    // Leaf node, return the value stored in it.
    if (root->left == NULL && root->right == NULL)
        return root->x;

    // Recursively evaluate left nad right.
    double leftVal = eval(root->left);
    double rightVal = eval(root->right);

    // Perform the appropriate operation and return.
    if (root->op == '+') return leftVal+rightVal;
    if (root->op == '-') return leftVal-rightVal;
    if (root->op == '*') return leftVal*rightVal;
    return leftVal/rightVal;
}

// Makes a node storing n.
exprnode* makeNum(double n) {
    exprnode* tmp = malloc(sizeof(exprnode));
    tmp->x = n;
    tmp->left = NULL;
    tmp->right = NULL;
    return tmp;
}

// Makes a node with operator ch, expression pointed to by first and expression pointed to by second.
exprnode* makeOp(char ch, exprnode* first, exprnode* second) {
    exprnode* tmp = malloc(sizeof(exprnode));
    tmp->op = ch;
    tmp->left = first;
    tmp->right = second;
    return tmp;
}

void freetree(exprnode* root) {
    if (root == NULL) return;
    freetree(root->left);
    freetree(root->right);
    free(root);
}