我正在尝试从 Ada 中完全带括号的中缀符号构建表达式树。我正在递归地构建树。每个节点都有一个数据字段，以及一个指向左右子节点的指针。以下是我为实施而整理的内容。
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;
我的问题是，当我输入表达式时，例如 ((5+6)*(1-3))，树的构建不正确。我从该表达式构建的树的按顺序遍历的输出是 5+6*5+6-3 而不是 5+6*1-3。基本上，根的右孩子 (1) 的左孩子没有被添加到树中，并且 (5+6) 被再次添加到它的位置。
Create_Node，这是一个在构造函数中调用的函数，看起来像：
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;
这是做作业的——我只是在寻找关于一般问题的指针，以及我的代码中可以查看的部分。提前致谢。
反馈后编辑：这是我的思考过程，希望它跟踪：
- 首先找到深度 = 1 的运算符，这将是树的根节点。
- 一旦我有了这个，我创建一个节点，左边的所有东西都作为左孩子送回构造函数，右边的所有东西都作为右孩子送回。据我了解，这是构建树的递归方法。
- 每次调用该函数时，它应该在深度 1 处找到运算符，这将是下一个节点。如果没有找到运算符，它应该使叶子节点带有数字。那里有一个循环来解析输入并构建一个数字字符串以存储在节点中，因此多个数字应该可以工作。我一直在考虑它，我在想第一个和最后一个被送回 Construct_ExpressionTree 可能有些可疑。
我只是在玩它并得到一个测试用例。我将错误的信息发送回函数。