Prefix, Infix, Postfix Expression Processor

Conversion.c

/**
 *  Prefix, Infix, Postfix Expression Processor
 *
 *  Functions:
 *  1. Convert between prefix (Normal Polish Notation), expression, postfix (Reverse Polish Notation)
 *  2. Evaluate value of any expression format, support *float*
 *  3. Show detailed error message and *location* of invalid elements in expressions
 *. 4. Read from files containing multiple expressions
 *
 *  In place error reporting:
 *  1. Invalid expression elements
 *  2. Imbalance parenthesis
 *  3. Imbalance operands and operators
 *  4. Zero Division
 *
 *  Notes:
 *  while it is better to declare variable once and reuse in all loops,
 *  all variables are declared inline as needed to improve readability
 *
 *  Expression Examples: "( 3 + 4 ) * ( 100 ^ 2 )" 
 */

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

#define MAX_OPERATORS   10
#define MAX_OPERANDS    10
#define MAX_BUFFER      100             //max buffer from user input
#define KEYBOARD_INPUT  "kin.txt"       //default file to save keyboard input
#define KEYBOARD_OUTPUT "kout.txt"      //default file to save keyboard output
#define FILE_INPUT      "default.txt"   //default file to read from, and value of expressions will save back to the file

/**
 * Expression Node, Node Tag, Node Data, Node Data Type
 *
 * Usage: store single element from expression,
 *      can contain string, int or float data,
 *      tagged with type for easier expresssion processing,
 *      data type is useful for printing and arithmetics,
 *      can be used to form array of struct or stack of struct.
 */

typedef enum{
    ENT_DEFAULT,
    ENT_OPERATOR,
    ENT_OPENPR,
    ENT_CLOSEPR,
    ENT_OPERAND
} ExpNodeTag;

typedef union{
    char *string;
    int integer;
    float real;
} ExpNodeData;

typedef enum{
    ENDT_STRING,
    ENDT_INTEGER,
    ENDT_FLOAT
} ExpNodeDataType;

typedef struct element{
    ExpNodeTag      tag;
    ExpNodeData     data;
    ExpNodeDataType type;
    
    struct element *next;
} ExpNode, *ExpNodePtr;

/**
 * Operations on Expression Node
 * Common logic on node creation and stack
 */

ExpNodePtr  node_create_str (ExpNodeTag tag,    char* value);
ExpNodePtr  node_create_flo (ExpNodeTag tag,    float value);
ExpNodePtr  node_create_int (ExpNodeTag tag,    int value);
void        node_print      (ExpNodePtr node,   FILE *stream);
void        node_destroy    (ExpNodePtr *node);

int         stack_is_empty  (ExpNodePtr head);
void        stack_push      (ExpNodePtr *head,  ExpNodePtr node);
ExpNodePtr  stack_pop       (ExpNodePtr *head);
void        stack_print     (ExpNodePtr head,   const char *delimiter, FILE *stream);
void        stack_destroy   (ExpNodePtr *head);

/**
 * Operations to clean and validate inputs
 * Tagging speed up identification in conversion
 */
char        *fscanAll           (FILE *stream);
int         get_expression      (ExpNodePtr *expression, FILE *inputSourcePtr, FILE *inputFilePtr,  int inputSource);
ExpNodePtr  tag_expression      (ExpNodePtr *expression, int length);
int         detect_expression   (ExpNodePtr *expression, int length);
ExpNodePtr  validate_parentheses(ExpNodePtr *expression, int length,            int format);
void        show_error          (ExpNodePtr *expression, ExpNodePtr position,   char *message,      int offset);

/**
 * Operations to convert expression format
 */
int         precedence              (ExpNodePtr node,       int from_stack);
ExpNodePtr  prefix_to_postfix       (ExpNodePtr *expression, int *length,   ExpNodePtr *output);
ExpNodePtr  infix_to_postfix        (ExpNodePtr *expression, int *length,   ExpNodePtr *output);
ExpNodePtr  postfix_to_postfix      (ExpNodePtr *expression, int length,    ExpNodePtr *output);
int         postfix_to_expression   (ExpNodePtr *expression, int length,    ExpNodePtr *output, int type);

/**
 * Operations to evaluate postfix expression
 */
ExpNodePtr  eval_postfix (ExpNodePtr *expression,   int length, ExpNodePtr *output);
float       eval_op      (char operator,            float f1,   float f2);

/**
 * Program Entry Point
 *
 * Process:
 * Program Loop -> Expression Loop -> Action Loop
 */

