BSTManupulation

//insert value to BST
//findPath of a number in BST
//Find Minimum value in BST
//Find Maximum value in BST
//Find Height of BST
//Pre Order Traversal
//Post Order Traversal
//In Order Traversal
//Level Order Traversal
//Find if a Tree in BST
//Delete Node in BST
//Get Successor in BST
//Get Predecessor in BST

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

typedef struct Node Node;

#define CHAR_BIT 8

struct BSTNode {
    int data;
    struct BSTNode* left;
    struct BSTNode* right;
};

/*Function to find minimum of x and y*/
//http://www.geeksforgeeks.org/compute-the-minimum-or-maximum-max-of-two-integers-without-branching/
//http://en.cppreference.com/w/cpp/language/operators

int min(int x, int y) {
    return y + ((x - y) & ((x - y) >>
            (sizeof (int) * CHAR_BIT - 1)));
}

/*Function to find maximum of x and y*/
int max(int x, int y) {
    return x - ((x - y) & ((x - y) >>
            (sizeof (int) * CHAR_BIT - 1)));
}

struct Node {
    struct BSTNode* data;
    struct Node* next;
};

void enqueue(struct Node** front, struct Node** rear, struct BSTNode* x) {
    struct Node* temp = malloc(sizeof (struct Node));

    temp->data = x;
    temp->next = NULL;

    if (*front == NULL && *rear == NULL) {
        *front = *rear = temp;
        return;
    }

    (*rear)->next = temp;
    *rear = temp;
}

void dequeue(struct Node** front, struct Node** rear) {
    struct Node* temp = *front;

    if (front == NULL) {
        printf("Queue is empty, no dequeue possible");
        return;
    }

    if (*front == *rear) {
        *front = *rear = NULL;
    } else
        *front = (*front)->next;
    free(temp);
}

struct BSTNode* frontValue(struct Node** front) {
    if (*front == NULL) {
        printf("No node in the list\n");
        return;
    }

    return (*front)->data;
}

bool isEmpty(struct Node** rear) {
    if (*rear == NULL) return true;
    return false;
}

void print(struct Node* front) {
    while (front != NULL) {
        printf("%d ", front->data);
        front = front->next;
    }
    printf("\n");
}

struct BSTNode* getNewNode(int x) {
    struct BSTNode* newNode = malloc(sizeof (struct BSTNode));

