-
parsing a binary tree
Hi everyone, I'm writing a program to parse an expression into a binary tree. The expression is like this
Code:
char expr[]={'6','7','+','8','/','3','*','1','-','7'};
and I just realized that there is no way I can represent a tree on here, but you probably know how it goes: each node has a value and two pointers, one going down to the left and the other down to the right. I'm working on the algorithm and I have 5 sheets covered with trees, but I can't seem to figure out a good one. Right now it goes:
create nodes for each high_op('/' and '*')
if there is not any low_op('+' and '-') between two high_ops then
link from right to left so that the left pointer of the right high_op points to the high_op that is to the left of it
else each high_op pointer links to the numbers on either side.
ditto for the low_ops
My problem is that I cant figure out how to connect the low_ops and the high_ops together. Is it practical to rearrange the string so that the ablove becomes 83*1-7+67? I would appreciate any tips, better procedures, insults, flames, etc. No code, though. You dont have to write it for me. Thank you very much.
PS I do have code but every time I stop to think I realize that there is a (seemingly) better way to do it and it all becomes useless.
-
Build the tree so that the operators with higher precedence are further along in the tree so that they are evaluated first:
Code:
expression: 2 * 5 + 30 * 2 * 4
tree:
+
* *
2 5 30 *
2 4
Assuming you are using right to left evaluation, the program would traverse the tree until it reached a value instead of an operator and then evaluate that expression. Then do the same thing for the next level up using the result, and so on. So this tree would be evaluated like so:
( ( 2 * 5 ) + ( 30 * ( 2 * 4 ) ) )
-Prelude
-
Okay, you have two kinds of expressions here. I will call them expr1, and expr2.
an expr1 is a left assosiative bunch of expr2s that are added or subtracted. Your entire equation is going to be an expr1...
An expr2 is a left associative bunch of numbers that are multiplied or divided...
expr1:
expr2
expr1 + expr2
expr1 - expr2
expr2:
number
expr2 * number
expr2 / number
The only good way I really know to process something like this is with a for loop for each one. (Incidentally, I suggest first writing a program that will calculate the expression, and then later modify it to produce a postfix representation.)
2 * 5 + 30 * 2 * 4
Code:
Process entire statement as expr1
Grab the first expr2 in the expr1
Grab the first number in the expr2 (it's a 2) // Make a 2 node
Grab the operator (it's a *) // Make a * node
Use * operator with next number (5) // Make a 5 node
2 * 5 = 10 // Put nodes together
Grab next operator (it's a +)
Can't process +, this expr2 is over. Return 10. // Return the tree
The first expr2 was a 10. // Result is really a tree
Grab the next operator (it's a +). // Make a + node
Grab the next expr2
Grab the first number in the expr2 (it's a 30) // Make a 30 node
Grab the operator (it's a *) // Make a * node
Grab the next number (it's a 2) // Make a 2 node
30 * 2 = 60 // Put the nodes together
Grab the next operator (it's a *) // Make a * node
Grab the next number (it's a 4) // Make a 4 node
60 * 4 = 240 // Connect the nodes. The left child will be the 30 * 2 tree
Grab the next operator. (It's end of input)
Can't process, this expr2 is over. Return 240. // Return the tree
The second expr is 240. // Result is the tree we just made
10 + 240 = 250 // Connect the 2 expr2s using the + node as parent
Grab the next operator (It's end of input)
Can't process. This expr1 is over. Return 250 // Return the tree
Result is 250 // Result is tree
And finally the tree we get looks like this
-
thank you all for your help. I've been working on it when I have free time. I've decided to do a recursive sort of thingy that goes like this:
Code:
function parse(str[],int k
if the array element k is high_op, call parse again, start at k+1
if element is low_op, call parse again, start at k+1
if element is digit, return element
the problem i am having is trying to deal with the recursion concept. I just can't seem to get a handle on it. Will the above handle the order of operations correctly, since high_op is checked for low_op? About the linking: Does each successive parse result become a parent of the previous result?
Code:
int parse(char fstr[],int start)
{
int i;
int val;
char c;
for (i=start+1;i<length;i++){
c=fstr[i];
if (pri_op(c)) {array[i]->data=parse(fstr,i);}
else if (sec_op(c)) {array[i]->data=parse(fstr,i);}
else if (isdigit(c)) {array[i]->data=c-'0';}
/*not sure about where to go from here*/
I would appreciate as always any help. Is there an easy way to write out a Backus Naur Form specification type of thingie in C?
