我有一個檔案tree.txt，裡面的格式為

使用遞廻方法
謹供參考

[code delphi]
unit fMain;

interface

uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;

type
TForm1 = class(TForm)
Label1: TLabel;
Button1: TButton;
Label2: TLabel;
procedure Button1Click(Sender: TObject);
private
function MyCalc(S: string): Double;
function MyFunction(LtS, RtS: string): Double;
function MyPos(SubStr, S: string; var P: Integer): Boolean;

function FindSymbol(
var FoundPos: Integer;
S: string; StartPos: Integer;
LtSym, RtSym: string): Boolean;
end;

var
Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);
var
S: string;
V: Single;
begin
S := '((t1:0.3,t2:0.5):0.1,(t3:0.2,t4:0.6):0.2)';
V := MyCalc(S);
Label2.Caption := Format('%f',[V]);
end;

function TForm1.FindSymbol(var FoundPos: Integer; S: string;
StartPos: Integer; LtSym, RtSym: string): Boolean;
var
I, WordCount, LtLen, RtLen: Integer;
begin
LtLen := Length(LtSym);
RtLen := Length(RtSym);
WordCount := 1;
for I := StartPos LtLen to Length(S)-RtLen 1 do
begin
if StrLComp(PChar(@S[I]),PChar(LtSym),LtLen) = 0 then Inc(WordCount)
else if StrLComp(PChar(@S[I]),PChar(RtSym),RtLen) = 0 then Dec(WordCount);

if WordCount < 1 then
begin
FoundPos := I RtLen-1;
Break;
end;
end;

Result := WordCount = 0;

end;

function TForm1.MyPos(SubStr, S: string; var P: Integer): Boolean;
var
I, K, SubStrLen: Integer;
begin
P := 0;
if Length(S) > 0 then
begin
SubStrLen := Length(SubStr);
I := 1;
repeat
if S[I] = '(' then
begin
if not FindSymbol(K,S,I,'(',')')
then Break
else I := K;
end
else begin
if StrLComp(PChar(@S[I]),PChar(SubStr),SubStrLen) = 0 then
begin
P := I;
Break;
end;
end;
Inc(I);
until I > Length(S)-SubStrLen 1;
end;
Result := P > 0;
end;

function TForm1.MyFunction(LtS, RtS: string): Double;
begin
Result := MyCalc(LtS) MyCalc(RtS);
end;

function TForm1.MyCalc(S: string): Double;
var
P: Integer;
LtS,Rts: string;
begin
Result := 0;
if S = '' then EXIT;
if MyPos(',',S,P) or MyPos(':',S,P) then
begin
LtS := Copy(S,1,P-1);
RtS := Copy(S,P 1,Length(S)-P);
Result := MyFunction(LtS,RtS);
end
else if (S[1]='(') and (S[Length(S)]=')') then
begin
S := Copy(S,2,Length(S)-2);
Result := MyCalc(S);
end
else begin
Result := StrToFloatDef(S,0);
end;
end;


end.
[/code]


唉! 又忘了注意提問者所使用的工具...

編輯記錄

嘿嘿,我記得jow前輩也會BCB ^__^

我很好奇jow前輩有沒有參加ACM跟code jam..:P
===================引 用 taishyang 文 章===================
嘿嘿,我記得jow前輩也會BCB ^__^

------
不論是否我發的文，在能力範圍皆很樂意為大家回答問題。
為了補我的能力不足之處，以及讓答案可以被重複的使用，希望大家能儘量以公開的方式問問題。
在引述到我的文時自然會儘量替各位想辦法，謝謝大家！

這個題目可以使用矩陣樹來做

在記憶體有限 (無法遞迴)，但仍足夠(建立完整的 Tree)的話，你可以

資料結構使用

node
{
node *up_link;
node *tail_link;
int node_sum;
}

node[] *Level_Head;

node *Level_Prev;

建立出一個矩陣型態的樹

先用前序 parser
up_link 記錄樹狀組織的上行節點 (這裡我不紀錄 down_link, head_link，因為沒有用到)
Level_Head 存放每一層的第一個節點 (由左往右，反之亦然，取一方向，統一即可)
Level_Prev 記錄該層的前一個建立的節點

這樣可以建立出該樹

然後就簡單了，由最底層倒著算回來，跑回圈，使用 Level_Head，可取出每一層的最左方的節點
然後將自己的值計算出來後，加到 up_link 的 node_sum 上，然後取出 tail_link，使用之做同樣的計算，直到沒有 tail