int main()
{   
    printf("Welcome to Prefix-Infix-Postfix Converter!\n");
    
    /**
     * Program Loop
     * Request user to choose input source
     * Exit when exit_program == 1
     */

    int exit_program = 0;
    do{
        
        //input source menu
        printf("\nWhere do you want to read expressions from?\n"
               "A. Text File\n"
               "B. Keyboard\n"
               "? ");
        char *choice = fscanAll(stdin);
        
        //0 for keyboard, 1 for file
        int inputSource;
        //stream to read from
        FILE *inputSourcePtr;
        //stream to save input
        FILE *inputFilePtr;
        //stream to save output
        FILE *outputFilePtr;
        
        //prepare input stream
        //use strcmp instead of switch to compare whole string
        //eg: As, B1, A s, a9, etc will not be misinterpreted
        if(strcmp("A", choice) == 0){
            printf("\nYour file can contain multiple lines, "
                "each represents an expression.\n"
                "Text file location (press enter to use default input file at %s):\n? ", FILE_INPUT);
            char *filename = fscanAll(stdin);

            //use default file location
            if(filename[0] == '\0')
                filename = FILE_INPUT;
                            
            inputSource = 1;
            if((inputSourcePtr = fopen(filename, "r+")) == NULL){
                printf("Error: Cannot open %s to read expressions.\n", filename);
                continue;
            }
            inputFilePtr = NULL;
            if((outputFilePtr = fopen(filename, "a+")) == NULL){
                printf("Error: Cannot open %s to save program output.\n", filename);
                continue;
            }

            printf("Hint: Program will read from %s and write back to the file. Output will be flushed only if program is exited properly.\n", filename);
        }else if(strcmp("B", choice) == 0){
            inputSource = 0;
            inputSourcePtr = stdin;
            if((inputFilePtr = fopen(KEYBOARD_INPUT, "a+")) == NULL){
                printf("Error: Cannot open %s to save keyboard input.\n", KEYBOARD_INPUT);
                continue;
            }
            if((outputFilePtr = fopen(KEYBOARD_OUTPUT, "a+")) == NULL){
                printf("Error: Cannot open %s to save program output.\n", KEYBOARD_OUTPUT);
                continue;
            }

            printf("Hint: Program will save keyboard input to %s and output to %s. File content will be flushed only if program is exited properly.\n", KEYBOARD_INPUT, KEYBOARD_OUTPUT);
        }else{
            printf("Choice unrecognised.\n");
            continue;
        }

        free(choice);

        /**
         * Expression Loop
         * Read an expression from stream
         * Exit when change_input == 1
         */

        int change_input = 0, file_error = 0;
        do{
            //confirm continue or not if last loop ended in 
            //error reading expression from file
            if(file_error){
                file_error = 0;
                printf("\nDo you want to stop reading from file (Y/N)?\n? ");
                char *stop = fscanAll(stdin);
                if(strcmp("Y", stop) == 0){
                    change_input = 1;
                    free(stop);
                    continue;
                }
                free(stop);
            }

            //buffer to store expression
            ExpNodePtr *expression = malloc(sizeof(ExpNodePtr)*(MAX_OPERATORS*3+MAX_OPERANDS));
            memset(expression, 0, MAX_OPERATORS*3+MAX_OPERANDS);
            
            //offset when printing error message
            int errorOffset = (inputSource == 0) ? 3 : 12;

            //get expression
            if(inputSource == 0)
                printf("\nWhat expression do you want to work on?"
                    "\nAccept: %i operands from -99 to 99, %i operators from +-*/^(), space seperated"
                    "\n?: ", MAX_OPERANDS, MAX_OPERATORS);
            int length = get_expression(expression, inputSourcePtr, inputFilePtr, inputSource);
            if(length == 0){
                printf("Error: expression is empty.\n");
                if(inputSource == 1)
                    file_error = 1;
                continue;
            }else if(length == -1){
                printf("Error: expression is too long.\n");
                if(inputSource == 1)
                    file_error = 1;
                continue;
            }

            /**
             * Error Checking: Expression Elements
             * Tag and validate expression elements
             * eg: (9, +-, a8, a8
             */
            ExpNodePtr val_el = tag_expression(expression, length);
            if(val_el != NULL){
                show_error(expression, val_el, "Error: invalid element.", errorOffset);
                if(inputSource == 1)
                    file_error = 1;
                continue;
            }

            //detect expression format
            int format = detect_expression(expression, length);
            
            /**
             * Error Checking: Imbalance Parenthesis
             * eg: ), (, )(, ()), (()
             */
            ExpNodePtr val_parentheses = validate_parentheses(expression, length, format);
            if(val_parentheses != NULL){
                if(val_parentheses->tag == ENT_OPENPR){
                    show_error(expression, val_parentheses, "Error: Ops, you didn't close this parenthesis.", errorOffset);
                }else{
                    show_error(expression, val_parentheses, "Error: invalid parenthesis.", errorOffset);
                }
                continue;
            }

            //buffer to store postfix as intermediate format
            ExpNodePtr *postfix = malloc(sizeof(ExpNodePtr)*(MAX_OPERATORS*3+MAX_OPERANDS));
            memset(postfix, 0, MAX_OPERATORS*3+MAX_OPERANDS);

            ExpNodePtr convert = NULL;
            switch(format){
                case -1:
                    convert = prefix_to_postfix(expression, &length, postfix);
                    break;
                case 0:
                    convert = infix_to_postfix(expression, &length, postfix);
                    break;
                case 1:
                    //still need to validate imbalance operand and operators
                    convert = postfix_to_postfix(expression, length, postfix);
                    break;
            }

            /**
             * Error Checking: Imbalance Operand and Operator
             * prefix    : + 9 9 9, + + 9 9, + + + 9 9 + 9 9
             * infix     : 9 9 + 9, ( 9 9 ) + 9, 9 + 9 9, 9 + ( 9 9 )
             * postfix   : 9 9 9 +, 9 9 + +, 9 9 + 9 9 + + + 
             */
            if(convert != NULL){
                if(convert->tag == ENT_OPERATOR){
                    show_error(expression, convert, "Error: not enough operand.", errorOffset);
                }else{
                    show_error(expression, convert, "Error: excess operand.", errorOffset);
                }
                continue;
            }

            /**
             * Error Checking: Zero Devision
             * Precalculate expression value
             * eg: 8 / 0, 20 / ( 8 - 8 )
             */
            ExpNodePtr result, eval;
            if((eval = eval_postfix(postfix, length, &result)) != NULL){
                show_error(expression, eval, "Error: zero division at here.", errorOffset);
                continue;
            }

            /**
             * Actions Loop
             * Execute actions on expressions
             * Exit when exit_menu == 1
             */
            int exit_menu = 0;
            do{
                //actions menu
                printf("\nPlease select an action: \n"
                    "A. Convert to infix, prefix or postfix \n"
                    "B. Evaluate expression\n"
                    "C. %s\n"
                    "D. Change Input Method\n"
                    "E. Exit Program\n?: ", 
                    (inputSource == 0) ? "Enter new expression" : "Get next expression from file");
                char *choice2 = fscanAll(stdin);

                //convert format
                if(strcmp("A", choice2) == 0){
                    //buffer for convertion                    
                    ExpNodePtr *convert_a = malloc(sizeof(ExpNodePtr)*(MAX_OPERATORS*3+MAX_OPERANDS));
                    memset(convert_a, 0, MAX_OPERATORS*3+MAX_OPERANDS);
                    ExpNodePtr *convert_b = malloc(sizeof(ExpNodePtr)*(MAX_OPERATORS*3+MAX_OPERANDS));
                    memset(convert_b, 0, MAX_OPERATORS*3+MAX_OPERANDS);

                    //use modulus to choose 0(prefix), 1(infix), 2(postfix)
                    char format_labels[3][8] = {"prefix", "infix", "postfix"};
                    int current = (format+1);
                    int a = (current+1)%3;
                    int b = (current+2)%3;

                    printf("\nThis is a(n) %s expression. Do you want to convert it to (A) %s or (B) %s or (C) for both? Select A, B, or C option.\n?: ", format_labels[current], format_labels[a], format_labels[b]);
                    char *choice3 = fscanAll(stdin);

                    //calculate conversion based on modulus result
                    int l_a = postfix_to_expression(postfix, length, convert_a, a-1);
                    int l_b = postfix_to_expression(postfix, length, convert_b, b-1);

                    if(strcmp("A", choice3) == 0){
                        printf("\nThe %s format is: ", format_labels[a]);
                        fprintf(outputFilePtr, "\nThe %s format is: ", format_labels[a]);
                        for(int i=0; i<l_a; i++){
                            node_print(convert_a[i], stdout);
                            node_print(convert_a[i], outputFilePtr);
                            printf(" ");
                            fprintf(outputFilePtr, " ");
                        }
                        printf("\n");
                    }else if(strcmp("B", choice3) == 0){
                        printf("\nThe %s format is: ", format_labels[b]);
                        fprintf(outputFilePtr, "\nThe %s format is: ", format_labels[b]);
                        for(int i=0; i<l_b; i++){
                            node_print(convert_b[i], stdout);
                            node_print(convert_b[i], outputFilePtr);
                            printf(" ");
                            fprintf(outputFilePtr, " ");
                        }
                        printf("\n");
                    }else if(strcmp("C", choice3) == 0){
                        printf("\nThe %s format is: ", format_labels[a]);
                        fprintf(outputFilePtr, "\nThe %s format is: ", format_labels[a]);
                        for(int i=0; i<l_a; i++){
                            node_print(convert_a[i], stdout);
                            node_print(convert_a[i], outputFilePtr);
                            printf(" ");
                            fprintf(outputFilePtr, " ");
                        }
                        printf("\nThe %s format is: ", format_labels[b]);
                        fprintf(outputFilePtr, "\nThe %s format is: ", format_labels[b]);
                        for(int i=0; i<l_b; i++){
                            node_print(convert_b[i], stdout);
                            node_print(convert_b[i], outputFilePtr);
                            printf(" ");
                            fprintf(outputFilePtr, " ");
                        }
                        printf("\n");
                    }else{
                        printf("\nChoice unrecognised.\n");
                    }

                    free(convert_a);
                    free(convert_b);
                    free(choice3);
                    
                //evaluate value
                }else if(strcmp("B", choice2) == 0){
                    printf("\nThe value of this expression is: ");
                    fprintf(outputFilePtr, "\nThe value of this expression is: ");
                    node_print(result, stdout);
                    node_print(result, outputFilePtr);
                    printf("\n");

                //next expression
                }else if(strcmp("C", choice2) == 0){
                    exit_menu = 1;

                //change input source
                }else if(strcmp("D", choice2) == 0){
                    exit_menu = 1;
                    change_input = 1;

                //exit program
                }else if(strcmp("E", choice2) == 0){
                    exit_menu = 1;
                    change_input = 1;
                    exit_program = 1;
                }else{
                    printf("\nChoice unrecognised.\n");
                }

                free(choice2);

            }while(exit_menu == 0);

            for(int i=0; (i<(MAX_OPERATORS*3+MAX_OPERANDS)) && (expression[i]!=NULL); i++)
                node_destroy(&expression[i]);
            free(expression);
            free(postfix);

        }while(change_input == 0);

        //close files
        if(inputSource == 0){
            fclose(inputSourcePtr);
            fclose(outputFilePtr);
        }else if(inputSource == 1){
            fclose(inputFilePtr);
            fclose(outputFilePtr);
        }

    }while(exit_program == 0);

    printf("\nThanks for using our converter!\n");

}