    newNode->data = x;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

void insertBST(struct BSTNode** root, int x) {
    if (*root == NULL) {
        struct BSTNode* temp = getNewNode(x);
        *root = temp;
        return;
    }
    if (x <= (*root)->data) insertBST(&((*root)->left), x);
    else insertBST(&((*root)->right), x);
}

void insertNoNBST(struct BSTNode** root, int x) {
    if (*root == NULL) {
        struct BSTNode* temp = getNewNode(x);
        *root = temp;
        return;
    }
    insertNoNBST(&((*root)->left), x);
}

bool search(struct BSTNode** root, int x) {
    if (*root == NULL) return false;
    else if (x == (*root)->data) return true;
    else if (x < (*root)->data)
        search(&((*root)->left), x);
    else if (x > (*root)->data)
        search(&((*root)->right), x);

    return false;
}

struct BSTNode* find(struct BSTNode*root, int data) {
    if (root == NULL) return NULL;
    else if (root->data == data) return root;
    else if (root->data < data) return find(root->right, data);
    else return find(root->left, data);
}

int g = 0;

void searchFindPath(struct BSTNode** root, int x, char* path) {

    if (*root == NULL) {
        if (g == 0)
            strcpy(path, "Its a Empty tree");
        else
            strcpy(path, "Value not found");
        return;
    } else if (x == (*root)->data) {

        g = 1;
        return;
        //        strcat(path, "root");
    } else if (x < (*root)->data) {
        strcat(path, "-> Left ");
        g = 1;
        searchFindPath(&((*root)->left), x, path);
    } else if (x > (*root)->data) {
        strcat(path, "-> Right ");
        g = 1;
        searchFindPath(&((*root)->right), x, path);
    }
}

void findMinimumValue(struct BSTNode** root, char* minValue) {

    if (*root == NULL) {

        return;
    } else if ((*root)->left != NULL)
        findMinimumValue(&((*root)->left), minValue);
    else {
        itoa(((*root)->data), minValue, 10);
    }
}

void findMaximumValue(struct BSTNode** root, char* maxValue) {

    if (*root == NULL) {
        return;
    } else if ((*root)->right != NULL)
        findMaximumValue(&((*root)->right), maxValue);
    else {
        itoa(((*root)->data), maxValue, 10);
    }
}

int findHeight(struct BSTNode** root) {


    if (*root == NULL) return -1;
    int leftDepth = findHeight(&((*root)->left));
    int rightDepth = findHeight(&((*root)->right));

    return (max(leftDepth, rightDepth) + 1);
}

void preOrderTraversal(struct BSTNode** root) {
    if (*root == NULL) return;
    printf("%d ", (*root)->data);
    preOrderTraversal(&((*root)->left));
    preOrderTraversal(&((*root)->right));
}

void inOrderTraversal(struct BSTNode** root) {
    if (*root == NULL) return;
    inOrderTraversal(&((*root)->left));
    printf("%d ", (*root)->data);
    inOrderTraversal(&((*root)->right));
}

void postOrderTraversal(struct BSTNode** root) {
    if (*root == NULL) return;
    postOrderTraversal(&((*root)->left));
    postOrderTraversal(&((*root)->right));
    printf("%d ", (*root)->data);
}

void levelOrderTraversal(struct BSTNode** root) {
    struct Node* front = NULL;
    struct Node* rear = NULL;

    if (*root == NULL) return;
    enqueue(&front, &rear, *root);
    while (!isEmpty(&rear)) {
        struct BSTNode* current = frontValue(&front);
        printf("%d ", current->data);
        if (current->left != NULL) enqueue(&front, &rear, current->left);
        if (current->right != NULL) enqueue(&front, &rear, current->right);

        dequeue(&front, &rear);
    }

}

bool isBinarySearchTree(struct BSTNode** root, int *temp, int *g) {
    if (*root == NULL) {
        return;
    }

    if (*g == 0) return false;

    isBinarySearchTree(&((*root)->left), temp, g);


    if (*temp > (*root)->data) {
        *g = 0;
        return false;
    }

    //    printf("temp before assigning: %d\n", *temp);
    *temp = (*root)->data;
    //    printf("temp after assigning: %d\n\n", *temp);

    isBinarySearchTree(&((*root)->right), temp, g);
    return true;
}

struct BSTNode* findMin(struct BSTNode *root) {
    if (root == NULL) return NULL;
    while (root->left != NULL) root = root->left;
    return root;
}

struct BSTNode* findMax(struct BSTNode *root) {
    if (root == NULL) return NULL;
    while (root->right != NULL) root = root->right;
    return root;
}

struct BSTNode* deleteNode(struct BSTNode* root, int x) {
    if (root == NULL) return;
    else if (x < root->data)
        root->left = deleteNode(root->left, x);
    else if (x > root->data)
        root->right = deleteNode(root->right, x);
    else if (x == root->data) {
        if (root->left == NULL && root->right == NULL) {

            free(root);
            root = NULL;
        } else if (root->left == NULL && root->right != NULL) {
            struct BSTNode* temp = root;
            root = root->right;
            free(temp);
        } else if (root->right == NULL && root->left != NULL) {
            struct BSTNode* temp = root;
            root = root->left;
            free(temp);
        } else {
            struct BSTNode* temp = findMin(root->right);
            root->data = temp->data;
            root->right = deleteNode(root->right, temp->data);
        }
    }
    return root;
}

void inorderSuccessor(struct BSTNode* root, int x, int *previousLeftTraversal, int *hasLeftTraversed) {



    if (root == NULL) return;
    else if (x < root->data) {
        *previousLeftTraversal = root->data;
        *hasLeftTraversed = 1;
        inorderSuccessor(root->left, x, previousLeftTraversal, hasLeftTraversed);
    } else if (x > root->data) {
        //        *previousLeftTraversal = root->data;
        inorderSuccessor(root->right, x, previousLeftTraversal, hasLeftTraversed);
    } else if (x == (root)->data) {
        printf("found %d\n", x);


        if (root->right != NULL) {
            printf("Successor of %d is %d\n", x, (findMin(root->right))->data);

        } else if (*hasLeftTraversed == 0 && root->right == NULL) {
            printf("%d is the highest value in the tree, no successor\n", x);
        } else if (root->right == NULL) {
            printf("Successor of %d is %d\n", x, *previousLeftTraversal);
            //            printf("parent value: %d\n", *parentValue);
            //            printf("Current value: %d\n", root->data);
        }
    }
    return;
}

struct BSTNode* getSuccessor(struct BSTNode* root, int data) {
    struct BSTNode* current = find(root, data);
    if (current == NULL) return NULL;
    if (current->right != NULL) {
        return findMin(current->right);
    } else {
        struct BSTNode* successor = NULL;
        struct BSTNode* ancestor = root;

        while (ancestor != current) {
            if (current->data < ancestor->data) {
                successor = ancestor;
                ancestor = ancestor->left;
            } else
                ancestor = ancestor->right;
        }
        return successor;
    }
}

struct BSTNode* getPredecessor(struct BSTNode* root, int data) {
    struct BSTNode* current = find(root, data);

