Помощь - Поиск - Пользователи - Календарь
Полная версия: Упростить дерево-формулу!
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Веталь
Формулу вида
<формула >::=<терминал >|(<формула ><знак><формула >)
<знак>::= + | – | * | /
<терминал >::=<переменная>|<цифра >
<переменная>::=a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z
<цифра >::=0|1|2|3|4|5|6|7|8|9
можно представить в виде двоичного дерева по следующим правилам:
формула из одного терминального символа (цифры или переменной )
представляется деревом, состоящим из одной вершины, содержащей этот
символ, а формула вида (f1 s f2) — деревом, в котором корень — это знак s, а
левое и правое поддеревья — это соответствующие представления формул
f1 и f2. О писать подпрограмму, которая:
преобразует дерево-формулу, заменяя в нем все поддеревья,
соответствующие формулам ((f1 +- f2) * f3) и (f1 * (f2 + - f3)), на поддеревья,
соответствующие формулам ((f1 * f3) +-(f2 * f3)) и ((f1 * f2) +-(f1 * f3));

есть несколько готовых методов:
модуль создания корня дерева, здесь функция создания узла

unit UParentKnot;

interface


type
PNode = ^TNode;
TNode = object
private
FLeft,
FRight: PNode;

public

constructor InitEmpty;

Procedure Print; virtual;

function LoadFromStr (var str : string ; var i : integer) : boolean; virtual;
Procedure SaveToText(var F: Text); virtual;

{-}function Calculate: real; virtual;

procedure Clear;
destructor done; virtual;

Function GetLeft: PNode;
Function GetRight: PNode;

procedure SetLeft(ANode : PNode);
procedure SetRight(ANode : PNode);


end;

function NewNode (var str : string; var i : integer): PNode;


implementation

uses
SysUtils,
UIntKnot,
UVarNameKnot,
USignKnot;

function NewNode(var str: string; var i: integer): PNode;
begin
While (i<=Length(str)) and (str[i]=' ') do
inc(i);
if i>Length(str)
then Result:=nil
else
begin
case str[i] of
'0','1'..'9': Result:=New(PIntNode, InitEmpty);
'a'..'z': Result:=New(PVarNode, InitEmpty);
'(': Result:=New(PSignNode, InitEmpty);
else Result:=nil
end;
if Result<> nil
then
if not result.LoadFromStr(str,i)
then
begin
dispose(Result);
Result:=nil;
end;
end;
end;


добавление числа в дерево

uses
UParentKnot, SysUtils;

type
TElem = integer;
PIntNode = ^TIntNode;
TIntNode = object(TNode)
private
FInf: TElem;

public
constructor InitEmpty;
constructor Init(AInf: TElem);

procedure Input; virtual;
procedure Print; virtual;

function LoadFromStr (var str : string ; var i : integer) : boolean; virtual;
Procedure SaveToText(var f: TextFile); virtual;

{-}function Calculate: real; virtual;

Function GetInf: TElem;
Procedure SetInf(AInf: TElem);

end;



добавление переменной в дерево

TElem = string;
PVarNode = ^TVarNode;
TVarNode = object(TNode)
private
FInf: TElem;

public
Constructor InitEmpty;
constructor Init(AInf: TElem);

procedure Input; virtual;
procedure Print; virtual;

function LoadFromStr (var str : string ; var i : integer) : boolean; virtual;
Procedure SaveToText(var F: TextFile); virtual;

function Calculate: real; virtual;

Function GetInf: TElem;
Procedure SetInf(AInf: TElem);
end; {object}



добавление знака в дерево

type
TSign = (add,subtr,mult,divide,empty);
TElem = TSign;
PSignNode = ^TSignNode;
TSignNode = object (TNode)
private
FInf: TElem;
public

constructor InitEmpty;
constructor Init(AInf: TElem);

Procedure Input; virtual;
procedure Print; virtual;

function LoadFromStr (var str : string ; var i : integer) : boolean; virtual;
Procedure SaveToText(var f: TextFile); Virtual;

function Calculate: real; virtual;

Function GetInf: TElem;
Procedure SetInf(AInf: TElem);
end;{object}