/**
 * FscanAll
 * scanf(" %s") cannot accepts string with space,
 * if more character than expected, will left in buffer
 * and affect next reading
 * @return  pointer to character receive
 * @warning must free returned char* after use
 */
char *fscanAll(FILE *stream)
{
    char *all = calloc(256, sizeof(char)), *tmp, c;
    size_t size = 0, index = 0, chunk = 256;

    while ((c = fgetc(stream)) != '\n' && !feof(stream)) {
        //dynamically resize memory
        if(size <= index){
            size += chunk;
            tmp = realloc(all, size);
            memset(tmp+(size-chunk), 0, chunk);
            if(!tmp){
                free(all);
                all = NULL;
                break;
            }
            all = tmp;
        }

        all[index++] = c;
    }

    return all;
}

/**
 * Retrieve and tokenize expression
 *
 * @return  -1 if more operators or operands than allowed
 *          otherwise amount of operators and operands
 */
int get_expression(ExpNodePtr *expression, FILE *inputSourcePtr, FILE *inputFilePtr, int inputSource)
{
    char *btoken, delim[2] = " ";
    int i = -1;
    
    //retrieve input from stream
    char *buffer = fscanAll(inputSourcePtr);
    
    //save keyboard input when read from default input
    if(inputSource == 0)
        fprintf(inputFilePtr, "%s\n", buffer);
    
    //output expression if is read from file
    if(inputSource == 1)
        fprintf(stdout, "\nExpression: %s\n", buffer);
    
    //trim trailing space
    int bi = (int) strlen(buffer)-1;
    while(isspace(buffer[bi]))
        buffer[bi--] = 0;
    
    //tokenize input
    btoken = strtok(buffer, delim);
    while(btoken != NULL)
    {
        if(++i > MAX_OPERANDS+MAX_OPERATORS)
            return -1;
        expression[i] = node_create_str(ENT_DEFAULT, btoken);
        btoken = strtok(NULL, delim);
    }

    free(buffer);
    
    return i+1;
};

