I am attempting to build an Expression tree from fully parenthesized infix notation in Ada. I am building the tree recursively. Each node has a data field, and a pointer to left and right children. The following is what I have put together for implementation.
WITH Ada.Integer_Text_IO, Ada.Text_IO;
USE Ada.Text_IO;
PACKAGE BODY Tree_Expression IS
FUNCTION To_String (
Input : Tree_String)
RETURN String IS
Last : Natural := 0;
BEGIN
FOR I IN Input'RANGE LOOP
IF Input(I) /= ' ' THEN
Last := Last + 1;
END IF;
END LOOP;
RETURN Input(Input'First .. Last);
END To_String;
FUNCTION To_Number (
Input : String)
RETURN Float IS
Output : Integer;
First : Integer := - 1;
Last : Positive;
BEGIN
FOR I IN Input'RANGE LOOP
IF Input(I) IN '0'..'9' THEN
First := I;
EXIT;
END IF;
END LOOP;
IF First = -1 THEN
RAISE Number_Error;
END IF;
IF First = Input'First THEN
Ada.Integer_Text_IO.Get(
From => Input,
Item => Output,
Last => Last);
RETURN Float(Output);
ELSE
Ada.Integer_Text_IO.Get(Input(First .. Input'Last), Output, Last);
RETURN Float(Output);
END IF;
END To_Number;
FUNCTION To_Char (
Input : String)
RETURN Character IS
BEGIN
FOR I IN Input'RANGE LOOP
IF Input(I) = '*' OR Input(I) = '/' OR Input(I) = '+' OR Input(I) = '-' OR Input(I) = '^' THEN
RETURN Input(I);
END IF;
END LOOP;
RAISE Operator_Error;
END To_Char;
FUNCTION Construct_ExpressionTree (
Expression_String : String;
First,
Last : Natural)
RETURN Expression_Node_Ptr IS
Depth : Natural := 0;
Pos : Natural := 0;
Operator : Character := ' ';
Number_String : Tree_String;
Operator_String : Tree_String;
Build_Num_Str : Natural := Number_String'First;
BEGIN
FOR I IN First..Last LOOP
CASE(Expression_String(I)) IS
WHEN '(' =>
Depth := Depth + 1;
WHEN ')' =>
Depth := Depth - 1;
WHEN '+'|'-'|'*'|'/'|'^' =>
IF Depth = 1 THEN
Pos := I;
Operator := Expression_String(I);
EXIT;
END IF;
WHEN OTHERS =>
NULL;
END CASE;
END LOOP;
IF Operator = '+' OR Operator = '-' OR Operator = '*' OR Operator = '/' OR Operator = '^' THEN
Operator_String(Operator_String'First) := Operator;
FOR I IN Operator_String'RANGE LOOP
IF I > Operator_String'First THEN
Operator_String(I) := ' ';
END IF;
END LOOP;
RETURN Binary_Expression_Tree.Create_Node(Operator_String, Construct_ExpressionTree(Expression_String,
Expression_String'First+1, Pos-1), Construct_ExpressionTree(Expression_String, Pos+1, Expression_String'Last-1));
ELSE
FOR I IN First..Last LOOP
IF Expression_String(I) IN '0'..'9' THEN
Number_String(Build_Num_Str) := Expression_String(I);
Build_Num_Str := Build_Num_Str +1;
ELSIF Expression_String(I) = ')' THEN
EXIT;
ELSE
NULL;
END IF;
END LOOP;
IF Build_Num_Str = Number_String'First THEN
RAISE Number_Error;
END IF;
FOR I IN Build_Num_Str..Number_String'Last LOOP
Number_String(I) := ' ';
END LOOP;
RETURN Binary_Expression_Tree.Create_Node(Number_String, NULL, NULL);
END IF;
END Construct_ExpressionTree;
FUNCTION Evaluate_Expression (
Node : Expression_Node_Ptr)
RETURN Float IS
FUNCTION Eval (
Node : Expression_Node_Ptr)
RETURN Float IS
Data : Tree_String := Binary_Expression_Tree.Get_Data (Node);
Operator : Character;
BEGIN
Operator := To_Char(Data);
CASE Operator IS
WHEN '+' =>
RETURN Eval(Binary_Expression_Tree.Get_Left_Child(Node)) + Eval(Binary_Expression_Tree.Get_Right_Child(Node));
WHEN '-' =>
RETURN Eval(Binary_Expression_Tree.Get_Left_Child(Node)) - Eval(Binary_Expression_Tree.Get_Right_Child(Node));
WHEN '*' =>
RETURN Eval(Binary_Expression_Tree.Get_Left_Child(Node)) * Eval(Binary_Expression_Tree.Get_Right_Child(Node));
WHEN '/' =>
RETURN Eval(Binary_Expression_Tree.Get_Left_Child(Node)) / Eval(Binary_Expression_Tree.Get_Right_Child(Node));
WHEN '^' =>
RETURN Eval(Binary_Expression_Tree.Get_Left_Child(Node)) ** Natural(Eval(Binary_Expression_Tree.Get_Right_Child(Node)));
WHEN OTHERS =>
RAISE Expression_Error;
END CASE;
EXCEPTION
WHEN Operator_Error =>
RETURN To_Number(Data);
END Eval;
BEGIN
RETURN Eval (Node);
END Evaluate_Expression;
FUNCTION Infix_Notation (
Node : Expression_Node_Ptr)
RETURN String IS
BEGIN
RETURN Binary_Expression_Tree.Inorder_Traversal(Node);
END Infix_Notation;
FUNCTION Prefix_Notation (
Node : Expression_Node_Ptr)
RETURN String IS
BEGIN
RETURN Binary_Expression_Tree.Preorder_Traversal(Node);
END Prefix_Notation;
FUNCTION Postfix_Notation (
Node : Expression_Node_Ptr)
RETURN String IS
BEGIN
RETURN Binary_Expression_Tree.Postorder_Traversal(Node);
END Postfix_Notation;
END Tree_Expression;
My issue is that when I enter an expression, for example, ((5+6)*(1-3)), the tree is being built incorrectly. My output from an in order traversal of the tree built from that expression is 5+6*5+6-3 instead of 5+6*1-3. Basically, the left child of the root's right child (1) is not being added to the tree, and (5+6) is being added again in its place.
Create_Node, which is a function called in the construction function, looks like:
FUNCTION Create_Node (
Data : Item_Type;
Left_Child,
Right_Child : Node_Ptr)
RETURN Node_Ptr IS
BEGIN
RETURN NEW Node_Type'(Data, Left_Child, Right_Child);
END Create_Node;
This is for homework - I'm just looking for pointers as to what is going wrong in general, and sections of my code that it would make sense to look at. Thanks in advance.
Edited after feedback:
Here's my thought process, hopefully it tracks:
- Start by finding the operator at depth = 1, which will be the root node for the tree.
- Once I have that, I create a node, with everything to the left being sent back into the construct function as the left child, and everything to the right being sent back in as the right child. As I understand it, this is the recursive method to building the tree.
- Every time the function is called, it should find the operator at depth 1, which will be the next node down. If no operators are found, it should make leaf nodes with numbers. There's a loop there that parses input and builds a number string to store in the node, so multiple digits should work. I've been thinking about it, and I'm thinking something may be fishy with the First and Last being sent back into Construct_ExpressionTree.
And I was just playing with it and got a test case to work. I was sending the wrong info back into the function.