const
NameSign: array [TSign] of char = ('+', '-', '*', '/', '?');

procedure ReadSign (var Sign: TSign);
function StrToSign(ch:char):TSign;



И, собственно, загрузка формулы из файла

Type
TFormula = object
Private
FRoot: PNode;

Public
constructor Init;

Procedure LoadFromText(FName: string);
Function LoadFromStr(str: string): boolean;

Procedure SaveToText (FName: string);
Procedure Print;

Function Calculate: real;

Procedure Clear;
end;


function TIntNode.LoadFromStr (var str : string ; var i : integer) : boolean;
var d: string;
begin
d:='';
While (i<=length(str)) and (str[i] in ['0'..'9']) do
begin
d:=d+str[i];
inc(i);
end;
FInf:=StrToInt(d);
Result:=true;
end;


function TVarNode.LoadFromStr (var str : string ; var i : integer) : boolean;
var c: string;
begin
c:='';
While (i<=length(str))and(str[i] in ['a'..'z']) do
begin
c:=c+str[i];
inc(i);
end;
FInf:=c;
VarMas.Add(FInf);
Result:=true;
end;

function TSignNode.LoadFromStr (var str : string ; var i : integer) : boolean;
begin
Result:=true;
if (i>Length(str)) then
Result:=false
else
if str[i]<>'(' then
Result:=false
else
begin
i:=i+1;
While (i<=Length(str)) and (str[i]=' ') do
inc(i);
SetLeft(NewNode(str,i));
if GetLeft=nil
Then result:=false
else
begin
While (i<=Length(str)) and (str[i]=' ') do
inc(i);
if (i>Length(str)) or not (Str[i] in ['+','-','*','/']) then
Result:=false
else
begin
FInf:=StrToSign(Str[i]);
i:=i+1;
While (i<=Length(str)) and (str[i]=' ') do
inc(i);
SetRight(NewNode(str,i));
if GetRight=nil then
Result:=false
else
begin
While (i<=Length(str)) and (str[i]=' ') do
inc(i);
if (i>Length(str)) or (str[i]<>')') then
Result:=false
else
i:=i+1;
end;
end
end;
end;
end;

Procedure TFormula.LoadFromText(FName: string);
var
F: Text;
s, str: string;
begin
AssignFile(F,FName);
reset(f);
str:='';
while not eof(f) do
begin
readln(f, s);
str:=str+s
end;
close(f);
if not LoadFromStr(str)
then writeln;
end;



Помогите пожалуйста дописать нехватающие методы и оформить задачу. Заранее спасибо, кто поможет
volvo
Тему скрыл временно, до 1-го мая. Топикстартер уведомлен в PM.
volvo
Ну, в общем, тема открыта даже раньше, чем я говорил. Итак, по порядку:

1) я не знаю, зачем ты привел здесь эти куски программы, они ничего не дают. Либо надо было приводить только структуру классов, либо - программу, строящую дерево разбора полностью. Третьего не дано. Я не думаю, что кто-то будет подгонять программу, чтобы она легла точно на описания классов, которые привел ты. Тем более, что ты явно что-то перемудрил, все делается гораздо проще...

2) теперь о том, как это - "проще". Вот так:

Запусти программу и посмотри на результаты ее работы. Она сначала строит дерево разбора для приведенного выражения и вычисляет его, а потом
Цитата
преобразует дерево-формулу, заменяя в нем все поддеревья,
соответствующие формулам ((f1 +- f2) * f3) и (f1 * (f2 + - f3)), на поддеревья,
соответствующие формулам ((f1 * f3) +-(f2 * f3)) и ((f1 * f2) +-(f1 * f3));
и снова вычисляет значение выражения. При правильной замене значение всего выражения должно остаться неизменным. Смотри, разбирайся. Это можно было бы еще немного укоротить, но я этого делать не стал, боюсь, скажется на читабельности. Если разберешься в алгоритме создания дерева и замены поддеревьев, с легкостью сократишь программу самостоятельно... Пробуй smile.gif
Гость
спасибо, буду разбираться smile.gif
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.