/**
 * Tag and Validate Expression
 *
 * @return  NULL if no error
 *          ppinter of invalid element if error
 */
ExpNodePtr tag_expression(ExpNodePtr *expression, int length)
{
    for(int i=0; i<length; i++){
        int first_negative  = (expression[i]->data.string[0] == '-');
        int first_operator  = (memchr("^*/+", expression[i]->data.string[0], 4) != NULL);
        int first_openpr    = (expression[i]->data.string[0] == '(');
        int first_closepr   = (expression[i]->data.string[0] == ')');
        int exp_length      = (int) strlen(expression[i]->data.string);
        int all_digits      = 1;
        int neg_digits      = 1;
        
        for(int j=0; expression[i]->data.string[j]!='\0'; j++){
            if(!isdigit(expression[i]->data.string[j])){
                all_digits = 0;
                if(j!=0){
                    neg_digits = 0;
                    break;
                }
            }
        }
        
        if(first_openpr && (exp_length == 1)){
            expression[i]->tag = ENT_OPENPR;
        }else if(first_closepr && (exp_length == 1)){
            expression[i]->tag = ENT_CLOSEPR;
        }else if((first_operator || first_negative) && (exp_length == 1)){
            expression[i]->tag = ENT_OPERATOR;
        }else if((first_negative && neg_digits) || all_digits){
            //destroy original string node and create an int node
            int value = atoi(expression[i]->data.string);
            node_destroy(&expression[i]);
            expression[i] = node_create_int(ENT_OPERAND, value);
        }else{
            return expression[i];
        }
    }
    
    return NULL;
};