    if (current == NULL) return NULL;
    if (current->left != NULL) {
        return findMax(current->left);
    } else {
        struct BSTNode* predecessor = NULL;
        struct BSTNode* ancestor = root;

        while (ancestor != current) {
            if (current->data < ancestor->data) {
                ancestor = ancestor->left;
            } else {
                predecessor = ancestor;
                ancestor = ancestor->right;
            }
        }
        return predecessor;
    }
}

int main() {
    struct BSTNode* root = NULL;
    insertBST(&root, 15);
    insertBST(&root, 10);
    insertBST(&root, 20);
    insertBST(&root, 12);
    insertBST(&root, 8);
    insertBST(&root, 6);
    insertBST(&root, 11);
    insertBST(&root, 25);
    insertBST(&root, 27);
    insertBST(&root, 17);
    insertBST(&root, 16);

    //        insertNoNBST(&root, 6);
    //        insertNoNBST(&root, 4);
    //        insertNoNBST(&root, 10);
    //        insertNoNBST(&root, 2);
    //        insertNoNBST(&root, 5);
    //        insertNoNBST(&root, 7);
    //        insertNoNBST(&root, 11);
    //        insertNoNBST(&root, 1);
    //        insertNoNBST(&root, 3);
    //        insertNoNBST(&root, 9);
    //        insertNoNBST(&root, 8);

    //    int x = 12;
    //    char path[50] = "root ";
    //    search(&root, x, path);
    //    printf("Search result of record %d: %s\n", x, path);

    //    char s[50] = "This is a string";
    //    stringAsReference(s);
    //    printf("s: %s\n", s);
    //    char minValue[20] = "Empty tree";
    //    findMinimumValue(&root, minValue);
    //    printf("Minimum Value in the Tree: %s\n", minValue);
    //
    //
    //    char maxValue[20] = "Empty tree";
    //    findMaximumValue(&root, maxValue);
    //    printf("Maximum Value in the Tree: %s\n", maxValue);

    //    printf("Height of Tree: %d\n", findHeight(&root));
    //    preOrderTraversal(&root);
    //    inOrderTraversal(&root);

    //    levelOrderTraversal(&root);

    //    postOrderTraversal(&root);

    //    int temp = 0, g = 1;
    //    printf("\nisBinarySearchTree: %d\n", isBinarySearchTree((&root), &temp, &g));


    //    int x = 10;
    //
    //    root = deleteNode(root, x);

    int x = 16;
    //    int previousLeftTraversal = 0;
    //    int hasLeftTraversed = 0;

    //    inorderSuccessor(root, x, &previousLeftTraversal, &hasLeftTraversed);

        printf("Successor: %d\n", getSuccessor(root, x)->data);
    printf("Predecessor: %d\n", getPredecessor(root, x)->data);
    return (EXIT_SUCCESS);
}

InfixPrefixPostFix

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
//http://scanftree.com/Data_Structure/postfix-to-infix

typedef struct Node Node;

struct Node {
    int data;
    struct Node* next;
};

void push(struct Node** top, int x) {
    struct Node* temp = malloc(sizeof (struct Node));
    temp->data = x;
    temp->next = *top;
    *top = temp;
}

void pop(struct Node** top) {
    struct Node* temp = *top;
    *top = (*top)->next;
    free(temp);
}

bool isEmpty(struct Node** top) {
    if (*top == NULL) return true;
    else return false;
}

int topValue(struct Node** top) {
    return (*top)->data;
}

void print(struct Node** pointerToString) {
    struct Node* temp = *pointerToString;
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}



struct NodeChar {
    char data;
    struct NodeChar* next;
};

void pushChar(struct NodeChar** top, char x) {
    struct NodeChar* temp = malloc(sizeof (struct NodeChar));
    temp->data = x;
    temp->next = *top;
    *top = temp;
}

void popChar(struct NodeChar** top) {
    struct NodeChar* temp = *top;
    *top = (*top)->next;
    free(temp);
}

bool isEmptyChar(struct NodeChar** top) {
    if (*top == NULL) return true;
    else return false;
}

char topValueChar(struct NodeChar** top) {
    return (*top)->data;
}

void printChar(struct NodeChar** pointerToString) {
    struct NodeChar* temp = *pointerToString;
    while (temp != NULL) {
        printf("%c ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}



struct NodeString {
    char data[100];
    struct NodeString* next;
};

void pushString(struct NodeString** top, char* x) {
    struct NodeString* temp = malloc(sizeof (struct NodeString));
    strcpy(temp->data, x);
    temp->next = *top;
    *top = temp;
}

void popString(struct NodeString** top) {
    struct NodeString* temp = *top;
    *top = (*top)->next;
    free(temp);
}

bool isEmptyString(struct NodeString** top) {
    if (*top == NULL) return true;
    else return false;
}

char* topValueString(struct NodeString** top) {
    return (*top)->data;
}

void printString(struct NodeString** pointerToString) {
    struct NodeString* temp = *pointerToString;
    while (temp != NULL) {
        printf("%s ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}



int evaluate(int a, int b, char operator) {
    switch (operator) {
        case '/': return a / b;
        case '*': return a * b;
        case '+': return a + b;
        case '-': return a - b;
    }
}

// Function to verify whether a character is numeric digit. 
bool isOperand(char C) {
    if (C >= '0' && C <= '9') return true;
    if (C >= 'a' && C <= 'z') return true;
    if (C >= 'A' && C <= 'Z') return true;

    return false;
}

// Function to verify whether a character is operator symbol or not. 
bool isOperator(char C) {
    if (C == '+' || C == '-' || C == '*' || C == '/' || C == '$')
        return true;

    return false;
}

int isRightAssociative(char op) {
    if (op == '$') return true;
    return false;
}

int getOperatorWeight(char op) {
    int weight = -1;

    switch (op) {
        case '+':
        case '-':
            weight = 1;
            break;
        case '*':
        case '/':
            weight = 2;
            break;
        case '$':
            weight = 3;
            break;
    }
    return weight;
}

int hasHighterPrecedence(char op1, char op2) {
    int op1Weight = getOperatorWeight(op1);
    int op2Weight = getOperatorWeight(op2);

    if (op1Weight == op2Weight) {
        if (isRightAssociative(op1)) return false;
        else return true;
    }

    return op1Weight > op2Weight ? true : false;
}

int hasHighterPrecedenceInfixToPrefix(char op1, char op2) {
    int op1Weight = getOperatorWeight(op1);
    int op2Weight = getOperatorWeight(op2);

    if (op1Weight == op2Weight) {
        if (isRightAssociative(op1)) return true;
        else return false;
    }

    return op1Weight > op2Weight ? true : false;
}



void evaluatePostFix(char *expression) {
    struct Node* top = NULL;
    char * pch;
    int a, b;

    printf("Value of postfix expression %s = ", expression);
    //    printf("Splitting string \"%s\" into tokens:\n", expression);
    //    pch = strtok(expression, " ,.-");
    pch = strtok(expression, " ");
    while (pch != NULL) {
        //        printf("%s\n", pch);
        if ((strcmp(pch, "/") == 0) || (strcmp(pch, "*") == 0) || (strcmp(pch, "+") == 0) || (strcmp(pch, "-") == 0)) {
            b = topValue(&top);
            pop(&top);
            a = topValue(&top);
            pop(&top);

            //            printf("%d %d |%s|\n", b, a, pch);
            pch[1] = '\0';
            push(&top, evaluate(a, b, pch[0]));
        } else {
            push(&top, atoi(pch));
        }
        //        pch = strtok(NULL, " ,.-");
        pch = strtok(NULL, " ");
    }
    print(&top);
}

void evaluatePreFix(char *expression, int l) {
    struct Node* top = NULL;
    printf("Value of prefix expression %s = ", expression);

    int x = 0, y = 1, i, g = 0, a, b;

    for (i = l - 1; i >= 0; i--) {
        if (expression[i] == ' ' && g == 1) {
            //            printf("x: %d\n", x);
            push(&top, x);

            x = 0;
            y = 1;
            g = 0;
        } else if (isOperator(expression[i])) {
            //            printf("isOperator: %c\n", (expression[i]));
            a = topValue(&top);
            pop(&top);
            b = topValue(&top);
            pop(&top);
            push(&top, evaluate(a, b, expression[i]));
        } else if (isOperand(expression[i])) {
            x = x + (expression[i] - '0') * y;
            y = y * 10;
            g = 1;
        }
    }
    print(&top);
}

void infixToPostFix(char *infixExpression, char* postfixExpression, int l) {
    struct NodeChar* top = NULL;
    int i, j = 0;

    printf("InFix:   %s\n", infixExpression);
    for (i = 0; i < l; i++) {
        if (infixExpression[i] == ' ' || infixExpression[i] == ',') continue;

        else if (isOperator(infixExpression[i])) {
            while (!isEmptyChar(&top) && topValueChar(&top) != '(' && hasHighterPrecedence(topValueChar(&top), infixExpression[i])) {
                postfixExpression[j] = topValueChar(&top);

                postfixExpression[++j] = ' ';
                postfixExpression[++j] = '\0';
                popChar(&top);
            }
            pushChar(&top, infixExpression[i]);
        } else if (isOperand(infixExpression[i])) {
            //            int operand = 0;
            while (i < l && isOperand(infixExpression[i])) {
                postfixExpression[j] = infixExpression[i];

                j++;
                i++;
            }
            postfixExpression[j] = ' ';
            postfixExpression[++j] = '\0';
        } else if (infixExpression[i] == '(') {
            pushChar(&top, infixExpression[i]);
        } else if (infixExpression[i] == ')') {
            while (!isEmptyChar(&top) && topValueChar(&top) != '(') {
                postfixExpression[j] = topValueChar(&top);

                postfixExpression[++j] = ' ';
                postfixExpression[++j] = '\0';
                popChar(&top);
            }
            popChar(&top);
        }
    }

    while (!isEmptyChar(&top)) {
        postfixExpression[j] = topValueChar(&top);

        postfixExpression[++j] = ' ';
        postfixExpression[++j] = '\0';
        popChar(&top);
    }
    postfixExpression[++j] = '\0';
}

void infixToPreFix(char *infixExpression, char* prefixExpression, int l) {
    struct NodeChar* top = NULL;
    int i, j = 0;
    char temp;

    printf("InFix:   %s\n", infixExpression);
    for (i = 0; i < l / 2; i++) {
        temp = infixExpression[i];
        infixExpression[i] = infixExpression[(l - 1) - i];
        infixExpression[(l - 1) - i] = temp;
    }

    //    printf("InFix:   %s\n", infixExpression);
    for (i = 0; i < l; i++) {
        if (infixExpression[i] == ' ' || infixExpression[i] == ',') continue;

        else if (isOperator(infixExpression[i])) {
            while (!isEmptyChar(&top) && topValueChar(&top) != ')' && hasHighterPrecedenceInfixToPrefix(topValueChar(&top), infixExpression[i])) {
                prefixExpression[j] = topValueChar(&top);

                prefixExpression[++j] = ' ';
                prefixExpression[++j] = '\0';
                popChar(&top);
            }
            pushChar(&top, infixExpression[i]);
        } else if (isOperand(infixExpression[i])) {
            //            int operand = 0;
            while (i < l && isOperand(infixExpression[i])) {
                prefixExpression[j] = infixExpression[i];

                j++;
                i++;
            }
            prefixExpression[j] = ' ';
            prefixExpression[++j] = '\0';
        } else if (infixExpression[i] == ')') {
            pushChar(&top, infixExpression[i]);
        } else if (infixExpression[i] == '(') {
            while (!isEmptyChar(&top) && topValueChar(&top) != ')') {
                prefixExpression[j] = topValueChar(&top);

                prefixExpression[++j] = ' ';
                prefixExpression[++j] = '\0';
                popChar(&top);
            }
            popChar(&top);
        }
    }

    while (!isEmptyChar(&top)) {
        prefixExpression[j] = topValueChar(&top);

        prefixExpression[++j] = ' ';
        prefixExpression[++j] = '\0';
        popChar(&top);
    }
    prefixExpression[++j] = '\0';
    //    printf("prefixExpression length: %d\n", strlen(prefixExpression));

    l = strlen(prefixExpression);
    for (i = 0; i < l / 2; i++) {
        temp = prefixExpression[i];
        prefixExpression[i] = prefixExpression[(l - 1) - i];
        prefixExpression[(l - 1) - i] = temp;
    }
}

void postfixToInfix(char *postfixExpression, char *infixExpression) {
    struct NodeString* top = NULL;
    char temp[100] = "", c[4] = "";
    char lastStackValue[100] = "";
    char secondLastStackValue[100] = "";

    printf("postfixExpression: %s\n", postfixExpression);
    int i = 0, j = 0;

    for (i = 0; postfixExpression[i] != '\0'; i++) {
        if (postfixExpression[i] == ' ' || postfixExpression[i] == ',') continue;
        else if (isOperand(postfixExpression[i])) {
            strcpy(temp, "");
            j = 0;

            while (i < strlen(postfixExpression) && isOperand(postfixExpression[i])) {
                temp[j] = postfixExpression[i];
                temp[++j] = '\0';
                i++;
            }
            pushString(&top, temp);
        } else if (isOperator(postfixExpression[i])) {
            strcpy(temp, "");
            strcpy(lastStackValue, "");
            strcpy(secondLastStackValue, "");

            if (isEmptyString(&top)) {
                printf("No last value, invalid expression\n");
                return;
            }
            strcpy(lastStackValue, topValueString(&top));
            popString(&top);

            if (isEmptyString(&top)) {
                printf("No second last value, invalid expression\n");
                return;
            }
            strcpy(secondLastStackValue, topValueString(&top));
            popString(&top);


            strcat(temp, "( ");
            strcat(temp, secondLastStackValue);
            c[0] = ' ';
            c[1] = postfixExpression[i];
            c[2] = ' ';
            c[3] = '\0';
            strcat(temp, c);
            strcat(temp, lastStackValue);
            strcat(temp, " )");
            pushString(&top, temp);
        }
    }
    strcpy(infixExpression, topValueString(&top));
    //    printString(&top);
}

void prefixToInfix(char *prefixExpression, char *infixExpression) {
    struct NodeString* top = NULL;
    char temp[100] = "", c[4] = "";
    char lastStackValue[100] = "";
    char secondLastStackValue[100] = "";

    printf("prefixExpression: %s\n", prefixExpression);
    int i = 0, j = 0;

    for (i = (strlen(prefixExpression) - 1); i > -1; i--) {
        if (prefixExpression[i] == ' ' || prefixExpression[i] == ',') continue;
        else if (isOperand(prefixExpression[i])) {
            strcpy(temp, "");
            j = 0;

            while (i < strlen(prefixExpression) && isOperand(prefixExpression[i])) {
                temp[j] = prefixExpression[i];
                temp[++j] = '\0';
                i--;
            }
            pushString(&top, temp);
        } else if (isOperator(prefixExpression[i])) {
            strcpy(temp, "");
            strcpy(lastStackValue, "");
            strcpy(secondLastStackValue, "");

            if (isEmptyString(&top)) {
                printf("No last value, invalid expression\n");
                return;
            }
            strcpy(lastStackValue, topValueString(&top));
            popString(&top);

            if (isEmptyString(&top)) {
                printf("No second last value, invalid expression\n");
                return;
            }
            strcpy(secondLastStackValue, topValueString(&top));
            popString(&top);


            strcat(temp, "( ");
            strcat(temp, lastStackValue);
            c[0] = ' ';
            c[1] = prefixExpression[i];
            c[2] = ' ';
            c[3] = '\0';
            strcat(temp, c);
            strcat(temp, secondLastStackValue);
            strcat(temp, " )");
            pushString(&top, temp);
        }
    }
    strcpy(infixExpression, topValueString(&top));
    //    printString(&top);
}

//https://www.youtube.com/watch?v=mGnAuIA2DFU
void postfixToPrefix(char *postfixExpression, char *prefixExpression) {
    struct NodeString* top = NULL;
    char temp[100] = "", c[3] = "";
    char lastStackValue[100] = "";
    char secondLastStackValue[100] = "";

    printf("postfixExpression: %s\n", postfixExpression);
    int i = 0, j = 0;

    for (i = 0; postfixExpression[i] != '\0'; i++) {
        if (postfixExpression[i] == ' ' || postfixExpression[i] == ',') continue;
        else if (isOperand(postfixExpression[i])) {
            strcpy(temp, "");
            j = 0;

            while (i < strlen(postfixExpression) && isOperand(postfixExpression[i])) {
                temp[j] = postfixExpression[i];
                temp[++j] = '\0';
                i++;
            }
            pushString(&top, temp);
        } else if (isOperator(postfixExpression[i])) {
            strcpy(temp, "");
            strcpy(lastStackValue, "");
            strcpy(secondLastStackValue, "");

            if (isEmptyString(&top)) {
                printf("No last value, invalid expression\n");
                return;
            }
            strcpy(lastStackValue, topValueString(&top));
            popString(&top);

            if (isEmptyString(&top)) {
                printf("No second last value, invalid expression\n");
                return;
            }
            strcpy(secondLastStackValue, topValueString(&top));
            popString(&top);


            //            strcat(temp, "( ");

            //            c[0] = ' ';
            c[0] = postfixExpression[i];
            c[1] = ' ';
            c[2] = '\0';
            strcat(temp, c);
            strcat(temp, secondLastStackValue);
            strcat(temp, " ");
            strcat(temp, lastStackValue);
            //            strcat(temp, " )");
            pushString(&top, temp);
        }
    }
    strcpy(prefixExpression, topValueString(&top));
    //    printString(&top);
}

//http://www.manojagarwal.co.in/conversion-from-prefix-to-postfix/

void prefixToPostfix(char *prefixExpression, char *postfixExpression) {
    struct NodeString* top = NULL;
    char temp[100] = "", c[4] = "";
    char lastStackValue[100] = "";
    char secondLastStackValue[100] = "";

    printf("prefixExpression: %s\n", prefixExpression);
    int i = 0, j = 0;

    for (i = (strlen(prefixExpression) - 1); i > -1; i--) {
        if (prefixExpression[i] == ' ' || prefixExpression[i] == ',') continue;
        else if (isOperand(prefixExpression[i])) {
            strcpy(temp, "");
            j = 0;

            while (i < strlen(prefixExpression) && isOperand(prefixExpression[i])) {
                temp[j] = prefixExpression[i];
                temp[++j] = '\0';
                i--;
            }
            pushString(&top, temp);
        } else if (isOperator(prefixExpression[i])) {
            strcpy(temp, "");
            strcpy(lastStackValue, "");
            strcpy(secondLastStackValue, "");

            if (isEmptyString(&top)) {
                printf("No last value, invalid expression\n");
                return;
            }
            strcpy(lastStackValue, topValueString(&top));
            popString(&top);

            if (isEmptyString(&top)) {
                printf("No second last value, invalid expression\n");
                return;
            }
            strcpy(secondLastStackValue, topValueString(&top));
            popString(&top);


            //            strcat(temp, "( ");
            strcat(temp, lastStackValue);
            strcat(temp, " ");
            strcat(temp, secondLastStackValue);
            c[0] = ' ';
            c[1] = prefixExpression[i];
            c[2] = ' ';
            c[3] = '\0';
            strcat(temp, c);

            //            strcat(temp, " )");
            pushString(&top, temp);
        }
    }
    strcpy(postfixExpression, topValueString(&top));
    //    printString(&top);
}

int main() {
    //    char postfixExpression[] = "25 3 * 5 4 * + 9 -";
    //    char prefixExpression[] = "- + * 25 3 * 5 4 9";
    char infixExpression[100] = ""; //"( 1 + 2 ) * ( 3 - 4 ) * 5"; //postfix: A B C * + D E * - //prefix: - + 1 * 2 3 * 4 5
    //    char postfixExpression[50] = "";
    //    char prefixExpression[50] = "";
    //    "1 + 2 * 3 - 4 * 5";
    //    evaluatePostFix(postFixExpression);

    //    evaluatePreFix(expression, strlen(preFixExpression));

    //    infixToPostFix(infixExpression, postfixExpression, strlen(infixExpression));
    //    printf("postfix: %s\n", postfixExpression);
    //    

    //    char postfixExpression[50] = "a b c * + d e / f * -";
    //    postfixToInfix(postfixExpression, infixExpression);
    //    printf("infix: %s\n", infixExpression);

    //    char prefixExpression[50] = "* + a - b c / - d e + - f g h";
    //    prefixToInfix(prefixExpression, infixExpression);
    //    printf("infix: %s\n", infixExpression);

    //    char prefixExpression[] = "";
    //    char postfixExpression[50] = "4 2 $ 3 * 3 - 8 4 / 1 1 + / +"; //prefix: + 1 * 4 2 3 3 / / 8 4 + 1 1
    //    postfixToPrefix(postfixExpression, prefixExpression);
    //    printf("infix: %s\n", prefixExpression);

    char prefixExpression[] = "* + A B - C D";
    char postfixExpression[50] = "";
    prefixToPostfix(prefixExpression, postfixExpression);
    printf("postfix: %s\n", postfixExpression);

    return (EXIT_SUCCESS);
}