下面是代码,核心部分是MakeTree.
至于画树的代码不看也罢,仅仅为了直观一点而已.
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, ExtCtrls, StdCtrls;
type
TTree = ^TNode;
TNode = record
op: string;
LeftChild, RightChild: TTree
end;
TForm1 = class(TForm)
Panel: TPanel;
ExpressEdit: TEdit;
CalculateButton: TButton;
DrawButton: TButton;
ValueEdit: TEdit;
FormatButton: TButton;
MakeTreeButton: TButton;
PaintBox: TPaintBox;
procedure FormatButtonClick(Sender: TObject);
procedure CalculateButtonClick(Sender: TObject);
procedure FormClose(Sender: TObject;
var Action: TCloseAction);
procedure MakeTreeButtonClick(Sender: TObject);
procedure DrawButtonClick(Sender: TObject);
private
{ Private declarations }
function FindLastOpPos(s: string): Integer;
procedure DestroyTree(Root: TTree);
public
{ Public declarations }
Root: TTree;
function MakeTree(s: string): TTree;
function FormatTree(Root: TTree): string;
function CalculateTree(Root: TTree):do
uble;
procedure DrawTree(Root: TTree;
Top, Left, Right: Integer);
end;
var
Form1: TForm1;
implementation
{$R *.dfm}
{ TForm1 }
//找出表达式s中最后一个运算的运算符的位置
function TForm1.FindLastOpPos(s: string): Integer;
var
i: Integer;
Count: Integer;
begin
Result:=0;
Count:=0;
for i:=Length(s)do
wnto 1do
case s of
'(' : Dec(Count);
')' : Inc(Count);
'+', '-': if Count=0 then
begin
Result:=i;
Exit
end;
'*', '/': if (Count=0) and (Result=0) then
Result:=i
end
end;
procedure TForm1.DestroyTree(Root: TTree);
//回收内存
begin
if Root=nil then
Exit;
if Root^.LeftChild<>nil then
DestroyTree(Root^.LeftChild);
if Root^.RightChild<>nil then
DestroyTree(Root^.RightChild);
Dispose(Root)
end;
//根据表达式s构造树
function TForm1.MakeTree(s: string): TTree;
var
Len: Integer;
p: Integer;
begin
if s='' then
Result:=nil
else
begin
Len:=Length(s);
if (s[1]='(') and (s[Len]=')') then
Result:=MakeTree(Copy(s, 2, Len-2))
else
begin
New(Result);
p:=FindLastOpPos(s);
if p>0 then
begin
Result^.op:=s[p];
Result^.LeftChild:=MakeTree(Copy(s, 1, p-1));
Result^.RightChild:=MakeTree(Copy(s, p+1, Len-p))
end
else
begin
Result^.Op:=s;
Result^.LeftChild:=nil;
Result^.RightChild:=nil
end
end
end
end;
//根据树Root输出逆波兰式(后序)
function TForm1.FormatTree(Root: TTree): string;
begin
if Root=nil then
Result:=''
else
Result:=FormatTree(Root^.LeftChild)+' '+FormatTree(Root^.RightChild)+' '+Root^.op
end;
//根据树计算结果(后序)
function TForm1.CalculateTree(Root: TTree):do
uble;
var
a, b:do
uble;
begin
if (Root^.LeftChild=nil) and (Root^.RightChild=nil) then
Result:=StrToFloat(Root^.op)
else
begin
a:=CalculateTree(Root^.LeftChild);
b:=CalculateTree(Root^.RightChild);
case Root^.op[1] of
'+': Result:=a+b;
'-': Result:=a-b;
'*': Result:=a*b;
'/': Result:=a/b
end
end
end;
//画树(先序)
procedure TForm1.DrawTree(Root: TTree;
Top, Left, Right: Integer);
var
Mid: Integer;
begin
PaintBox.Canvas.TextOut(Left+(Right-Left-PaintBox.Canvas.TextWidth(Root^.op)) div 2,
Top, Root^.op);
if (Root^.LeftChild<>nil) and (Root^.RightChild<>nil) then
begin
Mid:=Left+(Right-Left) div 2;
PaintBox.Canvas.MoveTo(Mid, Top+PaintBox.Canvas.TextHeight(Root^.op)+2);
PaintBox.Canvas.LineTo(Mid, Top+PaintBox.Canvas.TextHeight(Root^.op)+10);
PaintBox.Canvas.LineTo(Left+(Mid-Left) div 2, Top+PaintBox.Canvas.TextHeight(Root^.op)+10);
PaintBox.Canvas.LineTo(Mid+(Right-Mid) div 2, Top+PaintBox.Canvas.TextHeight(Root^.op)+10);
PaintBox.Canvas.MoveTo(Left+(Mid-Left) div 2, Top+PaintBox.Canvas.TextHeight(Root^.op)+10);
PaintBox.Canvas.LineTo(Left+(Mid-Left) div 2, Top+PaintBox.Canvas.TextHeight(Root^.op)+18);
PaintBox.Canvas.MoveTo(Mid+(Right-Mid) div 2, Top+PaintBox.Canvas.TextHeight(Root^.op)+10);
PaintBox.Canvas.LineTo(Mid+(Right-Mid) div 2, Top+PaintBox.Canvas.TextHeight(Root^.op)+18);
DrawTree(Root^.LeftChild, Top+PaintBox.Canvas.TextHeight(Root^.op)+20, Left, Mid);
DrawTree(Root^.RightChild, Top+PaintBox.Canvas.TextHeight(Root^.op)+20, Mid, Right)
end
end;
procedure TForm1.FormatButtonClick(Sender: TObject);
begin
ValueEdit.Text:=FormatTree(Root)
end;
procedure TForm1.CalculateButtonClick(Sender: TObject);
begin
ValueEdit.Text:=FloatToStr(CalculateTree(Root))
end;
procedure TForm1.FormClose(Sender: TObject;
var Action: TCloseAction);
begin
DestroyTree(Root)
end;
procedure TForm1.MakeTreeButtonClick(Sender: TObject);
begin
DestroyTree(Root);
Root:=MakeTree(ExpressEdit.Text)
end;
procedure TForm1.DrawButtonClick(Sender: TObject);
begin
PaintBox.Canvas.FillRect(PaintBox.ClientRect);
DrawTree(Root, 10, 0, PaintBox.Width)
end;
end.
;inc(n2);mulsign[n2]:='*';muldev[n2]:=n;