/**
 * Detect Expression Format
 *
 * @return  -1 if is prefix
 *          0 if is infix expression
 *          1 if is postfix
 */
int detect_expression (ExpNodePtr *expression, int length)
{
    //prefix: return -1 if first character is operator
    for(int i=0; i<length; i++){
        if(expression[i]->tag == ENT_OPENPR)
            continue;
        if(expression[i]->tag == ENT_OPERATOR)
            return -1;
        else
            break;
    }
    
    //postfix: return 1 if last character is operator
    for(int i=(length-1); i>=0; i--){
        if(expression[i]->tag == ENT_CLOSEPR)
            continue;
        if(expression[i]->tag == ENT_OPERATOR)
            return 1;
        else
            break;
    }
    
    //otherwise infix expression
    return 0;
};

/**
 * Validate Parentheses in Expression
 *
 * @return  NULL if is balanced
 *          pointer of invalid parenthesis if is imbalanced
 */
ExpNodePtr validate_parentheses(ExpNodePtr *expression, int length, int format)
{
    ExpNodePtr prtrace = NULL, pop;
    
    for(int i=0; i<length; i++){
        //only infix expression can contain parenthesis
        if((format != 0) && ((expression[i]->tag == ENT_OPENPR) || (expression[i]->tag == ENT_CLOSEPR)))
            return expression[i];
        if(expression[i]->tag == ENT_OPENPR){
            stack_push(&prtrace, node_create_int(ENT_DEFAULT, i));
        }else if((expression[i]->tag == ENT_CLOSEPR) && (stack_is_empty(prtrace))){
            return expression[i];
        }else if(expression[i]->tag == ENT_CLOSEPR){
            pop = stack_pop(&prtrace);
            node_destroy(&pop);
        }
    }
    
    ExpNodePtr r = stack_is_empty(prtrace) ? NULL : expression[prtrace->data.integer];
    stack_destroy(&prtrace);
    
    return r;
};

/**
 * Show Error
 * Print space until the position of the incorrect element
 * Then, print arrow and error message
 */
void show_error (ExpNodePtr *expression, ExpNodePtr position, char *message, int offset)
{
    for(int i=0;i<offset;i++)
        printf(" ");
    
    int length = 0;
    for(int i=0;expression[i] != position;i++){
        switch(expression[i]->type){
            case ENDT_INTEGER:
                if(expression[i]->data.integer == 0){
                    length = 1;
                }else{
                    length = floor(log10(abs(expression[i]->data.integer)))+1;
                    if(expression[i]->data.integer < 0)
                        length++;
                }
                break;
            case ENDT_STRING:
                length = (int) strlen(expression[i]->data.string);
                break;
            default:
                break;
        }
        
        for(int j=0;j<length;j++)
            printf(" ");
        printf(" ");
    }
    
    printf("^\n%s\n", message);
    
};