等到回圈跑到 Level_Head[0] 時，所有節點都會被計算出來

這樣，若是一共有 n 節點，會使用記憶體 (一個節點 4 byte * 3), 12 * (n (long(n) 1) 1) 記憶體空間

不過要是記憶體真的很有限，那你就必須使用類似外部排序法的技巧

例如，先將資料來源格式化成為樹狀，並倒著存放到檔案中，倒數第一行，是 Level 0，倒數第二行，是樹的 Level 1
然後開檔，使用上述的回圈方式，每次載入一個小陣列來計算，帶計算到檔尾，也是可行的方式

上述方式，仍有很大改善空間，同時作法不限上述方式，提出來給你參考看看，相信你應該有辦法將演算方式轉化成實際的程式


PS. 如果 tree.txt 格式是你制訂的，建議依據你的需求，稍微設計一下，
設計一個不需要再度 parser，直接取出即可使用的格式，可以減輕你不少負擔與不必要的麻煩

===================引 用 lulala 文 章===================
我有一個檔案tree.txt，裡面的格式為

以下版本,新增一個 TraceList 來追蹤運算的過程
範例程式碼的動作是直接將數值運算出來,

謹供參考...^_^


[code delphi]
unit fMain;

interface

uses
Windows, Classes, Controls, Dialogs, SysUtils, StdCtrls, Forms;

type
TForm1 = class(TForm)
Label1: TLabel;
Button1: TButton;
Label2: TLabel;
procedure Button1Click(Sender: TObject);
private
TraceList: TStringList;
function MyCalc(S: string): Double;
function MyPos(SubStr, S: string; var P: Integer): Boolean;
function FindSymbol(var FoundPos: Integer;
S: string; StartPos: Integer; LtSym, RtSym: string): Boolean;
end;

var
Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);
var
S: string;
V: Single;
begin
TraceList := TStringList.Create;
try
S := '((t1:0.3,t2:0.5):0.1,(t3:0.2,t4:0.6):0.2)';
V := MyCalc(S);
Label2.Caption := Format('%f',[V]);
ShowMessage(TraceList.Text);
//TraceList.SaveToFile('C:\TRACELIST.TXT');
finally
FreeAndNil(TraceList);
end;
end;

function TForm1.FindSymbol(var FoundPos: Integer; S: string;
StartPos: Integer; LtSym, RtSym: string): Boolean;
var
I, WordCount, LtLen, RtLen: Integer;
begin
LtLen := Length(LtSym);
RtLen := Length(RtSym);
WordCount := 1;
for I := StartPos LtLen to Length(S)-RtLen 1 do
begin
if StrLComp(PChar(@S[I]),PChar(LtSym),LtLen) = 0 then Inc(WordCount)
else if StrLComp(PChar(@S[I]),PChar(RtSym),RtLen) = 0 then Dec(WordCount);

if WordCount < 1 then
begin
FoundPos := I RtLen-1;
Break;
end;
end;

Result := WordCount = 0;

end;

function TForm1.MyPos(SubStr, S: string; var P: Integer): Boolean;
var
I, K, SubStrLen: Integer;
begin
P := 0;
if Length(S) > 0 then
begin
SubStrLen := Length(SubStr);
I := 1;
repeat
if S[I] = '(' then
begin
if not FindSymbol(K,S,I,'(',')')
then Break
else I := K;
end
else begin
if StrLComp(PChar(@S[I]),PChar(SubStr),SubStrLen) = 0 then
begin
P := I;
Break;
end;
end;
Inc(I);
until I > Length(S)-SubStrLen 1;
end;
Result := P > 0;
end;

function TForm1.MyCalc(S: string): Double;
const
FS0='[A] MyCalc{ %s } = MyCalc{ %s } MyCalc{ %s }';
FS1='[B] MyCalc{ %s } = MyCalc{ %s }';
FS2='[C] MyCalc{ %s } = %f';
var
P: Integer;
LtS,Rts: string;
begin
Result := 0;
if S = '' then EXIT;
if MyPos(',',S,P) or MyPos(':',S,P) then
begin{A.分項計算}
LtS := Copy(S,1,P-1);
RtS := Copy(S,P 1,Length(S)-P);
TraceList.Add(Format(FS0,[S,Lts,RtS]));
Result := MyCalc(LtS) MyCalc(RtS);
end
else if (S[1]='(') and (S[Length(S)]=')') then
begin{B.去除最外層 '(', ')' 符號}
LtS := Copy(S,2,Length(S)-2);
TraceList.Add(Format(FS1,[S,LtS]));
Result := MyCalc(LtS);
end
else begin
{C.取得數值, 其中 t1,t2,t3,t4 需另外處理, 目前讓它等於 0}
TraceList.Add(Format(FS2,[S,Result]));
Result := StrToFloatDef(S,0);
end;
end;

