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*1-3 ではなく 5+6*5+6-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 で演算子を見つける必要があります。これは、次のノードの下になります。演算子が見つからない場合は、番号を持つリーフ ノードを作成する必要があります。入力を解析し、ノードに格納する数値文字列を作成するループがあるため、複数の数字が機能するはずです。私はそれについて考えてきました.FirstとLastがConstruct_ExpressionTreeに送り返されているので、何か怪しいかもしれないと考えています.
そして、私はそれで遊んでいて、テストケースが機能するようになりました。関数に間違った情報を送り返していました。