/**
 * Return Operator's Precedence
 *
 * @return operator's precedence
 */
int precedence(ExpNodePtr node, int from_stack)
{
    if(from_stack && (node->tag == ENT_OPENPR))
        return 1;
    
    switch(node->data.string[0])
    {
        case '(':
            return 5;
        case '^':
            return 4;
        case '*':
        case '/':
            return 3;
        case '+':
        case '-':
            return 2;
        default:
            return 0;
    }
};

/**
 * Prefix to Postfix Conversion
 *
 * @reference: http://www.manojagarwal.co.in/conversion-from-prefix-to-postfix/
 * @return pointer of invalid element
 *         NULL if no error
 */
ExpNodePtr prefix_to_postfix(ExpNodePtr *expression, int *length, ExpNodePtr *output)
{
    ExpNodePtr op1 = NULL, op2 = NULL, optrace = NULL, pop;
    int oi = 0;
    
    for(int i=(*length)-1; i>=0; i--){
        if(expression[i]->tag == ENT_OPERAND){
            output[oi++] = expression[i];
            stack_push(&optrace, node_create_int(ENT_DEFAULT, i));
        }else if(expression[i]->tag == ENT_OPERATOR){
            int pc = 0;
            do{
                if((--oi<0) || (output[oi]==NULL)) return expression[i];
                ExpNodePtr top = output[oi];
                if(top->tag == ENT_CLOSEPR) pc++;
                if(top->tag == ENT_OPENPR) pc--;
                stack_push(&op1, top);
            }while(pc > 0);
            
            pop = stack_pop(&optrace);
            node_destroy(&pop);
            
            pc = 0;
            do{
                if((--oi<0) || (output[oi]==NULL)) return expression[i];
                ExpNodePtr top = output[oi];
                if(top->tag == ENT_CLOSEPR) pc++;
                if(top->tag == ENT_OPENPR) pc--;
                stack_push(&op2, top);
            }while(pc > 0);
            
            pop = stack_pop(&optrace);
            node_destroy(&pop);
            
            //put '('
            output[oi++] = node_create_str(ENT_OPENPR, "(");
            
            //operand 1
            while(!stack_is_empty(op1))
                output[oi++] = stack_pop(&op1);
            
            //operand 2
            while(!stack_is_empty(op2))
                output[oi++] = stack_pop(&op2);
            
            //operator
            output[oi++] = expression[i];
            
            //put ')'
            output[oi++] = node_create_str(ENT_CLOSEPR, ")");
            
            stack_push(&optrace, node_create_int(ENT_DEFAULT, -1));
        }
    }
    
    //check operands
    pop = optrace;
    int r = -1;
    while(pop != NULL){
        if(pop->data.integer == -1){
            pop = pop->next;
            continue;
        }else{
            r = pop->data.integer;
            break;
        }
    }
    stack_destroy(&optrace);
    if(r!=-1) return expression[r];
    
    //remove brackets
    ExpNodePtr temp = NULL;
    while((--oi) >= 0){
        if((output[oi]->tag == ENT_OPENPR) || (output[oi]->tag == ENT_CLOSEPR))
            node_destroy(&output[oi]);
        else
            stack_push(&temp, output[oi]);
        output[oi] = NULL;
    }
    
    while(!stack_is_empty(temp))
        output[++oi] = stack_pop(&temp);
    
    *length = ++oi;
    
    return NULL;
}

/**
 * Infix to Postfix Conversion
 *
 * @reference: stack.pdf by Mr. Chew
 * @return pointer of invalid element
 *         NULL if no error
 */
ExpNodePtr infix_to_postfix(ExpNodePtr *expression, int *length, ExpNodePtr *output)
{
    ExpNodePtr operators = NULL;
    int oi = 0, last_element = -1;
    
    for(int i=0; i<(*length); i++){
        switch(expression[i]->tag){
            case ENT_OPERAND:
                output[oi++] = expression[i];
                
                if(last_element == 0)
                    return expression[i];
                else
                    last_element = 0;
                break;
            case ENT_OPERATOR:
            case ENT_OPENPR:
                if(!stack_is_empty(operators)){
                    while((!stack_is_empty(operators)) && (precedence(expression[i],0) <= precedence(operators,1))){
                        if(operators->tag != ENT_OPENPR)
                            output[oi++] = stack_pop(&operators);
                    }
                }
                stack_push(&operators, expression[i]);
                
                if(expression[i]->tag == ENT_OPERATOR){
                    if(last_element == 1)
                        return expression[i];
                    else
                        last_element = 1;
                }
                break;
            case ENT_CLOSEPR:
                while(operators->tag != ENT_OPENPR)
                    output[oi++] = stack_pop(&operators);
                stack_pop(&operators);
                break;
            default:
                continue;
        }
    }
    
    while(!stack_is_empty(operators))
        output[oi++] = stack_pop(&operators);
    
    *length = oi;
    
    return NULL;
};

