CS F213 - Logic Assignment Task [ *Convert from Infix to Postfix | * Convert Postfix into a parse tree | * Get Infix from parse tree via in-order traversal ]

central_code.c

#include <stdio.h>
#include <string.h>
// Double quotes as we get this header file from local repository
#include "infixtopostfix.h" // For infix to postfix conversion functions
#include "parsetree.h" // For converting postfix to parse tree functions
#define MAXSIZE 4000

char storeInfix[MAXSIZE], storePostfix[MAXSIZE];
int top;
struct treeNode *storeTreeRoot;

int main()
{
    // Note - How difficult is it to implement a is-infix-expression checker?
    // The above is not required as it has been guaranteed that input is a proper infix expression.
    // However, due to the use of isalnum(), any other character besides the 4 defined operators will be
    // treated as an operand
    printf("Please enter an infix expression\n");
    scanf("%s", storeInfix);

    // The Infix to Postfix Section
    inToPostfix(storeInfix, storePostfix);
    printf("\nGiven Infix Expression: %s \nPostfix Expression: %s\n",storeInfix, storePostfix);

    // Feed Postfix to ParseTree Section
    storeTreeRoot = postfixToTree(storePostfix);
    printf("Postfix Expression has been converted into rooted binary parse tree");

    // Get back our infix expression
    printf("\n Our original Infix Expression :");
    inOrderTraversal(storeTreeRoot);
    printf("\n");

    return 0;
}

infixtopostfix.c

#include "infixtopostfix.h"

// The following functions are for converting from Prefix to PostFix Expression

// arrstk_x means arraystack_x, pointing to stack operations happening on array

// Gives a initial value to the top of stack
void arrstk_initialize(int *top)
{
    *top = 0;
}

// Pop the topmost element of stack (by changing where top points)
int arrstk_pop(char *stack, int *top)
{
    return stack[(*top)--];
}

// Add an element to the stack, it will replace any other element that was at that
// array index
void arrstk_push(char *stack, int* top, char elem)
{
    stack[++(*top)] = elem;
}

// Precedence of operators checker
int oper_prec(char opr)
{
    switch(opr)
    {
    case '(': return 1;
    case '>': return 2;
    case '+': return 3;
    case '*': return 4;
    case '~': return 5;
    default : return 0;
    }
}

// Check if stack is empty
int arrstk_empty(int *top)
{
    return *top == 0 ? 1 : 0;
}

// The Infix to PostFix Function

void inToPostfix(char *arg_inFix, char *arg_postfix)
{
    char arr_stack[4000]; // The max size of the expression that we consider
    int stack_top, infix_iter = 0, postfix_iter=-1; //The indicies for our arrays
    char checker, element;
    arrstk_initialize(&stack_top);

    while((checker = arg_inFix[infix_iter++]) != '\0')
    {
        if( checker == '(')   // If '(' then push on stack
        {
            arrstk_push(arr_stack, &stack_top, checker);
        }
        else if(isalnum(checker))  // If an operand then send to postfix
        {
            arg_postfix[++postfix_iter] = checker;
        }
        // For closing bracket pop elements from stack and send to postfix
        else if(checker == ')')
        {   while((arr_stack[stack_top] != '('))
            {
                arg_postfix[++postfix_iter] = arrstk_pop(arr_stack, &stack_top);
            }
            arrstk_pop(arr_stack, &stack_top);
        }
        // It is an operator
        else
        {
            while(!arrstk_empty(&stack_top) && (oper_prec(arr_stack[stack_top]) >= oper_prec(checker)))
            {
                arg_postfix[++postfix_iter] = arrstk_pop(arr_stack, &stack_top);
            }
            arrstk_push(arr_stack, &stack_top, checker);
        }
    }

    while(stack_top != 0)
        {
            arg_postfix[++postfix_iter] = arrstk_pop(arr_stack, &stack_top);
        }
    arg_postfix[++postfix_iter]='\0';
}

infixtopostfix.h

// The purpose of this header file is to store minimum practical interface to a corresponding
// .c file, including function declarations used in multiple source files.
/* However, the declarations here are used in only one source file currently.
   They are still kept here for convenience and as they maybe required for multiple
   source files in the future (for later assignments)
*/
#ifndef _INFIXTOPOSTFIX_H_   /* Include guard */
#define _INFIXTOPOSTFIX_H_

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

// Functions for the array stack
void arrstk_initialize(int *top);

// Pop the topmost element of stack
int arrstk_pop(char *stack, int *top);

// Push an element into the stack
void arrstk_push(char *stack, int* top, char elem);

// Function to check precedence
int oper_prec(char opr);

// To check if stack is empty
int arrstk_empty(int *top);

// Infix to Postfix function
void inToPostfix(char *arg_inFix, char *arg_postfix);

#endif

LogicAssignment_README.md

To run the main code, go to the directory containing the files and run the following commands on bash/terminal.

• gcc -o main central_code.c infixtopostfix.c parsetree.c
• ./main

To run the tests, which are an additional feature that comes with the code

• gcc -o test unittests.c parsetree.c infixtopostfix.c
• ./test

parsetree.c

#include "parsetree.h"

// strstk_x means structurestack_x, pointing to stack operations happening on the treeNode structure

void strstk_initialize(int *top)
{
    *top = 0;
}

struct treeNode* strstk_pop(struct treeNode* *stack, int *top)
{
    return stack[(*top)--];
}

void strstk_push(struct treeNode* *stack, int* top, struct treeNode* elem)
{
    stack[++(*top)] = elem;
}

struct treeNode* addNewNode(char nodeValue)
{
    // Memory allocation syntax is [type - malloc - size ]
    struct treeNode *currentNode = (struct treeNode *) malloc(sizeof(struct treeNode));
    currentNode->parentNode = NULL;
    currentNode->value = nodeValue;
    // Seperate functions allocate memory to these subtrees
    currentNode->childNode_Left = NULL;
    currentNode->childNode_Right = NULL;
    return currentNode;
}

struct treeNode* postfixToTree(char arg_postfix[])
{
    // A frustrating treenode* a,b versus treenode *a,*b bug was here
    struct treeNode *mainStore, *secondaryStore1, *secondaryStore2;
    struct treeNode *str_stack[4000]; // Return of the stack
    int stack_top, treeIter, store_element; // And it's top position
    strstk_initialize(&stack_top);

    for (treeIter=0; treeIter < 4000; treeIter++)
    {
        store_element = arg_postfix[treeIter];
        if(store_element == '\0')
            break;
        // The standard function `isalnum` returns 1 if the argument is
        // alpha-numeric, else zero
        if (isalnum(store_element))
        {   // For now, just push any operand onto the stack
            mainStore = addNewNode(arg_postfix[treeIter]);
            strstk_push(str_stack, &stack_top, mainStore);
        }
        // Special negation shenanigans
        else if (store_element == '~')
        {
            mainStore = addNewNode(arg_postfix[treeIter]);

            // Pop only one node since it's negation
            secondaryStore1 = strstk_pop(str_stack, &stack_top);
            // Store the element, the left child remains NULL
            mainStore->childNode_Right = secondaryStore1;
            // Add this subexpression to stack
            strstk_push(str_stack, &stack_top, mainStore);
        }
        else // If we have operators other than negation
        {
            mainStore = addNewNode(arg_postfix[treeIter]);

            // Pop two top nodes
            secondaryStore1 = strstk_pop(str_stack, &stack_top);
            secondaryStore2 = strstk_pop(str_stack, &stack_top);

            //  Store them as children of the current node
            mainStore->childNode_Right = secondaryStore1;
            mainStore->childNode_Left = secondaryStore2;

            // Add this subexpression to stack
            strstk_push(str_stack, &stack_top, mainStore);
        }
    }
    //  only element will be root of expression
    // tree
    mainStore = strstk_pop(str_stack, &stack_top);
    return mainStore;
}

