/*
   translate.c
   Translates prefix expressions to infix and postfix using
   an expression tree (Standish exercises 9.6.3 and 9.6.4).
   
   A solution to CS 12 assignment 4, part 2, Fall 2008.
   
   Original from Standish instructor resources (modified by cmc, 11/11/08).
*/

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

/* use this structure to represent a tree node - DO NOT CHANGE */
typedef struct NodeTag {
    char symbol;
    struct NodeTag *left;
    struct NodeTag *right;
} Node;

/* mandatory functions to implement below main - DO NOT CHANGE */
Node *createTree(char *prefixString);
void printInfix(Node *tree);
void printPostfix(Node *tree);
void freeTree(Node *tree);

/* DO NOT CHANGE main either */
int main(void) {
    /* some example prefix expressions */
    char *s[] = { "+xy",
                  "-*abc",
                  "/-^b2**4ac*2a",
                  "**+ag+bc*++cd+de++efg",
                  "/^2+a*bc-e-fg",
                  "/^2*a^bc--ehg",
                  "/^2*a^bc//xy/hg" };                  
    int i, n = (sizeof s) / sizeof(char *);

    Node *tree;

    for (i = 0; i < n; i++) {
        printf(" prefix: %s\n",s[i]);
        tree = createTree(s[i]);     /* using createTree(char *prefixString) */
        printf("  infix: ");
        printInfix(tree);            /* using printInfix(Node *tree) */
        printf("\npostfix: ");
        printPostfix(tree);          /* using printPostfix(Node *tree) */
        printf("\n\n");
        freeTree(tree);              /* using freeTree(Node *tree) */
    }

    return 0;
}

/* SOLUTION HERE */

/* declare recursive function used by createTree */
Node *prefixStringToTree(char **);

/* createTree just passes string address to recursive function */
Node *createTree(char *prefixString) {
    return prefixStringToTree(&prefixString);
}

/* utility to identify an operator */
int isOperator(char c) {
    return c == '+' || c == '-' || c == '*' ||
           c == '/' || c == '^';
}

/* recursive function used by createTree */
Node *prefixStringToTree(char **s) {
    char c = *(*s)++; /* extract next character from string s
                         and postincrement char pointer (*s)  */
    Node *node = (Node *) malloc(sizeof(Node));
    node->symbol = c;
    
    if (isOperator(c)) {
        node->left = prefixStringToTree(s);
        node->right = prefixStringToTree(s);
    }
    else {
        node->left = NULL;
        node->right = NULL;
    }
    
    return node;
}

/* declare recursive function and enum used by printInfix */
typedef enum { LEFT, RIGHT } Side;
void printSubtree(Node *, char, Side);

/* not recursive - but calls recursive function
   to print left and right subtrees */
void printInfix(Node *tree) {
    if (tree != NULL) {
        if ( isOperator(tree->symbol) ) {
            printSubtree(tree->left,tree->symbol, LEFT);
            putchar(tree->symbol);
            printSubtree(tree->right,tree->symbol, RIGHT);
        }
        else
            putchar(tree->symbol);
    }
}

/* utility defines precedence of operators & "atoms" */
int precedence(char c) {
    switch (c) {
        case '^':
            return 3;
        case '*': case '/':
            return 2;
        case '+': case '-':
            return 1;
        default : /* an atom: i.e., operand in this case */
            return 4;
    }
}

/* recursive function to print a subtree;
   parentSymbol is the symbol above and to the right of subtree tree;
   different rules apply to left and right sides */
void printSubtree(Node *tree, char parentSymbol, Side side) {
    if (tree == NULL)
        ; /* print nothing */
    else if ( !isOperator(tree->symbol) )
        putchar(tree->symbol);
    else {

        int needParens;
        if (side == LEFT)
            needParens  = precedence(tree->symbol) < precedence(parentSymbol);

        else /* side == RIGHT: more complicated */
            needParens = precedence(tree->symbol) < precedence(parentSymbol) ||
            ( precedence(tree->symbol) == precedence(parentSymbol) &&
               ( !( tree->symbol == parentSymbol &&
                    ( parentSymbol == '+' || parentSymbol == '*')
                  )
               )
            );

        if (needParens)
            putchar('(');

        printSubtree(tree->left,tree->symbol, LEFT);
        putchar(tree->symbol);
        printSubtree(tree->right,tree->symbol, RIGHT);

        if (needParens)
            putchar(')');
    }
}

/* recursive function prints postfix form all by itself */
void printPostfix(Node *tree) {
    if (tree != NULL) {
        printPostfix(tree->left);
        printPostfix(tree->right);
        putchar(tree->symbol);
    }
}

/* recursively frees children, then self */
void freeTree(Node *tree) {
    if (tree != NULL) {
        freeTree(tree->left);
        freeTree(tree->right);
        free(tree);
    }
}