Help with a recursive expression tree program

**TeamRival** · 03-25-2011

Hey everyone I'm trying to write a program in C that will evaluate and display an expression tree correctly through the use of recursion. So an expression such as : 3 + 4 * 5 - 56/7 will evaluate correctly as (3 + (4 * 5)) - (56/7). I have been writing a header class that defines all needed type definitions and functions. Here's the code in progress so far :

Code:

#ifndef TREE_NODE
#define TREE_NODE

typedef struct Node_t {
	int				value;
	struct Node_t	*left;
	struct Node_t	*right;
} Node, *Node_p;

typedef char *String;

	char* s = "string";

typedef enum {false, true} bool;

void setNode(Node_p np,
			int		value,
			Node_p	left,
			Node_p	right,
			bool	display);

	value = (value, NULL, NULL);

String nodeToString(Node_p np);

int eval(Node_p np);

#endif

This code will be used by a test class that I will develop to test and see if everything is working properly. My problem is starting off the setNode function. I'm not exactly sure as to how I go about getting started on defining each type of Node. There should be a few "types":
-one that is just a numeric value, such as a 2. This won't have a pointer to either the left node or the right node.
-one for each arithmetical function multiply and times, and with pointers to either the left node or right node, or both.
This is actually my first program written in C, I haven't been studying it for more than a month, as I've mostly worked with Java to this point so it's a bit overwhelming to have a program working with recursion and a few other elements that I'm not used to using in C. Any sort of suggestions on how I should proceed or where there is error in my thinking will be greatly appreciated. I'm just not sure how setNode should proceed, am I supposed to create a Node for each case that I may run into, or am I looking at this from the wrong point of view?
Thanks again!

**quzah** · 03-25-2011

It doesn't sound like you actually have different node types. Rather, it sounds like you have to decide how to handle each point along the way that you encouner:

3 + 4

That makes you have one node that stores the + operator, and points to a left node that just stores a 3, and a right node that just stores a 4.

Start with simple cases and get that working. Make it parse your input so the above works, and that when you pass that tree (the node with the +) to the "do stuff" function, that it will do the math by reading the tree for you. Then worry about the other operators and parenthesis later.

Quzah.

**TeamRival** · 03-25-2011

where I'm having trouble is with trying to create each node. If the node is just a value (like a 2) it will have two nulls for the right and left pointers. If it's an operator it will have 1 or 2 nonnull pointers(those pointers usually pointing to a value). if its a binary operator (such as + or *) it will use both the left and right pointers to point to a value. I figured out how I'm going to set up the evaluate portion. I'm just going to make a switch statement that will take care of each case I can have.
I'm not exactly sure how to go about making each case for the nodes in the setNode function. do I just define each separate nodecase that I can have? Sorry I'm just frustrated because I'm still very new to C and this program, while easy to understand how it will work, is a pain in the neck to sit down and code.

**quzah** · 03-25-2011

Read in a line.
Look at the first value.

Code:

if number
    look at the next value
else
if operator
    take previous value and next value to form a node

That's the general idea. Honestly you may just want to go through and push everything onto a stack (search the forum for stack and expression tree or something similar), then pop them off to build your nodes.

It doesn't really matter how you do it, but the general idea is to grab one chunk, and see what to do with it, as I implied above.

Quzah.

**TeamRival** · 03-25-2011

Ok so I'm following your logic, but what should I do when I run into an operator? Value is defined as an int so it would not be able to accept a char such as "+" or "*". I'm assuming I set up an if statement such as If (np == int) then node np = (value, NULL, NULL) it will be able to store the value at least. and then using If else statements I will set up each individual case for the few variations on the nodes I can have.
There's a few other ways to write this sort of program (as I did check out the forums to see if I could find any help) but I'm trying to stick to the code that I provided since it's the way I learned how to make this happen.

**quzah** · 03-25-2011

You can use it to store the operator, but you would need to be keeping track some place of what it is you expect to see. For example:

(1+2) + 3

Are you just trying to solve this, or are you trying to keep track of all of the pieces: ( and 1 and + and 2 and ) and + and 3? Because it matters with how you handle all of the pieces.

You could always just add another piece to your structure that says "this is an operator".

You need to be able to do this on paper first before you start turning it into a program. You need to know what you are going to do in a tree with anything you encounter.

Quzah.

**TeamRival** · 03-25-2011

ok so for setNode would this little piece of code be sufficient? I defined a new int called operator in both setNode and Node_T which I will have set to look for any operator and it will take care of that node accordingly.

Code:

void setNode(Node_p np,
			int		value,
			int     operator,
			Node_p	left,
			Node_p	right,
			bool	display);

		For each (value)
		Node np =(value, NULL, NULL, true);
		For each (operator)
		Node np =(operator, *left, *right, true);

The true values are for displaying the node, but at this rate I'm not going to be able to figure out how to get this going properly. I did write down all the functions I wanted to include and a diagram of how this thing would work. I would be able to write something to handle this in Java but most of the help I've tried to look for online deals in either C++ or C# so it's not exactly written for just C. Thanks for the help, I just need a good kick in the you-know-what to get me moving in the right direction.

Thread: Help with a recursive expression tree program

Thread Tools

Search Thread

Display

Help with a recursive expression tree program

Similar Threads

Help with a Battleship Program

c program that accepts and executes commands?

Program Plan

Help Debugging my AVL tree program.

Screwy Linker Error - VC2005