end.
[/code]

編輯記錄

以下是 C++ 的版本

[code cpp]
//---------------------------------------------------------------------------
#ifndef fMainH
#define fMainH
//---------------------------------------------------------------------------
#include
#include
#include
#include <Forms.hpp><br />//---------------------------------------------------------------------------
class TForm1 : public TForm
{
__published: // IDE-managed Components
TButton *Button1;
TLabel *Label1;
TLabel *Label2;
void __fastcall Button1Click(TObject *Sender);
private:
TStringList *TraceList;
double __fastcall MyCalc(AnsiString S);
bool __fastcall MyPos(AnsiString SubStr, AnsiString S, int& P);
bool __fastcall FindSymbol(int& FoundPos, AnsiString S,
int StartPos, AnsiString LtSym, AnsiString RtSym);
public:
__fastcall TForm1(TComponent* Owner);
};
//---------------------------------------------------------------------------
extern PACKAGE TForm1 *Form1;
//---------------------------------------------------------------------------
#endif
[/code]

[code cpp]
//---------------------------------------------------------------------------

#include
#pragma hdrstop

#include "fMain.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner): TForm(Owner)
{
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
TraceList = new TStringList();
try{
AnsiString S = "((t1:0.3,t2:0.5):0.1,(t3:0.2,t4:0.6):0.2)";
double V = MyCalc(S);
Label2->Caption = S.sprintf("%f",V);
ShowMessage(TraceList->Text);
//TraceList->SaveToFile("C:\TRACELIST.TXT");
}
__finally{
delete TraceList;
}
}
//---------------------------------------------------------------------------
bool __fastcall TForm1::MyPos(AnsiString SubStr, AnsiString S, int& P)
{
P = 0;
int K;
if(S.Length()>0){
int len = SubStr.Length();
int I = 1;
while(I<=S.Length()-len 1){
if(S[I]=='('){
if(!FindSymbol(K,S,I,"(",")")) break;
I = K;
}
else{
if(StrLComp(&S[I],&SubStr[1],len)==0){
P = I;
break;
}
}
I ;
}
}
return (P>0);
}
//---------------------------------------------------------------------------
bool __fastcall TForm1::FindSymbol(int& FoundPos, AnsiString S,
int StartPos, AnsiString LtSym, AnsiString RtSym)
{
int WordCount = 1;
for(int I=StartPos LtSym.Length();S.Length()-RtSym.Length() 1;I ){
if(StrLComp(&S[I],&LtSym[1],LtSym.Length())==0)WordCount ;
else if(StrLComp(&S[I],&RtSym[1],RtSym.Length())==0)WordCount--;
if(WordCount<1){
FoundPos = I RtSym.Length()-1;
break;
}
}
return (WordCount==0);
}
//---------------------------------------------------------------------------
double __fastcall TForm1::MyCalc(AnsiString S)
{
char *FS0="[A] MyCalc{ %s } = MyCalc{ %s } MyCalc{ %s }";
char *FS1="[B] MyCalc{ %s } = MyCalc{ %s }";
char *FS2="[C] MyCalc{ %s } = %f";

if(S=="") return 0;

int P;
AnsiString T,LtS,RtS;
if(MyPos(",",S,P)||MyPos(":",S,P)){
/* A.分項計算 */
LtS = S.SubString(1,P-1);
RtS = S.SubString(P 1,S.Length()-P);
T.sprintf(FS0,S,LtS,RtS);
TraceList->Add(T);
return (MyCalc(LtS) MyCalc(RtS));
}
else if(S[1]=='(' && S[S.Length()]==')'){
/* B.去除最外層 '(', ')' 符號 */
LtS = S.SubString(2,S.Length()-2);
T.sprintf(FS1,S,LtS);
TraceList->Add(T);
return MyCalc(LtS);
}
else{
/* 取得數值, t1,t2,t3,t4 需另外處理, 目前等於 0 */
double ret= StrToFloatDef(S,0);
T.sprintf(FS2,S,ret);
TraceList->Add(T);
return ret;
}
}
//---------------------------------------------------------------------------

[/code]

TRACELIST.TXT 的內容

