Creating an Arithmetic Expression Tree

[araisbec]

Alright, so I've spent countless hours on this code and I need a fresh pair of eyes to give it a glance...

This is my third assignment for my datastructures class, where I am to write code that turns a fully parenthesized expression (such as "((3+2)/(3-8))") into aan "arithemtic expression tree", where the internal nodes are operators and the external nodes are operands.

The following function that I have written contains a logic error somewhere I suppose, because it simply crashes when I call it. My approach uses recursion, and the function contains parameters to pass the expression (in string form), and start and end indicators (in int form, to tell the function what section of the expression it is currently dealing with).

Most of the logic in the algorithm is based around the brackets in the expression; using them to figure out where the next operator is, boundaries of the chunk of the expression, etc...

Anyway, here she is... Any help would be greatly appreciated!

typedef struct _Tree{
	char* value;
	struct _Tree* parent;
	struct _Tree* leftChild;
	struct _Tree* rightChild;
}Tree;

Tree* newNode (char* exprssn, int strt, int end){

	int i, oBrkts, cBrkts;    // Counter Variables
	Tree* node;
	node->value = malloc (sizeof (char)*6);
	int operator = 0;
	char* subExprssn;

	for (i = strt; i < end; i++){
		if (exprssn [strt] == '('){
			if (exprssn [i] == '(') oBrkts++;
			if (exprssn [i] == ')') cBrkts++;
			if (oBrkts == cBrkts && cBrkts > 0){
				strcpy(node->value, exprssn [i+1]+"");
				node->leftChild = newNode (exprssn, strt+1, i - 1);
				node->rightChild = newNode (exprssn, i+1, end - 1);
			}
		}else{ 
			if (exprssn [i] == '*' || exprssn [i] == '/' || exprssn [i] == '+' || exprssn [i] == '-'){
				strcpy (node->value, exprssn [i]+"");
				sprintf (subExprssn, "%.*s", (i - 1) - strt, &exprssn [strt]);
				node->leftChild->value = malloc (sizeof (char)*6);
				strcpy (node->leftChild->value, subExprssn);
				sprintf (subExprssn, "%.*s", (i - 1) - strt, &exprssn [strt]);
				node->rightChild->value = malloc (sizeof (char)*6);
				strcpy (node->rightChild->value, subExprssn);
			}else if ((i + 1) == end){
				sprintf (subExprssn, "%.*s", end - strt, &exprssn [strt]);
				strcpy (node->value, subExprssn);
			}
		}
	}
	return node;
}

int main () {

	//Allocate memory for user input//
	char* input = malloc (sizeof (char)*41);
		
	//Get input from user//
	printf ("Please enter a fully parenthesized algebraic expression with\nno more then two terms per bracket, and no spaces: ");
	scanf ("%s", input);
	
	//Call the recursive tree creating function "newNode"//
	Tree* root = newNode (input, 1, strlen (input) - 1);

}

[gerard4143]

Line 11 and 12...should you allocate the memory for the node first before you you allocate the memory for one of its members.

[gerard4143]

Also line 14

char* subExprssn;

You use this without allocating or assigning memory to it.

[araisbec]

Thanks a lot Gerard4143, sorry for the late reply, I've been really busy with stuff around here. I have that function running smoothly now. However, I am now having another issue, and this time it deals with a function I have written to display the tree I have created. I'm not sure where I've gone wrong with this one.

The function uses printf in a for loop to space each node value out an appropriate amount, and attempts to print (in the end) what resembles a tree structure.

I have a dynamically allocated array of strings that I am using as a buffer to write the levels of the tree to, so that in the end I can simply print the array of strings to display the tree. To add a node, I append the appropriate spacing to whatever level I am working on, and then append the value. The tree would look something like this...

*
             /       \
        -                 +
      /   \            /     \
    1       2        3         4

However, the function (as usual) is not working as expected, and inserting an absurd amount of whitespace into the levels of my beautiful tree. Heres what I've got:

int displayTree (Tree* node, int level, char** treeLevel, int* location){

	int i, temp = strlen (treeLevel [level]);

	for (i = 0; i < *location - temp; i++){
		treeLevel [level] = strcat (treeLevel [level], " ");
	}
	
	treeLevel [level] = strcat (treeLevel [level], node->value);

	if (node->leftChild != NULL){
	
		for (i = 0; i < (*location - *location / 4); i++){
			treeLevel [level+1] = strcat (treeLevel [level+1], " ");
		}

		treeLevel [level+1] = strcat (treeLevel [level+1], "/");
	
		*location = *location / 2;
       	
		level = displayTree (node->leftChild, level+2, treeLevel, location);

	}

	*location = *location*2;

	if (node->rightChild != NULL){

		for (i = 0; i < *location / 4; i++){
			treeLevel [level+1] = strcat (treeLevel [level+1], " ");
		}

		treeLevel [level+1] = strcat (treeLevel [level+1], "!");

		*location = *location + (*location / 2);
		
		level = displayTree (node->rightChild, level+2, treeLevel, location);

	}

	*location = *location - (*location / 3);

	if (level == 0){
		for (i = 0; i < 5; i++){
			printf ("\n%s", treeLevel [i]);
		}
	}

	
	return level - 2;
}