2
Ada에서 완전히 괄호로 묶인 중절 표기법으로 표현식 트리를 작성하려고합니다. 나는 재귀 적으로 나무를 짓고있다. 각 노드에는 데이터 필드와 왼쪽 및 오른쪽 자식에 대한 포인터가 있습니다. 다음은 구현을 위해 함께 사용한 것입니다.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)가 그 위치에 다시 추가됩니다. 이 숙제입니다
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;
- 그냥 잘못 일반적으로 무슨 일이 일어나고 있는지에 관해서는 포인터를 찾고, 그리고 섹션 해요 : 같은 건설 함수를 호출하는 기능입니다
Create_Node은 보인다 내 코드를 보면 이해할 만하다. 미리 감사드립니다. 피드백 후 편집
: 는 여기에 희망이 추적, 내 생각 과정입니다 :
- 트리의 루트 노드가 될 깊이 = 1에서 운영자를 찾아 시작합니다.
- 일단 그 노드를 만들면 왼쪽에있는 모든 것이 왼쪽 자식으로 생성 기능으로 다시 보내지고 오른쪽에있는 모든 것이 올바른 자식으로 다시 보내지는 노드가 만들어집니다. 내가 알기에 이것은 나무를 만드는 재귀 적 방법이다.
- 함수가 호출 될 때마다 깊이 1에서 다음 노드가 될 연산자를 찾아야합니다. 연산자가 발견되지 않으면 잎 노드에 숫자가 있어야합니다. 여기에는 입력을 파싱하고 노드에 저장할 숫자 문자열을 만드는 루프가 있으므로 여러 자리가 작동해야합니다. 나는 그것에 대해 생각 해왔다. 그리고 나는 처음과 마지막이 Construct_ExpressionTree로 다시 보내지는 것에서 어떤 것이 비린내 일 수 있다고 생각하고있다.
그리고 나는 그저 놀고 있었고 작동 할 테스트 케이스를 얻었다. 잘못된 정보를 다시 함수에 보냈습니다.
언급하는 것을 잊었다 - 나무를 건설하기 위하여 이용되는 기능은 Construct_ExpressionTree에게 불리고 부호의 중간에 대략 시작된다. –
1> Ive의 모양은 매우 빠르며 노드가 있어야하는 깊이를 어떻게 결정했는지 의심 스럽습니다. 2> 이것은 본질적으로 재귀적인 문제입니다. 재귀를 사용하지 않는 이유가 있습니까? 3> '깊이 = 1'을 확인하십시오. 이것은 나무의 2 레벨 만 얻을 수 있음을 의미합니까? 4> 한 자리 숫자 만 확인하면 충분합니까? – NWS