[B] MyCalc{ ((t1:0.3,t2:0.5):0.1,(t3:0.2,t4:0.6):0.2) } = MyCalc{ (t1:0.3,t2:0.5):0.1,(t3:0.2,t4:0.6):0.2 }
[A] MyCalc{ (t1:0.3,t2:0.5):0.1,(t3:0.2,t4:0.6):0.2 } = MyCalc{ (t1:0.3,t2:0.5):0.1 } MyCalc{ (t3:0.2,t4:0.6):0.2 }
[A] MyCalc{ (t1:0.3,t2:0.5):0.1 } = MyCalc{ (t1:0.3,t2:0.5) } MyCalc{ 0.1 }
[B] MyCalc{ (t1:0.3,t2:0.5) } = MyCalc{ t1:0.3,t2:0.5 }
[A] MyCalc{ t1:0.3,t2:0.5 } = MyCalc{ t1:0.3 } MyCalc{ t2:0.5 }
[A] MyCalc{ t1:0.3 } = MyCalc{ t1 } MyCalc{ 0.3 }
[C] MyCalc{ t1 } = 0.000000
[C] MyCalc{ 0.3 } = 0.300000
[A] MyCalc{ t2:0.5 } = MyCalc{ t2 } MyCalc{ 0.5 }
[C] MyCalc{ t2 } = 0.000000
[C] MyCalc{ 0.5 } = 0.500000
[C] MyCalc{ 0.1 } = 0.100000
[A] MyCalc{ (t3:0.2,t4:0.6):0.2 } = MyCalc{ (t3:0.2,t4:0.6) } MyCalc{ 0.2 }
[B] MyCalc{ (t3:0.2,t4:0.6) } = MyCalc{ t3:0.2,t4:0.6 }
[A] MyCalc{ t3:0.2,t4:0.6 } = MyCalc{ t3:0.2 } MyCalc{ t4:0.6 }
[A] MyCalc{ t3:0.2 } = MyCalc{ t3 } MyCalc{ 0.2 }
[C] MyCalc{ t3 } = 0.000000
[C] MyCalc{ 0.2 } = 0.200000
[A] MyCalc{ t4:0.6 } = MyCalc{ t4 } MyCalc{ 0.6 }
[C] MyCalc{ t4 } = 0.000000
[C] MyCalc{ 0.6 } = 0.600000
[C] MyCalc{ 0.2 } = 0.200000

編輯記錄

 首先先謝謝 jow 及 syntax 兩位前輩提供的意見！

以下Parse的方式, 提供你參考
[code cpp]
//---------------------------------------------------------------------------
#ifndef fMainH
#define fMainH
//---------------------------------------------------------------------------
#include
#include
#include
#include <Forms.hpp><br />#include
//---------------------------------------------------------------------------
bool __fastcall MyPos(AnsiString SubStr, AnsiString S, int& P);
bool __fastcall FindSymbol(int& FoundPos, AnsiString S, int StartPos,
AnsiString LtSym, AnsiString RtSym);
//---------------------------------------------------------------------------
class TreeNode{
public:
TreeNode *Parent;
AnsiString S;
TreeNode *left;
TreeNode *right;
public:
TreeNode(TreeNode *Parent, AnsiString S);
~TreeNode();
};
//---------------------------------------------------------------------------
class Tree{
private:
void DoParse(TreeNode *Parent, AnsiString S);
void Release(TreeNode *node);
TreeNode* Add(TreeNode *Parent, TreeNode *p, AnsiString S);
public:
int NodeCount;
TreeNode *root;
Tree(AnsiString S);
~Tree();
void Parse(AnsiString S);
void Print(TreeNode *p, TStringList *L);
};
//---------------------------------------------------------------------------
class TForm1 : public TForm
{
__published:
TListBox *ListBox1;
TButton *Button1;
void __fastcall Button1Click(TObject *Sender);
public:
__fastcall TForm1(TComponent* Owner);
};
//---------------------------------------------------------------------------
extern PACKAGE TForm1 *Form1;
//---------------------------------------------------------------------------
#endif
[/code]


[code cpp]
//---------------------------------------------------------------------------
#include
#pragma hdrstop
#include "fMain.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
//---------------------------------------------------------------------------
bool __fastcall MyPos(AnsiString SubStr, AnsiString S, int& P)
{
P = 0;
int K;
if(S.Length()>0){
int len = SubStr.Length();
int I = 1;
while(I <= S.Length()-len 1){
if(S[I]=='('){
if(!FindSymbol(K,S,I,"(",")")) break;
I = K;
}
else{
if(StrLComp(&S[I],&SubStr[1],len)==0){
P = I;
break;
}
}
I ;
}
}
return (P>0);
}
//---------------------------------------------------------------------------
bool __fastcall FindSymbol(int& FoundPos, AnsiString S,
int StartPos, AnsiString LtSym, AnsiString RtSym)
{
int WordCount = 1;
for(int I=StartPos LtSym.Length();S.Length()-RtSym.Length() 1;I ){
if(StrLComp(&S[I],&LtSym[1],LtSym.Length())==0)WordCount ;
else if(StrLComp(&S[I],&RtSym[1],RtSym.Length())==0)WordCount--;
if(WordCount<1){
FoundPos = I RtSym.Length()-1;
break;
}
}
return (WordCount==0);
}
//---------------------------------------------------------------------------
//THE TREENODE
TreeNode::TreeNode(TreeNode *Parent, AnsiString S)
{
this->Parent=Parent;
this->S = S;
left = right = NULL;
}
//---------------------------------------------------------------------------
TreeNode::~TreeNode()
{
}
//---------------------------------------------------------------------------
//THE TREE
Tree::Tree(AnsiString S)
{
root = NULL;
NodeCount = 0;
Parse(S);
}
//---------------------------------------------------------------------------
Tree::~Tree()
{
Release(root);
}
//---------------------------------------------------------------------------
void Tree::Release(TreeNode *node)
{
if(node!=NULL){
Release(node->left);
Release(node->right);
delete node;
node = NULL;
}
}
//---------------------------------------------------------------------------
void Tree::Parse(AnsiString S)
{
Release(root);
root = Add(NULL,root,S);
DoParse(root,S.SubString(2,S.Length()-2));
}
//---------------------------------------------------------------------------
TreeNode* Tree::Add(TreeNode *Parent, TreeNode *p, AnsiString S)
{
if(p==NULL){
NodeCount ;
p = new TreeNode(Parent,S);
}
else if(p->left==NULL) Add(p,p->left,S);
else if(p->right==NULL)Add(p,p->right,S);
return p;
}
//---------------------------------------------------------------------------
void Tree::DoParse(TreeNode *Parent, AnsiString S)
{
int P;
if(S[1]=='('&&S[S.Length()]==')'){

DoParse(Parent,S.SubString(2,S.Length()-2));
}
else if(MyPos(",",S,P)){

AnsiString LtS = S.SubString(1,P-1);
Parent->left = Add(Parent,Parent->left,LtS);
DoParse(Parent->left,LtS);

AnsiString RtS = S.SubString(P 1,S.Length()-P);
Parent->right = Add(Parent,Parent->right,RtS);
DoParse(Parent->right,RtS);

}
else if(MyPos(":",S,P)){
AnsiString LtS = S.SubString(1,P-1);
DoParse(Parent,LtS);
}
}
//---------------------------------------------------------------------------
void Tree::Print(TreeNode *p, TStringList *L)
{
if(p!=NULL&&L!=NULL){
Print(p->left,L);
L->Add(p->S);
Print(p->right,L);
}
}
//---------------------------------------------------------------------------
//測試碼
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner): TForm(Owner)
{
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
AnsiString S = "((t1:0.3,t2:0.5):0.1,(t3:0.2,t4:0.6):0.2)";

TStringList *L = new TStringList();
try{
Tree* tree = new Tree(S);
try{
tree->Print(tree->root,L);
L->SaveToFile("C:\TRACELIST.TXT");
Caption = tree->NodeCount;
ListBox1->Items->Text = L->Text;
}
__finally{
delete tree;
}
}
__finally{
delete L;
}
}
//---------------------------------------------------------------------------
[/code]


以下是 TRACELIST.TXT 的內容
t1:0.3
(t1:0.3,t2:0.5):0.1
t2:0.5
((t1:0.3,t2:0.5):0.1,(t3:0.2,t4:0.6):0.2) <--- root
t3:0.2
(t3:0.2,t4:0.6):0.2
t4:0.6

除 root 外其他的 TreeNode 的 內含字串格式為

編輯記錄

提問者您好:


以上回應是否已得到滿意的答覆？


若已得到滿意的答覆，請在一週內結案，否則請在一週內回覆還有什麼未盡事宜，不然，
將由版主(尚無版主之區域將由副站長或站長)採自由心證,選擇較合適之解答予以結案處理，
被選上之答題者同樣會有加分獎勵，同時發問者將受到扣 1 分的處分。不便之處，請見諒。


有問有答有結案，才能有良性的互動，良好的討論環境需要大家共同維護，感謝您的配合。

------
我是機器人,我不接受簡訊.