// Finally, let's get back our Infix expression by in-order traversal of tree
// With some friendly recursion
void inOrderTraversal(struct treeNode *Node)
{
    if(Node != NULL)
    {
        // Parenthesis printf's added
        if(!(Node->childNode_Left == NULL) || !(Node->childNode_Right == NULL))
            printf("(");
        inOrderTraversal(Node->childNode_Left);
        printf("%c", Node->value);
        inOrderTraversal(Node->childNode_Right);
        if(!(Node->childNode_Left == NULL) || !(Node->childNode_Right == NULL))
            printf(")");
        /*
            NOTE -
            An important point to note is that the infix expression we gave
            as input and the infix expression we get from in-order traversal will have some
            difference in number of parenthesis. This is because information is lost due to
            conversion of the expression to postfix.
            And so,
            Infix Input 1: A+(B*C+(D*E+F)*G)*H
            Infix Input 2: (A+(((B*C)+(((D*E)+F)*G))*H))
            both will give In-Order Traversal Infix as (A+(((B*C)+(((D*E)+F)*G))*H))
        */
    }
}

parsetree.h

#ifndef _PARSETREE_H_   /* Include guard */
#define _PARSETREE_H_

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

// The structure (of nodes) to hold the parse tree
struct treeNode
{
    char value;
    struct treeNode *parentNode;
    struct treeNode *childNode_Left;
    struct treeNode *childNode_Right;
};

void strstk_initialize(int *top);
struct treeNode* strstk_pop(struct treeNode* *stack, int *top);
void strstk_push(struct treeNode* *stack, int* top, struct treeNode* elem);

struct treeNode* addNewNode(char nodeValue);

struct treeNode* postfixToTree(char arg_postfix[]);

void inOrderTraversal(struct treeNode *Node);

#endif

unittests.c

/*
    This is an additional C file that is used for testing the code of the main file.
    A standard practice in open source development, unit testing helps detect errors and
    hidden problems in the code.
*/

#include <stdio.h>
#include "unittests.h"
#include "parsetree.h"
#include "infixtopostfix.h"

// No of tests (runs)
int tests_run = 0;
int finalInfix_Iter = 0;
char storePostfix[100];
char finalInfix[100];

// Test 1
static char * testCase1()
{
    char storeInfix1[] = "A+(B*C)";
    inToPostfix(storeInfix1, storePostfix);
    assert_test("Test Case 1 fails for postfix expression!", strcmp(storePostfix, "ABC*+") == 0);

    return 0;
}

// Test 2
static char * testCase2()
{
    char storeInfix2[] = "A+(B*C+(D*E+F)*G)*H";
    inToPostfix(storeInfix2, storePostfix);
    assert_test("Test Case 2 fails for postfix expression!", strcmp(storePostfix, "ABC*DE*F+G*+H*+") == 0);

    return 0;
}

static char * testCase3()
{
    char storeInfix3[] = "P*~(P+~Q)>(R>S)";
    inToPostfix(storeInfix3, storePostfix);
    assert_test("Test Case 3 fails for postfix expression!", strcmp(storePostfix, "PPQ~+~*RS>>") == 0);

    return 0;
}


static char * all_tests() {
    run_test(testCase1);
    run_test(testCase2);
    run_test(testCase3);
    return 0;
}

int main(int argc, char **argv) {
    char *result = all_tests();
    if (result != 0) {
        printf("%s\n", result);
    }
    else {
        printf("\nALL TESTS PASS\n");
    }
    printf("Tests run: %d\n", tests_run);

    return result != 0;
}

unittests.h

/*
    Unit testing of the code for a better code, a better assignment and a better future.
    Reference material - http://www.jera.com/techinfo/jtns/jtn002.html
*/

#ifndef _UNITTESTS_H_   /* Include guard */
#define _UNITTESTS_H_

#define assert_test(message, test) do { if (!(test)) return message; } while (0)
#define run_test(test) do { char *message = test(); tests_run++; if (message) return message; } while (0)
extern int tests_run;

#endif