/*
   translate.c
   Translates prefix expressions to infix and postfix using
   an expression tree (Standish exercises 9.6.3 and 9.6.4).
   
   YOUR NAME AND THE DATE HERE
*/

#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 */