I am attempting to make and evaluate a binary expression tree based on a postfix user input string in C. My binary tree initialization function is causing memory leaks, however. To summarize my algorithm, the user enters a postfix string of input which is parsed through by a function and assembled into the tree. Here's my full code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TRUE 1
#define FALSE 0
// Define binary expression tree data structure
typedef struct binExpTree {
char *val;
struct binExpTree *left;
struct binExpTree *right;
} expTree;
// Define expression tree stack data structure
typedef struct expTreeStack {
int height;
int used;
expTree **expTreeDarr;
} treeStack;
// Function prototypes
void initStack(treeStack *stack);
expTree * getTopStack(treeStack *stack);
int isEmptyStack(treeStack *stack);
void pushStack(treeStack *stack, expTree *treeNode);
expTree * popStack(treeStack *stack);
void clearStack(treeStack *stack);
expTree * initTree(char *val);
void printCommands();
expTree * parseExpression(char *expString);
void clearTree(expTree *rootNode);
void printInfix(expTree *rootNode);
void printPrefix(expTree *rootNode);
int evalExpression(expTree *rootNode);
/* File contains all functions necessary for stack operations */
// Initialize empty binary tree stack of size 4
void initStack(treeStack *stack) {
stack->height = 4;
stack->used = 0;
stack->expTreeDarr = (expTree **)malloc(sizeof(expTree *) * stack->height);
}
// Return the tree node from the stack's top
expTree * getTopStack(treeStack *stack) {
if (stack->used > 0) {
return stack->expTreeDarr[stack->used - 1];
}
else {
return NULL;
}
}
// Discern whether tree stack is empty
int isEmptyStack(treeStack *stack) {
if (stack->used == 0) {
return TRUE;
}
else {
return FALSE;
}
}
// Push tree node pointer onto stack
void pushStack(treeStack *stack, expTree *treeNode) {
if (stack->used == stack->height) {
expTree **expTreeTmp = stack->expTreeDarr;
stack->height += 4;
stack->expTreeDarr = (expTree **)malloc(sizeof(expTree *) * stack->height);
for (int i = 0; i < stack->used; i++) {
stack->expTreeDarr[i] = expTreeTmp[i];
//free(expTreeTmp[i]);
}
free(expTreeTmp);
}
stack->expTreeDarr[stack->used] = treeNode;
stack->used = stack->used + 1;
}
// Pop tree node pointer from the stack
expTree * popStack(treeStack *stack) {
expTree *stackTmp = getTopStack(stack);
expTree *newNode = (expTree *)malloc(sizeof(expTree));
*newNode = *stackTmp;
stack->used -= 1;
return newNode;
}
// Empty stack of all data (make sure this works)
void clearStack(treeStack *stack) {
for (int i = 0; i < stack->used; i++) {
clearTree(stack->expTreeDarr[i]);
}
free(stack->expTreeDarr);
stack->used = 0;
stack->height = 0;
}
/* File contains all functions necessary for binary tree operations */
// Initialize binary expression tree with specified operator/operand
expTree * initTree(char *val) {
expTree *newTree = (expTree *)malloc(sizeof(expTree));
newTree->val = (char *)malloc(strlen(val) + 1);
strcpy(newTree->val, val);
newTree->left = NULL;
newTree->right = NULL;
return newTree;
}
// Print commands available to the user
void printCommands() {
printf("The commands for this program are:\n\n");
printf("q - to quit the program\n");
printf("? - to list the accepted commands\n");
printf("or any postfix mathematical expression using the operators of *, /, +, -\n");
}
// Return size of binary expression tree
int sizeTree(expTree *treeNode) {
if (treeNode == NULL) {
return 0;
}
else {
return 1 + sizeTree(treeNode->left) + sizeTree(treeNode->right);
}
}
// Construct a postfix binary expression tree from expression string
expTree * parseExpression(char *expString) {
char *expStringCopy = (char *)malloc(strlen(expString) + 1);
expTree *treeNode;
treeStack expStack;
initStack(&expStack);
strcpy(expStringCopy, expString);
char *expStringTok = strtok(expStringCopy, " ");
while (expStringTok != NULL) {
if (*expStringTok == '+' || *expStringTok == '-' ||
*expStringTok == '*' || *expStringTok == '/') {
if (expStack.used < 2) {
return NULL;
}
treeNode = initTree(expStringTok);
treeNode->right = popStack(&expStack);
treeNode->left = popStack(&expStack);
pushStack(&expStack, treeNode);
}
else {
treeNode = initTree(expStringTok);
pushStack(&expStack, treeNode);
}
expStringTok = strtok(NULL, " ");
}
if (expStack.used > 1 || (*(treeNode->val) != '+' && *(treeNode->val) != '-' &&
*(treeNode->val) != '*' && *(treeNode->val) != '/')) {
return NULL;
}
free(expStringCopy);
treeNode = popStack(&expStack);
clearStack(&expStack);
return treeNode;
}
// Clear binary expression tree
void clearTree(expTree *rootNode) {
if (rootNode == NULL) {
return;
}
else {
clearTree(rootNode->left);
clearTree(rootNode->right);
free(rootNode->val);
free(rootNode);
}
}
// Print infix notation of expression
void printInfix(expTree *rootNode) {
if (rootNode == NULL) {
return;
}
else {
if (*(rootNode->val) == '+' || *(rootNode->val) == '-' ||
*(rootNode->val) == '*' || *(rootNode->val) == '/') {
printf("( ");
}
printInfix(rootNode->left);
printf(" %s ", rootNode->val);
printInfix(rootNode->right);
if (*(rootNode->val) == '+' || *(rootNode->val) == '-' ||
*(rootNode->val) == '*' || *(rootNode->val) == '/') {
printf(" )");
}
}
}
// Print prefix notation of expression
void printPrefix(expTree *rootNode) {
if (rootNode == NULL) {
return;
}
else {
printf(" %s ", rootNode->val);
printPrefix(rootNode->left);
printPrefix(rootNode->right);
}
}
// Evaluate the expression tree
int evalExpression(expTree *rootNode) {
char op;
if (*(rootNode->val) == '+') {
return evalExpression(rootNode->left) + evalExpression(rootNode->right);
}
else if (*(rootNode->val) == '-') {
return evalExpression(rootNode->left) - evalExpression(rootNode->right);
}
else if (*(rootNode->val) == '*') {
return evalExpression(rootNode->left) * evalExpression(rootNode->right);
}
else if (*(rootNode->val) == '/') {
return evalExpression(rootNode->left) / evalExpression(rootNode->right);
}
else {
return atoi(rootNode->val);
}
}
int main(int argc, char const *argv[])
{
char input[300];
expTree *expPostfix;
/* set up an infinite loop */
while (1)
{
fgets(input,300,stdin);
/* remove the newline character from the input */
int i = 0;
while (input[i] != '\n' && input[i] != '\0') {
i++;
}
input[i] = '\0';
/* check if user enter q or Q to quit program */
if ( (strcmp (input, "q") == 0) || (strcmp (input, "Q") == 0) )
break;
/* check if user enter ? to see command list */
else if ( strcmp (input, "?") == 0)
printCommands();
/* user enters an expression */
else {
// Parse the expression into a binary expression tree
printf("%s\n", input);
expPostfix = parseExpression(input);
// Discern whether expression is valid
if (expPostfix == NULL) {
printf("Invalid expression. Enter a valid postfix expression \n");
continue;
}
// Print the expression in infix notation
printf("Infix notation: ");
printInfix(expPostfix);
printf("\n");
// Print the expression in prefix notation
printf("Prefix notation: ");
printPrefix(expPostfix);
printf("\n");
// Print the expression in postfix notation
printf("Postfix notation: ");
printf("%s\n", input);
// Evaluate expression and print result
printf("Expression result: %d \n\n", evalExpression(expPostfix));
clearTree(expPostfix);
}
}
printf("\nGoodbye\n");
return 0;
}
Upon running with Valgrind and an input of "1 1 -", this is the output:
==35604==
==35604== HEAP SUMMARY:
==35604== in use at exit: 72 bytes in 3 blocks
==35604== total heap usage: 13 allocs, 10 frees, 2,236 bytes allocated
==35604==
==35604== 24 bytes in 1 blocks are definitely lost in loss record 1 of 2
==35604== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==35604== by 0x10952C: initTree (proj4base_38.c:143)
==35604== by 0x1096CC: parseExpression (proj4base_38.c:194)
==35604== by 0x109B8A: main (proj4base_38.c:323)
==35604==
==35604== 48 bytes in 2 blocks are definitely lost in loss record 2 of 2
==35604== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==35604== by 0x10952C: initTree (proj4base_38.c:143)
==35604== by 0x109719: parseExpression (proj4base_38.c:201)
==35604== by 0x109B8A: main (proj4base_38.c:323)
==35604==
==35604== LEAK SUMMARY:
==35604== definitely lost: 72 bytes in 3 blocks
==35604== indirectly lost: 0 bytes in 0 blocks
==35604== possibly lost: 0 bytes in 0 blocks
==35604== still reachable: 0 bytes in 0 blocks
==35604== suppressed: 0 bytes in 0 blocks
==35604==
==35604== For lists of detected and suppressed errors, rerun with: -s
==35604== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)
So it seems the culprit is my initTree() function. However, I just cannot wrap my head around why this memory is being lost. I hope this isn't too much code. This is an edit from previously, where someone informed me there was not enough information to go on.
The leak is caused by popStack, because the target of stackTmp gets leaked when the function exits:
expTree * popStack(treeStack *stack) {
expTree *stackTmp = getTopStack(stack);
expTree *newNode = (expTree *)malloc(sizeof(expTree));
*newNode = *stackTmp;
stack->used -= 1;
return newNode;
}
Given that the stack seemed to be the exclusive owner of the tree, and it no longer has a pointer to it, popStack can avoid the leak by simply not making a copy and returning the original:
expTree * popStack(treeStack *stack) {
expTree *topNode = getTopStack(stack);
stack->used -= 1;
return topNode;
}