/**
 * Postfix Validation and Zero Division Prevent
 *
 * @reference: stack.pdf by Mr. Chew
 * @return pointer of invalid element
 *          -1 if no error
 */
ExpNodePtr postfix_to_postfix(ExpNodePtr *expression, int length, ExpNodePtr *postfix)
{
    ExpNodePtr optrace = NULL, pop;
    
    for(int i=0; i<length; i++){
        postfix[i] = expression[i];
        if(expression[i]->tag == ENT_OPERAND){
            stack_push(&optrace, node_create_int(ENT_DEFAULT, i));
        }else if(expression[i]->tag == ENT_OPERATOR){
            if(stack_is_empty(optrace)) return expression[i];
            pop = stack_pop(&optrace);
            node_destroy(&pop);
            if(stack_is_empty(optrace)) return expression[i];
            pop = stack_pop(&optrace);
            node_destroy(&pop);
            stack_push(&optrace, node_create_int(ENT_DEFAULT, -1));
        }
    }
    
    //check operands
    pop = optrace;
    int r = -1;
    while(pop != NULL){
        if(pop->data.integer == -1){
            pop = pop->next;
            continue;
        }else{
            r = pop->data.integer;
            break;
        }
    }
    stack_destroy(&optrace);
    if(r!=-1) return expression[r];
    
    return NULL;
}

/**
 * Postfix to Prefix/Infix Conversion
 *
 * @param type -1 to convert into prefix; 0 to convert into infix; 1 to retain postfix
 * @reference: http://rubyquiz.com/quiz148.html
 * @reference: http://see-programming.blogspot.my/2013/05/postfix-to-prefix-conversion.html
 */
int postfix_to_expression (ExpNodePtr *expression, int length, ExpNodePtr *output, int type)
{
    if(type == 1){
        for(int i=0; i<length; i++)
            output[i] = expression[i];
        return length;
    }
    
    ExpNodePtr op1 = NULL, op2 = NULL;
    int oi = 0;
    
    for(int i=0; i<length; i++){
        if(expression[i]->tag == ENT_OPERAND){
            output[oi++] = expression[i];
        }else if(expression[i]->tag == ENT_OPERATOR){
            int pc = 0;
            do{
                ExpNodePtr top = output[--oi];
                if(top->tag == ENT_CLOSEPR) pc++;
                if(top->tag == ENT_OPENPR) pc--;
                stack_push(&op2, top);
            }while(pc > 0);
            
            pc = 0;
            do{
                ExpNodePtr top = output[--oi];
                if(top->tag == ENT_CLOSEPR) pc++;
                if(top->tag == ENT_OPENPR) pc--;
                stack_push(&op1, top);
            }while(pc > 0);
            
            //put '('
            output[oi++] = node_create_str(ENT_OPENPR, "(");
            
            //put operator in front if is prefix
            if(type == -1)
                output[oi++] = expression[i];
            
            //operand 1
            while(!stack_is_empty(op1))
                output[oi++] = stack_pop(&op1);
            
            //put operator in middle if is prefix
            if(type == 0)
                output[oi++] = expression[i];
            
            //operand 2
            while(!stack_is_empty(op2))
                output[oi++] = stack_pop(&op2);
            
            //put ')'
            output[oi++] = node_create_str(ENT_CLOSEPR, ")");
        }
    }
    
    //remove brackets if is prefix
    if(type == -1){
        ExpNodePtr temp = NULL;
        while((--oi) >= 0){
            if((output[oi]->tag == ENT_OPENPR) || (output[oi]->tag == ENT_CLOSEPR))
                node_destroy(&output[oi]);
            else
                stack_push(&temp, output[oi]);
            output[oi] = NULL;
        }
        
        while(!stack_is_empty(temp))
            output[++oi] = stack_pop(&temp);
        
        ++oi;
    }
    
    return oi;
}


/**
 * Evaluate Postfix Expression
 *
 * @reference: stack.pdf by Mr. Chew
 * @return pointer to node that leads to zero division
  *        else pointer to node that contains the value
 */
ExpNodePtr eval_postfix (ExpNodePtr *expression, int length, ExpNodePtr *output){
    ExpNodePtr operands = NULL, op1, op2;
    
    for(int i=0; i<length; i++){
        if(expression[i]->tag == ENT_OPERAND){
            stack_push(&operands, expression[i]);
        }else if(expression[i]->tag == ENT_OPERATOR){
            float f1=0, f2=0, result=0;
            
            char operator = expression[i]->data.string[0];
            
            op2 = stack_pop(&operands);
            switch(op2->type){
                case ENDT_INTEGER:
                    f2 = op2->data.integer;
                    break;
                case ENDT_FLOAT:
                    f2 = op2->data.real;
                    break;
                default:
                    break;
            }
            
            if((f2 == 0.0) && (operator == '/'))
                return expression[i];
            
            op1 = stack_pop(&operands);
            switch(op1->type){
                case ENDT_INTEGER:
                    f1 = op1->data.integer;
                    break;
                case ENDT_FLOAT:
                    f1 = op1->data.real;
                    break;
                default:
                    break;
            }
            
            result = eval_op(operator, f1, f2);
            stack_push(&operands, node_create_flo(ENT_OPERAND, result));
        }
    }
    
    *output = operands;
    
    return NULL;
};

/**
 * Evaluate Arithmetic Operation
 *
 * @return  value of operation
 *          0 otherwise
 */
float eval_op (char operator, float f1, float f2){
    switch(operator)
    {
        case '^':
            return pow(f1, f2);
        case '*':
            return f1*f2;
        case '/':
            return f1/f2;
        case '+':
            return f1+f2;
        case '-':
            return f1-f2;
        default:
            return 0;
    }
};

/**
 * Create a string node
 */
ExpNodePtr node_create_str (ExpNodeTag tag, char* value)
{
    ExpNodePtr create       = malloc(sizeof(ExpNode));
    create->tag             = tag;
    create->data.string     = malloc(sizeof(char)*strlen(value));
    strcpy(create->data.string, value);
    create->type            = ENDT_STRING;
    create->next            = NULL;
    
    return create;
};

/**
 * Create an int node
 */
ExpNodePtr node_create_int (ExpNodeTag tag, int value)
{
    ExpNodePtr create       = malloc(sizeof(ExpNode));
    create->tag             = tag;
    create->data.integer    = value;
    create->type            = ENDT_INTEGER;
    create->next            = NULL;
    
    return create;
};

/**
 * Create a floating point node
 */
ExpNodePtr node_create_flo (ExpNodeTag tag, float value)
{
    ExpNodePtr create       = malloc(sizeof(ExpNode));
    create->tag             = tag;
    create->data.real       = value;
    create->type            = ENDT_FLOAT;
    create->next            = NULL;
    
    return create;
};

/**
 * Print out node based on data type
 */
void node_print (ExpNodePtr node, FILE *stream)
{
    switch(node->type){
        case ENDT_STRING:
            fprintf(stream, "%s", node->data.string);
            break;
        case ENDT_INTEGER:
            fprintf(stream, "%i", node->data.integer);
            break;
        case ENDT_FLOAT:
            fprintf(stream, "%.2f", node->data.real);
            break;
    }
};

/**
 * Release node memory
 */
void node_destroy (ExpNodePtr *node)
{
    if((*node)->type == ENDT_STRING)
        free((*node)->data.string);
    free(*node);
};

/**
 * Check stack is empty or not
 */
int stack_is_empty (ExpNodePtr head)
{
    return (head == NULL);
};

/**
 * Push a node to stack
 */
void stack_push (ExpNodePtr *head, ExpNodePtr node)
{
    if(head != NULL)
        node->next = *head;
    *head = node;
};

/**
 * Pop a node from stack
 */
ExpNodePtr stack_pop (ExpNodePtr *head)
{
    ExpNodePtr temp = *head;
    if(*head!=NULL){
        *head = (*head)->next;
        temp->next = NULL;
    }
    return temp;
};

/**
 * Print out stack
 */
void stack_print (ExpNodePtr head, const char *delimeter, FILE *stream)
{
    while(head!=NULL){
        node_print(head, stream);
        fprintf(stream, "%s", delimeter);
        head = head->next;
    }
};

/**
 * Release stack memory
 */
void stack_destroy (ExpNodePtr *head)
{
    ExpNodePtr temp;
    while(*head!=NULL){
        temp = (*head)->next;
        node_destroy(head);
        *head = temp;
    }
};