Skip to content

Instantly share code, notes, and snippets.

@TestSubjector

TestSubjector/LogicAssignment_README.md

Last active November 15, 2017 07:01
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save TestSubjector/7ae90d70f19bd70033e28eeb4d8c53fe to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save TestSubjector/7ae90d70f19bd70033e28eeb4d8c53fe to your computer and use it in GitHub Desktop.
Download ZIP
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 ]
Raw
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;
}
Raw
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';
}
Raw
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
Raw
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
Raw
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))
*/
}
}
Raw
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
Raw
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;
}
Raw
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment