Có ai biết dùng cây nhị phân hay stack để biểu diễn biểu thức toán học không ?

[unfriendlyboy]

Có bro nào biết không vậy ? Chỉ boy nhé.

Thanks in advanced !

[CrazyBabe]

Hic
Cây nhị phân nhé: node đấy chứa dấu hoặc giá trị. Nếu chứa dấu thì có child node left và right là 2 bt 2 phía. Thế là xong, nhỉ ?

[unfriendlyboy]

Biết là thế, nhưng mà lập trình như thế nào. Ví dụ, cho 1 biểu thức */+-, làm sao biểu diễn biểu thức ấy thành cây nhị phân ? :(

[hiepsi4rum]

Theo tớ hình như là cây nhị phân là để biểu diễn 1 cấu trúc dữ liệu mà!!!
Còn việc thể hiện biểu thức thì hình như là tùy vào kỹ thậut lập trình thui!!

[jiSh@n]

Ví dụ đơn giản:
a*b
. *
. / \
. a b

[bete]

Cho bie^?u thu*'c: 1 + 2 * 5 / (7 + 3 ) - 4
==> tuo*ng đuo*ng vo*'i ca^y nhi. pha^n:

' -- + --
' | |
' 1 -- - --
' | |
' -- * -- 4
' | |
' 2 -- / --
' | |
' 5 -- + --
' | |
' 7 3

Lu*u y': bie^?u thu*'c ngye^n thu?y tuo*ng đuo*ng vo*'i: 1 + (2 * 5 / (7 + 3)) - 4

Đe^? ta.o ca^y nhi. pha^n, co' the^? dun`g logic sau:

bie^?u thu*'c: expression := factor
or factor + expression
or factor - expression

ti'ch / thuo*ng so^' : factor := base
or base * factor
or base / factor
co* so*?: base := number
or ( expression )

pseudocode sau:

1) Đo.c bie^?u thu*'c (string) va`o 1 bo^. đe^.m (bufer)
2) ha`m TaoCayChoBieuThuc /* tra? ve^` con tro? to*'i 1 node */ :
go.i ha`m TaoCayChoTichThuong: ga'n gia' tri. tra? ve^` va`o bie^'n root (cu.c bo^.)
đo.c ky_tu_ke (ca^`n skip whitespaces cho thi'ch ho*.p) tu*` bo^. đe^.m
loop (ky_tu_ke la` '+' hay '-')
ga'n gia' tri. cu?a root va`o bie^'n p (cu.c bo^.)
Xin ca^'p pha't bie^'n con tro? root
ga'n p va`o root->left
ga'n TaoCayChoBieuThuc() va`o root->right
end loop
tra lui ky_tu_ke va`o bo^. đe^.m ne^'u ky_tu_ke kho^ng la` ky' tu*. tro^'ng
tra? ve^` gia' tri. cu?a root

3) ha`m TaoCayChoTichThuong /* tra? ve^` con tro? to*'i 1 node */ :
đo.c ky_tu_ke (ca^`n skip whitespaces cho thi'ch ho*.p) tu*` bo^. đe^.m
if (ky_tu_ke la` '(')
ga'n gia' tri. cu?a root va`o bie^'n p (cu.c bo^.)
Xin ca^'p pha't bie^'n con tro? root
ga'n TaoCayChoBieuThuc() va`o root
đo.c ky_tu_ke (ca^`n skip whitespaces cho thi'ch ho*.p) tu*` bo^. đe^.m
if (ky_tu_ke 0 la` ')')
ba'o error "Mising ')'"
end if
else
ga'n TaoCayChoMotSo va`o root
end if
tra lui ky_tu_ke va`o bo^. đe^.m ne^'u ky_tu_ke kho^ng la` ky' tu*. tro^'ng
tra? ve^` gia' tri. cu?a root

4) ha`m TaoCayChoMotSo /* tra? ve^` con tro? to*'i 1 node */ :
đo.c va`o 1 da~y ca'c chu*~ so^' (digits)
Xin ca^'p pha't bie^'n con tro? root
ga'n da~y ca'c chu*~ so^' vu*~a đo.c va`o root->data
tra? ve^` gia' tri. cu?a root

Lu*u y' 1: Vie^'t nhu* tre^n thi` code ho*i da`i (ca'c ha`m TaoCayChoBieuThuc & TaoCayChoTichThuong tuo*ng tu*. nhau) nhu* logic
de^~ hie^?u -> de^~ debug

Lu*u y' 2: Ne^'u muo^'n mi`nh co' the^? mo*? ro^.ng ra cho phe'p lu~y
thu*`a va` khai ca(n (ne^n du`ng so^' thu*.c). Ho*n nu*~a, co' the^?
in ra gi'a tri. cu?a bie^?u thu*'c nguye^n thu?y --> calcultor. Gia?i thua^.t na`y đuo*.c đuo*.c da.y trong lo*'p Tri`nh Bie^n Di.ch (Compiler)

(ha^`u he^'t trong mo.i truo*`ng ho*.p: ho.c la^.p tri`nh ba(`ng ca'ch tu*. mi`nh vie^'t code se~ thu nhie^`u tie^'n bo^. ho*n la` đo.c code do
nguo*`i kha'c vie^'t) => tui 0 đa(ng code o*? đa^y (ma` tui cu~ng 0 co' sa(~n -> pha?i ngo^`i vie^'t -> ma^'t co^ng qu'a :)). Ne^'u mi`nh bie^'t ca'i
y' chi'nh (thua^.t gia?i) ro^`i thi` co' the^? ca`i đa(.t ba(`ng ha^`u nhu*
ba^'t cu*' ngo^n ngu*~ na`o (C, C++, Java, VB,...) => bo^` chi.u kho' đo.c
ma~ gia? (pseudocode) nhe' :) Ne^'u va^~n co`n the'c me'c thi` tui se~
no'i ky~ ho*n. Tie^'c la` khi ba`i đa(ng le^n thi` nhu*~ng khoa?ng tro^'ng
o*? đa^`u ca'c do`ng bi. ca('t bo? => khi vie^'t code ne^n indent (thu.t
va`o tu*` đa^`u do`ng) ==> code se~ de^~ đo.c ho*n ra^'t nhie^`u

[bete]

Co' lo^.n 1 ti' xi'u -> xin su*?a la.i:

3) ha`m TaoCayChoTichThuong /* tra? ve^` con tro? to*'i 1 node */ :
go.i ha`m TaoCayChoCoSo: ga'n gia' tri. tra? ve^` va`o bie^'n root (cu.c bo^.)
đo.c ky_tu_ke (ca^`n skip whitespaces cho thi'ch ho*.p) tu*` bo^. đe^.m
loop (ky_tu_ke la` '*' hay '/')
ga'n gia' tri. cu?a root va`o bie^'n p (cu.c bo^.)
Xin ca^'p pha't bie^'n con tro? root
ga'n p va`o root->left
ga'n TaoCayChoTichThuong() va`o root->right
end loop
tra lui ky_tu_ke va`o bo^. đe^.m ne^'u ky_tu_ke kho^ng la` ky' tu*. tro^'ng
tra? ve^` gia' tri. cu?a root

4) ha`m TaoCayChoCoSo /* tra? ve^` con tro? to*'i 1 node */ :
đo.c ky_tu_ke (ca^`n skip whitespaces cho thi'ch ho*.p) tu*` bo^. đe^.m
if (ky_tu_ke la` '(')
ga'n gia' tri. cu?a root va`o bie^'n p (cu.c bo^.)
Xin ca^'p pha't bie^'n con tro? root
ga'n TaoCayChoBieuThuc() va`o root
đo.c ky_tu_ke (ca^`n skip whitespaces cho thi'ch ho*.p) tu*` bo^. đe^.m
if (ky_tu_ke 0 la` ')')
ba'o error "Mising ')'"
end if
else
ga'n TaoCayChoMotSo va`o root
end if
tra lui ky_tu_ke va`o bo^. đe^.m ne^'u ky_tu_ke kho^ng la` ky' tu*. tro^'ng
tra? ve^` gia' tri. cu?a root

5) ha`m TaoCayChoMotSo /* tra? ve^` con tro? to*'i 1 node */ :
............

[bete]

Xin no'i ro~ ho*n 1 ti' ve^` logic:

bie^?u thu*'c: expression := factor
or factor + expression
or factor - expression

ti'ch / thuo*ng so^' : factor := base
or base * factor
or base / factor

co* so*?: base := number
or ( expression )

==> ca'i y' la`:
1) bie^?u thu*'c la` to^?ng hay hie^.u cu?a nhu*~ng ti'ch & thuo*ng
2) Ti'ch hay thuo*ng la` ti'ch / thuo*ng cu?a nhu*~ng tha`nh pha^`n co* so*? (co* ba?n)
3) Tha`n pha^`n co* so*? la` 1 so^' (nguye^n hay thu*.c) hay la` 1 bie^?u thu*'c bi. ke.p giu*~a '(' & ')'

Nhu* va^.y: 1 + 2 * 5 / (7 + 3) - 4

1 + 2 * 5 / (7 + 3) - 4 : 1 bie^?u thu*'c

1: la` 1 ti'ch thuo*ng (đi sa^u ho*n nu*~a thi` 1 la` 1 tha`nh pha^`n co* so*? ro^`i la` 1 so^')

2 * 5 / (7 + 3): la` 1 ti'ch thuo*ng
2 la` 1 tha`nh pha^`n co* so*? (đi sa^u nu*~a thi` 2 la` 1 so^')
5 la` 1 tha`nh pha^`n co* so*? (đi sa^u nu*~a thi` 5 la` 1 so^')
(7 / 3) la` 1 tha`nh pha^`n co* so*? (đi sa^u nu*~a thi` (7 / 3) la` 1 bie^?u thu*'c ke.p giu*~a '(' & ')')
7 / 3: la` 1 bie^?u thu*'c (to^?ng cu?a 7 & 3)
7: la` 1 ti'ch thuo*ng (đi sa^u ho*n nu*~a thi` 7 la` 1 tha`nh pha^`n co* so*? ro^`i la` 1 so^')
3: la` 1 ti'ch thuo*ng (đi sa^u ho*n nu*~a thi` 3 la` 1 tha`nh pha^`n co* so*? ro^`i la` 1 so^')

4: la` 1 ti'ch thuo*ng (đi sa^u ho*n nu*~a thi` 4 la` 1 tha`nh pha^`n co* so*? ro^`i la` 1 so^')

Mi`nh co' the^? mo*? ro^.ng cho lu~y thu*`a & ca(n so^':

bie^?u thu*'c:
expression := factor
or factor + expression
or factor - expression

ti'ch / thuo*ng so^' :
factor := power
or power * factor
or power / factor

lu~y thu*~a / ca(n so^':
power := base
or base ^ power
or base \ root // gia? su*? mi`nh quy uo*'c 9 \ 2 = ca(n ba^.c 2 cu?a 9

co* so*?:
base := number
or ( expression )

Mi`nh co`n co' the^? mo*? ro^.ng ra cho lo^-ga-rit:

co* so*?:
base := number
or logarithm
or ( expression)

logarithm := log(co* so^', so^')
or log(so^') // log co* so^' 10
or lg(so^') // log co* so^' 2

==> co' 1 calculator kha' ma.nh (ne^'u muo^'n co' the^? mo*? ro^.ng ra
cho ca'c ha`m luo*.ng gia'c, luo*.ng gia'c nguo*.c, .....)

[bete]

Tui bi. so't 1 ti':

Trong ha`m TaoCayChoBieuThuc & TaoCayChoTichThuong

the^m va`o sau:

Xin ca^'p pha't bie^'n con tro? root

==>

Xin ca^'p pha't bie^'n con tro? root
ga'n ky_tu_ke va`o root->data

[jiSh@n]

Hic seo ko gõ TV có dấu? gõ VIQR khó đọc we'.

[unfriendlyboy]

Dù gì cũng cám ơn bạn đã giúp đỡ.

Thanks so much !

[bete]

> Hic seo ko gõ TV có dấu? gõ VIQR khó đọc we'.

==> xin lo^~i ma^'y bo^` nghen. Tui quen bo? da^'u kie^?u con nha` nghe`o (0 ca`i đa(.t the^m tool gi`he^'t -- la`m bie^'ng qu'a ma` :))

[jiSh@n]

DĐ có tích hợp sẵn bộ gõ TV mờ.

[bete]

> DĐ có tích hợp sẵn bộ gõ TV mờ.

==> Va^.y bo^` co' the^? chi? tui xa`i no' 0 (xin ca'm o*n truo*'c) !?

[unfriendlyboy]

À, bete đã lỡ giúp thì giúp luôn đi, boy hổng biết cài đặt bằng Pascal seo hết ấy :(. Bạn có thể cho mình xin source hông ?

Còn về vụ tiếng việt, mình chuyển thành Unicode nè:



Cho biểu thức: 1 + 2 * 5 / (7 + 3 ) - 4
==> tuơng ðuơng với cây nhị phân:

' -- + --
' | |
' 1 -- - --
' | |
' -- * -- 4
' | |
' 2 -- / --
' | |
' 5 -- + --
' | |
' 7 3

Lưu ý: biểu thức ngyên thủy tuơng ðuơng với: 1 + (2 * 5 / (7 + 3)) - 4

Ðể tạo cây nhị phân, có thể dun`g logic sau:

biểu thức: expression := factor
or factor + expression
or factor - expression

tích / thuơng số : factor := base
or base * factor
or base / factor
cơ sở: base := number
or ( expression )

pseudocode sau:

1) Ðọc biểu thức (string) vào 1 bộ ðệm (bufer)
2) hàm TaoCayChoBieuThuc /* trả về con trỏ tới 1 node */ :
gọi hàm TaoCayChoTichThuong: gán giá trị trả về vào biến root (cục bộ)
ðọc ky_tu_ke (cần skip whitespaces cho thích hợp) từ bộ ðệm
loop (ky_tu_ke là '+' hay '-')
gán giá trị của root vào biến p (cục bộ)
Xin cấp phát biến con trỏ root
gán p vào root->left
gán TaoCayChoBieuThuc() vào root->right
end loop
tra lui ky_tu_ke vào bộ ðệm nếu ky_tu_ke không là ký tự trống
trả về giá trị của root

3) hàm TaoCayChoTichThuong /* trả về con trỏ tới 1 node */ :
ðọc ky_tu_ke (cần skip whitespaces cho thích hợp) từ bộ ðệm
if (ky_tu_ke là '(')
gán giá trị của root vào biến p (cục bộ)
Xin cấp phát biến con trỏ root
gán TaoCayChoBieuThuc() vào root
ðọc ky_tu_ke (cần skip whitespaces cho thích hợp) từ bộ ðệm
if (ky_tu_ke 0 là ')')
báo error "Mising ')'"
end if
else
gán TaoCayChoMotSo vào root
end if
tra lui ky_tu_ke vào bộ ðệm nếu ky_tu_ke không là ký tự trống
trả về giá trị của root

4) hàm TaoCayChoMotSo /* trả về con trỏ tới 1 node */ :
ðọc vào 1 dãy các chữ số (digits)
Xin cấp phát biến con trỏ root
gán dãy các chữ số vữa ðọc vào root->data
trả về giá trị của root

Lưu ý 1: Viết như trên thì code hơi dài (các hàm TaoCayChoBieuThuc & TaoCayChoTichThuong tuơng tự nhau) như logic
dễ hiểu -> dễ debug

Lưu ý 2: Nếu muốn mình có thể mở rộng ra cho phép lũy
thừa và khai căn (nên dùng số thực). Hơn nữa, có thể
in ra gía trị của biểu thức nguyên thủy --> calcultor. Giải thuật này ðuợc ðuợc dạy trong lớp Trình Biên Dịch (Compiler)

(hầu hết trong mọi truờng hợp: học lập trình bằng cách tự mình viết code sẽ thu nhiều tiến bộ hơn là ðọc code do
nguời khác viết) => tui 0 ðăng code ở ðây (mà tui cũng 0 có sẵn -> phải ngồi viết -> mất công qúa ). Nếu mình biết cái
ý chính (thuật giải) rồi thì có thể cài ðặt bằng hầu như
bất cứ ngôn ngữ nào (C, C++, Java, VB,...) => bồ chịu khó ðọc
mã giả (pseudocode) nhé Nếu vẫn còn théc méc thì tui sẽ
nói kỹ hơn. Tiếc là khi bài ðăng lên thì những khoảng trống
ở ðầu các dòng bị cắt bỏ => khi viết code nên indent (thụt
vào từ ðầu dòng) ==> code sẽ dễ ðọc hơn rất nhiều

[unfriendlyboy]

Có lộn 1 tí xíu -> xin sửa lại:

3) hàm TaoCayChoTichThuong /* trả về con trỏ tới 1 node */ :
gọi hàm TaoCayChoCoSo: gán giá trị trả về vào biến root (cục bộ)
ðọc ky_tu_ke (cần skip whitespaces cho thích hợp) từ bộ ðệm
loop (ky_tu_ke là '*' hay '/')
gán giá trị của root vào biến p (cục bộ)
Xin cấp phát biến con trỏ root
gán p vào root->left
gán TaoCayChoTichThuong() vào root->right
end loop
tra lui ky_tu_ke vào bộ ðệm nếu ky_tu_ke không là ký tự trống
trả về giá trị của root

4) hàm TaoCayChoCoSo /* trả về con trỏ tới 1 node */ :
ðọc ky_tu_ke (cần skip whitespaces cho thích hợp) từ bộ ðệm
if (ky_tu_ke là '(')
gán giá trị của root vào biến p (cục bộ)
Xin cấp phát biến con trỏ root
gán TaoCayChoBieuThuc() vào root
ðọc ky_tu_ke (cần skip whitespaces cho thích hợp) từ bộ ðệm
if (ky_tu_ke 0 là ')')
báo error "Mising ')'"
end if
else
gán TaoCayChoMotSo vào root
end if
tra lui ky_tu_ke vào bộ ðệm nếu ky_tu_ke không là ký tự trống
trả về giá trị của root

5) hàm TaoCayChoMotSo /* trả về con trỏ tới 1 node */ :
............

[unfriendlyboy]

Xin nói rõ hơn 1 tí về logic:

biểu thức: expression := factor
or factor + expression
or factor - expression

tích / thuơng số : factor := base
or base * factor
or base / factor

cơ sở: base := number
or ( expression )

==> cái ý là:
1) biểu thức là tổng hay hiệu của những tích & thuơng
2) Tích hay thuơng là tích / thuơng của những thành phần cơ sở (cơ bản)
3) Thàn phần cơ sở là 1 số (nguyên hay thực) hay là 1 biểu thức bị kẹp giữa '(' & ')'

Như vậy: 1 + 2 * 5 / (7 + 3) - 4

1 + 2 * 5 / (7 + 3) - 4 : 1 biểu thức

1: là 1 tích thuơng (ði sâu hơn nữa thì 1 là 1 thành phần cơ sở rồi là 1 số)

2 * 5 / (7 + 3): là 1 tích thuơng
2 là 1 thành phần cơ sở (ði sâu nữa thì 2 là 1 số)
5 là 1 thành phần cơ sở (ði sâu nữa thì 5 là 1 số)
(7 / 3) là 1 thành phần cơ sở (ði sâu nữa thì (7 / 3) là 1 biểu thức kẹp giữa '(' & ')')
7 / 3: là 1 biểu thức (tổng của 7 & 3)
7: là 1 tích thuơng (ði sâu hơn nữa thì 7 là 1 thành phần cơ sở rồi là 1 số)
3: là 1 tích thuơng (ði sâu hơn nữa thì 3 là 1 thành phần cơ sở rồi là 1 số)

4: là 1 tích thuơng (ði sâu hơn nữa thì 4 là 1 thành phần cơ sở rồi là 1 số)

Mình có thể mở rộng cho lũy thừa & căn số:

biểu thức:
expression := factor
or factor + expression
or factor - expression

tích / thuơng số :
factor := power
or power * factor
or power / factor

lũy thữa / căn số:
power := base
or base ^ power
or base root // giả sử mình quy uớc 9 2 = căn bậc 2 của 9

cơ sở:
base := number
or ( expression )

Mình còn có thể mở rộng ra cho lô-ga-rit:

cơ sở:
base := number
or logarithm
or ( expression)

logarithm := log(cơ số, số)
or log(số) // log cơ số 10
or lg(số) // log cơ số 2

==> có 1 calculator khá mạnh (nếu muốn có thể mở rộng ra
cho các hàm luợng giác, luợng giác nguợc, .....)

[bete]

Bo^` unfriendlyboy a`,

Tui ho^?ng co' tri`nh bie^n di.ch Pascal, & la^u nga`y 0 xa`i tui cu~ng que^n cu'
pha'p Pascal ro^`i (tui co' thu*? character set encoding trong IE nhu*ng ma` cu~ng
0 đo.c ra ca'i Unicode cu?a bo^` -- toa`n la` o^ vuo^ng 0 ha`)

Tui vie^'t ky~ ca'i ma~ gi?a the^m 1 ti'

1) ta.o 1 ca^'u tru'c (record - structure)
record Node
dulieu : string cu?a 20 ky' tu*.
contrai : con tro? to*'i kie^?u record Node
conphai: con tro? to*'i kie^?u record Node
end record

2) ca'c ha`m, thuo*`ng tri`nh con:
a)
procedure InCay
tham so^' p la` con tro? to*'i kie^?u record Node
tham so^' i: so^' nguye^n

khai ba'o bie^'n cu.c bo^. j: so^' nguye^n

loop j: 1 -> 2*i
in 1 khoa?ng tro^'ng ' '
end loop

in chuo^~i "->"
in ra p^dulieu (tui nho*' mang ma'ng la` cu' pha'p na`y !?)

if contrai 0 la` NIL then
InCay(p^conphai, 0)
end

if contrai 0 la` NIL then
InCay(p^contrai, i+1)
end

end procedure InCay

b)
function DocMotSo
tra? ve^` 1 string (xa^u ky' tu*.)

tham so^' s: string
tham so^' i: so^' nguye^n (truye^`n ba(`ng THAM CHIE^'U, 0 truye^`n ba(`ng GIA' TRI.)

khai ba'o bie^'n cu.c bo^. motso: string[[20];
khai ba'o bie^'n cu.c bo^. ky_tu_ke: character
khai ba'o bie^'n cu.c bo^. j: so^' nguye^n

kho*?i ta.o j ba(`ng 1

ky_tu_ke := DocKyTu(s, i);

loop (ky_tu_ke la` 1 chu*~ so^' '0' -> '9')
ga'n ky_tu_ke vo^ chi? so^' thu*' j cu?a motso
ta(ng j le^n 1
ky_tu_ke := DocKyTu(s, i);
end loop

if ky_tu_ke kho^ng la` '' then
gia?m i đi 1 (tra? lui ky_tu_ke va`o bo^. đe^.m)
end if

tra? ve^` gia' tri. cu?a root

end function DocMotSo

c) function TaoCayChoMotSo
tra? ve^` 1 con tro? to*'i kie^?u record Node
tham so^' s: string
tham so^' i: so^' nguye^n (truye^`n ba(`ng THAM CHIE^'U, 0 truye^`n ba(`ng GIA' TRI.)

khai ba'o bie^'n cu.c bo^. root: con tro? to*'i kie^?u record Node

root := DocMotSo(s, i);

tra? ve^` gia' tri. cu?a root

end function TaoCayChoMotSo

d)
function TaoCayChoCanBan
tra? ve^` 1 con tro? to*'i kie^?u record Node
tham so^' s: string
tham so^' i: so^' nguye^n (truye^`n ba(`ng THAM CHIE^'U, 0 truye^`n ba(`ng GIA' TRI.)

khai ba'o bie^'n cu.c bo^. root: con tro? to*'i kie^?u record Node
khai ba'o bie^'n cu.c bo^. ky_tu_ke: character

ky_tu_ke := DocKyTu(s, i);
if (ky_tu_ke la` '(' )
root := ga'n TaoCayChoBieuThuc(s, i)
ky_tu_ke := DocKyTu(s, i);
if (ky_tu_ke kho^ng la` la` ')' )
in tho^ng ba'o lo^~i "Thie^'u ')' "
ngu*ng ngay chuo*ng tri`nh
end if
else
gia?m i đi 1 (tra? lui ky_tu_ke va`o bo^. đe^.m)
root: TaoCayChoMotSo(s, i)
end if

if ky_tu_ke kho^ng la` '' then
gia?m i đi 1 (tra? lui ky_tu_ke va`o bo^. đe^.m)
end if

tra? ve^` gia' tri. cu?a root

end function TaoCayChoCanBan

e)
function TaoCayChoTichThuong
tra? ve^` 1 con tro? to*'i kie^?u record Node
tham so^' s: string
tham so^' i: so^' nguye^n (truye^`n ba(`ng THAM CHIE^'U, 0 truye^`n ba(`ng GIA' TRI.)

khai ba'o bie^'n cu.c bo^. root: con tro? to*'i kie^?u record Node
khai ba'o bie^'n cu.c bo^. p: con tro? to*'i kie^?u record Node
khai ba'o bie^'n cu.c bo^. ky_tu_ke: character

root := TaoCayChoCanBan(s, i)
ky_tu_ke := DocKyTu(s, i);

loop (ky_tu_ke la` '*' hay '/')
p := root
Xin ca^'p pha't bie^'n con tro? root (tui 0 nho*' cu' pha'p)
root^data := ky_tu_ke
root^contrai := p
root^conphai := TaoCayChoTichThuong(s, i)
end loop

if ky_tu_ke kho^ng la` '' then
gia?m i đi 1 (tra? lui ky_tu_ke va`o bo^. đe^.m)
end if

tra? ve^` gia' tri. cu?a root

end function TaoCayChoTichThuong

f)
function TaoCayChoBieuThuc
tra? ve^` 1 con tro? to*'i kie^?u record Node
tham so^' s: string
tham so^' i: so^' nguye^n (truye^`n ba(`ng THAM CHIE^'U, 0 truye^`n ba(`ng GIA' TRI.)

khai ba'o bie^'n cu.c bo^. root: con tro? to*'i kie^?u record Node
khai ba'o bie^'n cu.c bo^. p: con tro? to*'i kie^?u record Node
khai ba'o bie^'n cu.c bo^. ky_tu_ke: character

root := TaoCayChoTichThuong(s, i)
ky_tu_ke := DocKyTu(s, i);

loop (ky_tu_ke la` '+' hay '-')
p := root
Xin ca^'p pha't bie^'n con tro? root (tui 0 nho*' cu' pha'p)
root^data := ky_tu_ke
root^contrai := p
root^conphai := TaoCayChoBieuThuc(s, i)
end loop

if ky_tu_ke kho^ng la` '' then
gia?m i đi 1 (tra? lui ky_tu_ke va`o bo^. đe^.m)
end if

tra? ve^` gia' tri. cu?a root

end function TaoCayChoBieuThuc

3) chuo*ng tri`nh chi'nh:

khai ba'o bie^'n toa`n cu.c s: string [20];
khai ba'o bie^'n toa`n cu.c i: so^' nguye^n
khai ba'o bie^'n toa`n cu.c j: so^' nguye^n
khai ba'o bie^'n toa`n cu.c root: con tro? to*'i kie^?u record Node

kho*?i ta.o s:= "1 * 2 + 3"
kho*?i ta.o i := 1 (ma?ng trong Pascal co' pha?i ba(`ng đa^`u tu*` chi? so^' 1 !?)
kho*?i ta.o j := 0;

root := TaoCayChoBieuThuc(s, i);
InCay(root, j)

end chuo*ng tri`nh chi'nh

Luu* y': bo^` vie^'t thu*? co' gi` sai thi` cho tui bie^'t
Đê^? test chuo*ng tri`nh => bo^` thay đo^?i gia' tri. kho*?i ta.o cu?a s.
Bo^` co' the^? đo^?i chuo*ng tri`nh đe^? nha^.p s tu*` ba`n phi'm, file , .....

[bete]

Tui lo^.n trong procedure InCay 1 chu't:


bo^` su*?a:

if contrai 0 la` NIL then
InCay(p^conphai, 0)
end

tha`nh

if conphai 0 la` NIL then
InCay(p^conphai, 0)
end


Tui co`n thie^'u:

function DocKyTu
tra? ve^` 1 ky' tu*.
tham so^' s: string
tham so^' i: so^' nguye^n (truye^`n ba(`ng THAM CHIE^'U, 0 truye^`n ba(`ng GIA' TRI.)

khai ba'o bie^'n cu.c bo^. ky_tu_ke: character

if i > len(s) then
ky_tu_ke = '' (ky' tu*. tro^'ng)
else
loop trong khi i <= len(s) va` ky' tu*. o*? chi? so^' cu?a s la` 1 khoa?ng tro^'ng ' '
tan(ng i le^n 1
end loop
ìf i > len(s) then
ky_tu_ke = '' (ky' tu*. tro^'ng)
end if
end if

tra? ve^` gia' tri. cu?a ky'_tu_ke
end function DocKyTu

[unfriendlyboy]

Uhm, cám ơn bạn nhiều lắm. Để mình thử đã. :)

À, mà bạn đổi tên thành Hay Lộn được đó :p

[bete]

>> À, mà bạn đổi tên thành Hay Lộn được đó :p

==> Ta.i vi` tui co' ca'i ta^.t xa^'u "ca('t & da'n" (copy & paste). Ma` la.i la`m
bie^'ng 0 coi la.i truo*'c khi na.p ba`i. To*'i lu'c ba`i đa(ng le^n ro^`i mo*'i tha^'y :)

Ne^'u bo^` vie^'t xong code (compile 0 co' lo^~i) nhu*ng ma` cha.y 0 đu'ng thi`
co' the^? thu*? debug ba(`ng ca'ch su*?a chuo*ng tri`nh chi'nh nhu* sau:

1) Kie^?m tra coi TaoCayChoMotSo co' đu'ng:
kho*?i ta.o s = "1"
root := TaoCayChoMotSo(s, i);
InCay(root, j)

ne^'u đu'ng thi` thu*? tie^'p s = "12", s = "123", s = " 1", s = "1 ", s = " 1 ", s = " 12",
s = "12 ", s = " 12 "

Lu*u y': 0 đuo*.c xa`i +, -, *, /, (, ) gi` he^'t !!!!

ne^'u sai thi` su*?a lo^~i (ne^'u bo^` xa`i BorlandC++/VisualC++ thi` xa`i Debug
cu?a no')

ne^'u đu'ng he^'t ma^'y truo*`ng ho*.p tre^n thi`

2) Kie^?m tra coi TaoCayChoCanBan co' đu'ng:
kho*?i ta.o s = "1"
root := TaoCayChoCanBan(s, i);
InCay(root, j)

ne^'u đu'ng thi` thu*? tie^'p s = "12", s = "123", s="(1)", s = "(12)", s= "(123)",
s = " ( 1 ) ", s = " ( 12 ) ", s = " 123 ",.....

Lu*u y': 0 đuo*.c xa`i +, -, *, / gi` he^'t !!!! Nhu*ng đuo*.c xa`i (, )

ne^'u sai thi` su*?a lo^~i

ne^'u đu'ng he^'t ma^'y truo*`ng ho*.p tre^n thi`

2) Kie^?m tra coi TaoCayChoTichThuong co' đu'ng:
kho*?i ta.o s = "1"
root := TaoCayChoTichThuong(s, i);
InCay(root, j)

ne^'u đu'ng thi` thu*? tie^'p s = "1 * 2", s = "1 * 2 * 3", s="(1)", s = "(1 * 2)",
s= " 1 * ( 2 / 3 )", s = " 1 / 2 * 3", s = " 1 / (2 * 3)", s = " (1 / 2) * 3" .....

Lu*u y': 0 đuo*.c xa`i +, - gi` he^'t !!!! Nhu*ng đuo*.c xa`i (, ), *, /

ne^'u sai thi` su*?a lo^~i

ne^'u đu'ng he^'t ma^'y truo*`ng ho*.p tre^n thi`

2) Kie^?m tra coi TaoCayChoBieuThuc co' đu'ng:
kho*?i ta.o s = "1"
root := TaoCayChoBieuThuc(s, i);
InCay(root, j)

ne^'u đu'ng thi` thu*? tie^'p s = "1 * 2", s = "1 * 2 * 3", s="(1)", s = "(1 * 2)",
s= " 1 * ( 2 / 3 )", s = " 1 / 2 * 3", s = " 1 / (2 * 3)", s = " (1 / 2) * 3" .....

Lu*u y': 0 +, -, *, /, (, ) gi` cu~ng cho*i he^'t :)


ne^'u sai thi` su*?a lo^~i

ne^'u đu'ng he^'t ma^'y truo*`ng ho*.p tre^n thi`

[unfriendlyboy]

Có mấy thắc mắc:

1. Dùng pascal thì làm sao phân biệt được truyền tham chiếu hay tham trị ?
2.
gia?m i đi 1 (tra? lui ky_tu_ke va`o bo^. đe^.m)
Là sao ?
3.
ky_tu_ke := DocKyTu(s, i);

loop (ky_tu_ke la` 1 chu*~ so^' '0' -> '9')
ga'n ky_tu_ke vo^ chi? so^' thu*' j cu?a motso
ta(ng j le^n 1
ky_tu_ke := DocKyTu(s, i);
end loop

Chỗ này sao kì kì vậy ? Tăng j thì đâu có liên quan gì đến DocKyTu ?

[bete]

1. Dùng pascal thì làm sao phân biệt được truyền tham chiếu hay tham trị ?

a) truye^`n ba(`ng gia' tri.:

procedure s1 (n1: integer) ....

b) truye^`n ba(`ng tham chie^'u (truye^`n ba(`ng đi.a chi?):

procedure s2 (var n2: integer) ....

Ne^'u bo^` 0 thi'ch truye^`n ba(`ng tham chie^'u thi` xa`i bie^'n toa`n cu.c. Tuy
nhie^n de^` bi. hie^.u u*'ng le^` (side effect) => debug me^.t


2. gia?m i đi 1 (tra? lui ky_tu_ke va`o bo^. đe^.m)

==> i := i-1;

Ly' do phai tra? lui 1 ky' tu*. la` vi` vi' du. mi`nh co' : 1+2

a) mi`nh se~ ra'ng đo.c 1 so^' nguye^n:
đuo*.c 1
đuo*.c +: ky' tu*. "+" 0 pha?i la` chu*~ so^' ==> pha?i tra? lui đe^? la^`n to*'i mi`nh đo.c 1 ky' tu*. thi` se~ ga(.p da^'u +. Ne^'u 0 tra? lui thi` la^`n to*'i mi`nh đo.c ky' tu*. se~ ga(.p so^' 2 ==> da^'u + bi. ro*i ma^'t tie^u !!!!

3. Tui nho*' 0 la^`m thi` ma?ng trong Pascal ba('t đa^`u tu*` chi? so^' 1 pha?i 0 !?

gia? su*? mi`nh co' chuo^~i s= "123+456". gia? su*? the^m mi`nh vu*` đo. c xong
so^' 123 & da^'u + => i đang la` 5 (chi? to*'i ky' tu*. "4"). Lu'c na`y j se~ la` 1 (
mi`nh đang chua^?n bi. đo.c so^' nguye^n 456):

i=5; j=1 => đo.c ky' tu*. "4" vo^ ky' tu*. chi? so^' 1 cu?a motso => motso = "4"
i=6; j=2 => đo.c ky' tu*. "5" vo^ ky' tu*. chi? so^' 2 cu?a motso => motso = "45"
i=7; j=3 => đo.c ky' tu*. "6" vo^ ky' tu*. chi? so^' 3 cu?a motso => motso = "456"

Ne^'u mi`nh 0 ta(ng j thi`:

i=5; j=1 => đo.c ky' tu*. "4" vo^ ky' tu*. chi? so^' 1 cu?a motso => motso = "4"
i=6; j=1 => đo.c ky' tu*. "5" vo^ ky' tu*. chi? so^' 1 cu?a motso => motso = "5"
i=7; j=1 => đo.c ky' tu*. "6" vo^ ky' tu*. chi? so^' 1 cu?a motso => motso = "6"

[unfriendlyboy]

Ý mình hỏi là bạn: DocKyTu(s, i) mà, đâu phải DocKyTu(s, j) đâu. Mà biến j cũng đâu khai báo toàn cục ?

[bete]

Đu'ng la` DocKyTu(s, i); kho^ng pha?i DocKyTu(s, j)
No'i cho ro~ ho*n, mi`nh co' 2 string (chuo^~i, xa^u) o*? đa^y:

1) input: chuo^~i s, đi ca(.p vo*'i bie^'n toa`n cu.c i
2) output: chuo^~i motso, đi ca(.p vo*'i bie^'n cu.c bo^. j

Ha`m DocKyTu se~ đo.c ky' tu*. chi? so^' i trong s va` ga'n va`o ky' tu*. chi? so^'
j trong motso

[unfriendlyboy]

Chỗ này:

if i > len(s) then
ky_tu_ke = '' (ky' tu*. tro^'ng)
else


ky_tu_ke đây là kiểu char, làm sao để kí tự trống được, nếu để spacebar thì trình biên dịch nói mới chịu ? :(

[avalanche]

trong chổ này thử.
http://www.cs.colorado.edu/~karl/2270.fall03/programs/DirectoryTrees/

[unfriendlyboy]

Cám ơn bạn, nhưng mình không biết C, bạn có thể tìm cái nào về Pascal được không :)

[bete]

bo^ co' the^? la`m nhu* sau: sau khi nha^.p chuo^~i s thi` the^m ky'
tu*. '=' va`o cuo^'i. Thi' du. "1 + 2 * 3" ==> "1 + 2 * 3=".
Va` thay vi` kie^?m tra xem dockytu() tra? ve^` ky' tu*. tro^'ng thi` kie^?m
tra xem dockytu() tra co' ve^` da^'u ba(`ng '=' ?

[bete]

unfriendlyboy làm tới đâu rồi ? Có cần giúp gì 0 ?

[unfriendlyboy]

Ah, tạm thời boy phải bỏ dở việc này để chuẩn bị cho kì thi sắp đến. anh bete có source kô cho em luôn đi :)

[bete]

unfriendly 0 cần gấp phải 0 (để coi chơi chớ 0 phải nộp cho thầy phải 0) ?
mình có làm tạo cây & tính đạo hàm sơ sơ; nhưng đang muốn làm thêm vẽ đồ thị :)

[unfriendlyboy]

Uhm, cám ơn anh nhiều lắm, thế anh gửi cho em được kô ? :)

[bete]

Gửi được chứ . Nhưng mà post lên hay là gửi riêng ?
Mình muốn upload lên => tạo 1 cái link => unfriendlyboy chỉ việc bấm chuột vô để download. Nhưng 0 biết làm ra sao :)

[unfriendlyboy]

À, cái đó anh dùng chức năng upload của dd trong bài post đó ;)

[moibelgal]

Cách dùng stack : bạn cần tìm đọc các cuốn sách về cấu trúc dữ liệu , tìm chương STACK ( hay NGĂN XẾP ) . Ở đó bạn sẽ thấy ứng dụng của stack đó là "Máy tính RPN " . Nghĩa là ta sẽ nhận 1 xâu phép tính từ người dùng ( gọi là " biểu thức trung tố" ) sau đó biểu diễn nó sang dạng " biểu thức trung tố" để tính toán biểu thức ban đầu.
VD :
. Trung tố : 3*(4+7)/10 + 4
. Hậu tố : 3 4 7 + * 10 / 4 -

Khi đọc sách bạn sẽ hiểu rõ hơn .

[moibelgal]

Một vài quyển sách có máy tính RPN : Cấu trúc dữ liệu với Java (NXB LĐXH) hay Lập trình dữ liệu nâng cao với Pascal (dịch bởi Trần Minh Trung - 2 tập ) ...

[bete]

Chương trình còn nhiều chỗ cần sửa nhưng lười qúa, unfriendlyboy rảnh thì coi lại (nhập biểu thức từ bàn phím, cho phép số âm, ........)


program DaoHam;
uses crt;
const
kieuTenBien = 1;
kieuSo = 2;
kieuMoNgoac = 3;
kieuDongNgoac = 4;
kieuToanTu = 5;
kieuTenHam = 6;
type
TokenPointer = ^Token;
Token = record
data: String;
kieu: integer;
next: TokenPointer;
end;

TreeNodePointer = ^TreeNode;
TreeNode = record
data: String;
kieu: integer;
left: TreeNodePointer;
right: TreeNodePointer;
end;
var
s: string;
xauToken: TokenPointer;
cacToken: TokenPointer;
cayChinh: TreeNodePointer;
cayDaoHam: TreeNodePointer;
cayDaoHamMoi: TreeNodePointer;

procedure DocBieuThuc(var s: string);
begin { DocBieuThuc }
{s := ' (246 ^ 123) * ( 345 + 678 - log(x) ) ';}
s := '(1^2) * (3+4-ln(x))';
s := '1*x^3 + 2*x^2 + 3*x + 4';
s := '-2^x';
s := 'ln sin x';
end; { DocBieuThuc }

function DoiRaSo(s: string): integer;
var n: integer;
len: integer;
soAm: boolean;
idx: integer;
i: integer;
begin
n := 0;
len := length(s);

if (s[i] = '-') then
begin
soAm := true;
idx := 2;
end
else
begin
soAm := false;
idx := 1;
end;

for i:=idx to len do
begin
n := n*10 + ord(s[i]) - ord('0');
end;

if (soAm) then
begin
n := -n;
end;

DoiRaSo := n;
end;

function DoiRaChu(n: integer): String;
var s: String;
soAm: boolean;
chuSoCuoiCung: integer;
chuSoDauTien: String;
begin
if (n < 0) then
begin
soAm := true;
n := -n;
end
else
begin
soAm := false;
end;

s := '';

while (n > 9) do
begin
chuSoCuoiCung := n mod 10;
n := n div 10;
end;

chuSoDauTien := chr(n + ord('0'));
s := chuSoDauTien + s;


if (soAm) then
begin
s := '-' + s;
end;

{writeln('');
write(n);
writeln(' -> "' + s + '" ("' + chuSoDauTien + '")');}

DoiRaChu := s;
end;

function IsAlpha(c: char): boolean;
begin
IsAlpha := (((c >= 'a') and (c <= 'z')) or ((c >= 'A') and (c <= 'Z')));
end;

function IsDigit(c: char): boolean;
begin
IsDigit := ((c >= '0') and (c <= '9'));
end;

function IsAlphaNum(c: char): boolean;
begin
IsAlphaNum := IsAlpha(c) or IsDigit(c);
end;

function TaoToken(var data: String; kieu: integer): TokenPointer;
var token: TokenPointer;
begin { TaoToken }
New(Token);
token^.data := data;
token^.kieu := kieu;
token^.next := nil;
TaoToken := token;
end; { TaoToken }

function TaoCacToken(var s: String): TokenPointer;
var
data: String;
kieu: integer;
i: integer;
len: integer;
xauToken: TokenPointer;
p: TokenPointer;
begin { TaoCacToken }

len := Length(s);
i := 1;

writeln('Bieu thuc: ' + s);

p := nil;
while (i <= len) do
begin
{ bo qua cac khoang trong }
while ((i <= len) and (s[i] = ' ')) do
begin
i := i+1;
end;

{ chua het chuoi s }
if (i <= len) then
begin
if IsDigit(s[i]) then
begin
data := '';
while ((i <= len) and IsDigit(s[i])) do
begin
data := data + s[i];
kieu := kieuSo;
i := i + 1;
end;
writeln('So nguyen: ' + data);
end

else if (IsAlpha(s[i])) then
begin
data:= '';
while ((i <= len) and IsAlpha(s[i])) do
begin
data := data + s[i];
i := i+1;
end;

if ((data = 'ln')
or (data = 'lg')
or (data = 'log')
or (data = 'sin')
or (data = 'cos')
or (data = 'tan')
or (data = 'cotg')
) then
begin
kieu := kieuTenHam;
writeln('ham: ' + data);
end

else
begin
kieu := kieuTenBien;
writeln('bien: ' + data);
end;

end

else
begin
data := s[i];
i := i+1;
if (data = '(') then
begin
writeln('mo ngoac don: ' + data);
kieu := kieuMoNgoac;
end

else if (data = ')') then
begin
writeln('dong ngoac don: ' + data);
kieu := kieuDongNgoac;
end

else
begin
writeln('toan tu: ' + data);
kieu := kieuToanTu;
end
end;

if (p = nil) then
begin
{ writeln('Tao token dau tien: ' + data); }
p := TaoToken(data, kieu);
TaoCacToken := p;
end

else
begin
{ writeln('Tao 1 token nua: ' + data); }
p^.next := TaoToken(data, kieu);
p := p^.next;
end
end;
end;


end; { TaoCacToken }

procedure XoaCacToken(xauToken: TokenPointer);
var p: TokenPointer;
begin { XoaCacToken }
write('XoaCacToken:');
while (xauToken <> nil) do
begin
write(' ' + xauToken^.data);
p := xauToken^.next;
Dispose(xauToken);
xauToken := p;
end;
writeln('');
end; { XoaCacToken }

procedure InCacToken(pToken: TokenPointer);
begin { InCacToken }
write('Token:');
while (pToken <> nil) do
begin
write(' ' + pToken^.data + '[');
write(pToken^.kieu);
write(']');
pToken := pToken^.next;
end;
writeln('');
end; { InCacToken }

function TaoTreeNode(var token: TokenPointer; pLeft: TreeNodePointer; pRight: TreeNodePointer): TreeNodePointer;
var p: TreeNodePointer;
begin
p := nil;
if (token <> nil) then
begin
New(p);
p^.data := token^.data;
p^.kieu := token^.kieu;
p^.left := pLeft;
p^.right := pRight;
token := token^.next;
end;
TaoTreeNode := p;
end;

function TaoTreeNode2(data: String; kieu: integer; pLeft: TreeNodePointer; pRight: TreeNodePointer): TreeNodePointer;
var p: TreeNodePointer;
begin
New(p);
p^.data := data;
p^.kieu := kieu;
p^.left := pLeft;
p^.right := pRight;
TaoTreeNode2 := p;
end;

function TrongSoCuaToanTu(toanTu: String; kieu: integer): integer;
begin
if ((toanTu = '+') or (toanTu = '-')) then TrongSoCuaToanTu := 1
else if ((toanTu = '*') or (toanTu = '/')) then TrongSoCuaToanTu := 2
else if ((toanTu = '^') or (toanTu = '\')) then TrongSoCuaToanTu := 3
else if (kieu = kieuTenHam) then TrongSoCuaToanTu := 4
else TrongSoCuaToanTu := 5;
begin
end;
end;

procedure InBieuThuc(cay: TreeNodePointer);
begin
if (cay <> nil) then
begin
if ((cay^.kieu = kieuToanTu) or (cay^.kieu = kieuTenHam)) then
begin
{ toan tu lay 2 toan hang }
if (cay^.right <> nil) then
begin

{if ((cay^.left <> nil)
and (cay^.left^.kieu = kieuToanTu)) then
begin}

{ in cay con trai }
if (TrongSoCuaToanTu(cay^.data, cay^.kieu)
> TrongSoCuaToanTu(cay^.left^.data, cay^.left^.kieu)) then
begin
write('(');
InBieuThuc(cay^.left);
write(')');
end

else
begin
InBieuThuc(cay^.left);
end;

{in toan tu }
write(cay^.data);

{ in cay con phai }
if (TrongSoCuaToanTu(cay^.data, cay^.kieu)
> TrongSoCuaToanTu(cay^.right^.data, cay^.right^.kieu)) then
begin
write('(');
InBieuThuc(cay^.right);
write(')');
end

else
begin
InBieuThuc(cay^.right);
end

{end

else
begin
end}

end

{toan tu lay 1 toan hang }
else
begin
write(cay^.data + ' ');
InBieuThuc(cay^.left);
end;
end

else
begin
write(cay^.data);
end;
end;
end;

procedure InCayCon(cay: TreeNodePointer; level: integer);
var i: integer;
begin { InCay }
if (cay <> nil) then
begin
for i := 1 to 4*level do
begin
write(' ');
end;

if (level > 0) then
begin
write('\');
end

else
begin
write('-');
end;

write('->');
writeln(' ' + cay^.data);
{write(' [k=');
write(cay^.kieu);
write(' -> ts=');
write(TrongSoCuaToanTu(cay^.data, cay^.kieu));
writeln(']');}

if (cay^.left <> nil) then
begin
InCayCon(cay^.left, level+1);
end;

if (cay^.right <> nil) then
begin
InCayCon(cay^.right, level+1);
end;
end;
end; { InCay }

procedure InCay(cay: TreeNodePointer);
begin { InCay }
InCayCon(cay, 0);
end; { InCay }

function KiemTraCay(cay: TreeNodePointer): boolean;
begin
if (cay^.kieu = kieuToanTu) then
begin
if ((cay^.left = nil) or (cay^.right = nil)) then
begin
writeln('Sai: goc la [' + cay^.data + ']');
write('Con trai la:');
InCay(cay^.left);
writeln('');
write('Con phai la:');
InCay(cay^.right);
writeln('');
halt;
end;
end

else if ((cay^.kieu = kieuSo) or (cay^.kieu = kieuTenBien)) then
begin
if ((cay^.left <> nil) or (cay^.right <> nil)) then
begin
writeln('Sai: goc la [' + cay^.data + ']');
write('Con trai la:');
InCay(cay^.left);
writeln('');
write('Con phai la:');
InCay(cay^.right);
writeln('');
halt;
end;
end

else
begin
end;

end;

procedure XoaCay(cay: TreeNodePointer);
begin
if (cay <> nil) then
begin
{
if ((cay^.left <> nil) and (cay^.right <> nil)) then
begin
write('(');
XoaCay(cay^.left);
write(' ' + cay^.data + ' ');
XoaCay(cay^.right);
write(')');
end

else if (cay^.left <> nil) then
begin
write(' ' + cay^.data + ' ');
write('(');
XoaCay(cay^.left);
write(')');
end

else
begin
write('' + cay^.data + '');
end;
}

XoaCay(cay^.left);
XoaCay(cay^.right);
Dispose(cay);
end;
end;

function TaoCayChoBieuThuc(var xauToken: TokenPointer): TreeNodePointer; forward;

function TaoCayChoSo(var xauToken: TokenPointer): TreeNodePointer;
var p: TreeNodePointer;
begin
p := nil;
if (xauToken <> nil) then
begin
p := TaoTreeNode(xauToken, nil, nil);
end;
TaoCayChoSo := p;
end;

function TaoCayChoCanBan(var xauToken: TokenPointer): TreeNodePointer;
var p: TreeNodePointer;
begin
if (xauToken <> nil) then
begin
{if (IsDigit(xauToken^.data[1])) then}
if (xauToken^.kieu = kieuSo) then
begin
p := TaoCayChoSo(xauToken);
end

else if (xauToken^.kieu = kieuTenBien) then
begin
{p := TaoCayChoBien(xauToken);}
p := TaoTreeNode(xauToken, nil, nil);
end

else if (xauToken^.data[1] = '(') then
begin
xauToken := xauToken^.next;
p := TaoCayChoBieuThuc(xauToken);
if ((xauToken <> nil) and (xauToken^.data[1] = ')')) then
begin
xauToken := xauToken^.next;
end

else
begin
write('Thieu dau dong ngoac don: ');
InCacToken(xauToken);
halt;
end;
end

else
begin
writeln('Token 0 hop le: "' + xauToken^.data + '" (dang cho so hoac dau mo ngoac don)');
halt;
end;
end;
TaoCayChoCanBan := p;

end;

function TaoCayChoHam(var xauToken: TokenPointer): TreeNodePointer;
var toanTu: String;
p: TreeNodePointer;
q: TreeNodePointer;
begin
p := nil;
if (xauToken <> nil) then
begin
if (xauToken^.kieu = kieuTenHam) then
begin
New(p);
p^.data := xauToken^.data;
p^.kieu := xauToken^.kieu;
xauToken := xauToken^.next;
{p^.left := TaoCayChoCanBan(xauToken);}
p^.left := TaoCayChoHam(xauToken);
p^.right := nil;
end

else if ((xauToken^.kieu = kieuToanTu)
and ((xauToken^.data = '+') or (xauToken^.data = '-'))) then
begin
New(p);
p^.data := xauToken^.data;
p^.kieu := xauToken^.kieu;
xauToken := xauToken^.next;
p^.right := TaoCayChoHam(xauToken);
p^.left := TaoTreeNode2('0', kieuSo, nil, nil);;
end

else
begin
p := TaoCayChoCanBan(xauToken);
end;

end;
TaoCayChoHam := p;
end;

function TaoCayChoLuyThuaCanSo(var xauToken: TokenPointer): TreeNodePointer;
var toanTu: String;
p: TreeNodePointer;
q: TreeNodePointer;
begin
p := nil;
if (xauToken <> nil) then
begin
p := TaoCayChoHam(xauToken);
while ((xauToken <> nil)
and ((xauToken^.data = '^') or (xauToken^.data = '\'))) do
begin
toanTu := xauToken^.data;
xauToken := xauToken^.next;

New(q);

q^.kieu := kieuToanTu;
q^.left := p;

if (toanTu = '^') then
begin
q^.data := toanTu;

q^.right := TaoCayChoHam(xauToken);
end

else
begin
q^.data := '^';
q^.right := TaoTreeNode2('/',
kieuToanTu,
TaoTreeNode2('1', kieuSo, nil, nil),
TaoCayChoHam(xauToken));
end;

p := q;
end;
end;
TaoCayChoLuyThuaCanSo := p;
{InCay(p);}
end;

function TaoCayChoTichThuong(var xauToken: TokenPointer): TreeNodePointer;
var toanTu: String;
p: TreeNodePointer;
q: TreeNodePointer;
begin
p := nil;
if (xauToken <> nil) then
begin
p := TaoCayChoLuyThuaCanSo(xauToken);
while ((xauToken <> nil)
and ((xauToken^.data = '*') or (xauToken^.data = '/'))) do
begin
toanTu := xauToken^.data;
xauToken := xauToken^.next;
New(q);
q^.data := toanTu;
q^.kieu := kieuToanTu;
q^.left := p;
q^.right := TaoCayChoLuyThuaCanSo(xauToken);
p := q;
end;
end;
TaoCayChoTichThuong := p;
end;

function TaoCayChoBieuThuc(var xauToken: TokenPointer): TreeNodePointer;
var toanTu: String;
p: TreeNodePointer;
q: TreeNodePointer;
begin
p := nil;
if (xauToken <> nil) then
begin
p := TaoCayChoTichThuong(xauToken);
while ((xauToken <> nil)
and ((xauToken^.data = '+') or (xauToken^.data = '-'))) do
begin
toanTu := xauToken^.data;
xauToken := xauToken^.next;
New(q);
q^.data := toanTu;
q^.kieu := kieuToanTu;
q^.left := p;
q^.right := TaoCayChoTichThuong(xauToken);
p := q;
end;
end;
TaoCayChoBieuThuc := p;
end;

function TaoCayDaoHam(cay: TreeNodePointer): TreeNodePointer;
var p: TreeNodePointer;
p1: TreeNodePointer;
p2: TreeNodePointer;
begin
p := nil;
if (cay <> nil) then
begin
if (cay^.kieu = kieuSo) then
begin
New(p);
p^.data := '0';
p^.kieu := kieuSo;
p^.left := nil;
p^.right := nil;
end

else if (cay^.kieu = kieuTenBien) then
begin
New(p);
p^.data := '1';
p^.kieu := kieuSo;
p^.left := nil;
p^.right := nil;
end

else if (cay^.kieu = kieuToanTu) then
begin
if ((cay^.data = '+') or (cay^.data = '-')) then
begin
New(p);
p^.data := cay^.data;
p^.kieu := kieuToanTu;
p^.left := TaoCayDaoHam(cay^.left);
p^.right := TaoCayDaoHam(cay^.right);
end

{ (f*g)' = f'*g + g'*f }
else if (cay^.data = '*') then
begin
p1 := TaoCayDaoHam(cay^.left);
p2 := TaoCayDaoHam(cay^.right);
p := TaoTreeNode2('+',
kieuToanTu,
TaoTreeNode2('*', kieuToanTu, p1, cay^.right),
TaoTreeNode2('*', kieuToanTu, p2, cay^.left)
);
end

{ (f/g)' = (f'*g - g'*f) / g^2 }
else if (cay^.data = '/') then
begin
p1 := TaoCayDaoHam(cay^.left);
p2 := TaoCayDaoHam(cay^.right);
p := TaoTreeNode2('/',
kieuToanTu,
TaoTreeNode2('-',
kieuToanTu,
TaoTreeNode2('*', kieuToanTu, p1, cay^.right),
TaoTreeNode2('*', kieuToanTu, p2, cay^.left)),
TaoTreeNode2('^',
kieuToanTu,
cay^.right,
TaoTreeNode2('2', kieuSo, nil, nil)));
end

{ (g^h)' = h'*h*g^h + g'*h*g^(h-1) }
else if (cay^.data = '^') then
begin
p1 := TaoCayDaoHam(cay^.left);
p2 := TaoCayDaoHam(cay^.right);
p := TaoTreeNode2('+',
kieuToanTu,
TaoTreeNode2('*',
kieuToanTu,
p2,
TaoTreeNode2('*',
kieuToanTu,
TaoTreeNode2('ln', kieuTenHam, cay^.left, nil),
TaoTreeNode2('^', kieuToanTu, cay^.left, cay^.right))),
TaoTreeNode2('*',
kieuToanTu,
p1,
TaoTreeNode2('*',
kieuToanTu,
cay^.right,
TaoTreeNode2('^',
kieuToanTu,
cay^.left,
TaoTreeNode2('-',
kieuToanTu,
cay^.right,
TaoTreeNode2('1', kieuSo, nil, nil)))))
);
end

else
begin
writeln('Khong biet cach tim dao ham cho ' + cay^.data);
halt;
end
end

else if (cay^.kieu = kieuTenHam) then
begin
if (cay^.data = 'ln') then
begin
p := TaoTreeNode2('*',
kieuToanTu,
TaoCayDaoHam(cay^.left),
TaoTreeNode2('/',
kieuToanTu,
TaoTreeNode2('1', kieuSo, nil, nil),
cay^.left));
end

else if (cay^.data = 'sin') then
begin
p := TaoTreeNode2('*',
kieuToanTu,
TaoCayDaoHam(cay^.left),
TaoTreeNode2('cos',
kieuTenHam,
cay^.left,
nil));
end

else
begin
writeln('Khong biet cach tim dao ham cho ' + cay^.data);
halt;
end;
end

else
begin
writeln('Khong biet cach tim dao ham cho ' + cay^.data);
halt;
end;

end;
TaoCayDaoHam := p;
end;

function DonGianCayBieuThuc(cay: TreeNodePointer): TreeNodePointer;
var p: TreeNodePointer;
p1: TreeNodePointer;
p2: TreeNodePointer;
begin
p := nil;
if (cay <> nil) then
begin
p1 := DonGianCayBieuThuc(cay^.left);
p2 := DonGianCayBieuThuc(cay^.right);

if (cay^.kieu = kieuToanTu) then
begin
if (cay^.data = '+') then
begin
{ 0 + x -> x }
if ((p1 <> nil)
and (p1^.kieu = kieuSo)
and (p1^.data = '0')) then
begin
XoaCay(p1);
p1 := nil;
p := p2;
end

{ x + 0 -> x }
else if ((p2 <> nil)
and (p2^.kieu = kieuSo)
and (p2^.data = '0')) then
begin
XoaCay(p2);
p2 := nil;
p := p1;
end

else if ((p1 <> nil)
and (p1^.kieu = kieuSo)
and (p2 <> nil)
and (p2^.kieu = kieuSo)) then
begin
p := TaoTreeNode2(DoiRaChu(DoiRaSo(p1^.data) + DoiRaSo(p2^.data)), kieuSo, nil, nil);
XoaCay(p1);
p1 := nil;
XoaCay(p2);
p2 := nil;
end

else
begin
p := TaoTreeNode2(cay^.data, cay^.kieu, p1, p2);
end;
end

else if (cay^.data = '-') then
begin
{ x - 0 -> x }
if ((p2 <> nil)
and (p2^.kieu = kieuSo)
and (p2^.data = '0')) then
begin
XoaCay(p2);
p2 := nil;
p := p1;
end

else if ((p1 <> nil)
and (p1^.kieu = kieuSo)
and (p2 <> nil)
and (p2^.kieu = kieuSo)) then
begin
p := TaoTreeNode2(DoiRaChu(DoiRaSo(p1^.data) - DoiRaSo(p2^.data)), kieuSo, nil, nil);
write(p1^.data); write('-'); write(p2^.data); write(' -> ');
write(DoiRaSo(p1^.data)); write('-'); write(DoiRaSo(p2^.data));
write(' = '); write(p^.data); writeln;
XoaCay(p1);
p1 := nil;
XoaCay(p2);
p2 := nil;
end

else
begin
p := TaoTreeNode2(cay^.data, cay^.kieu, p1, p2);
end;
end

else if (cay^.data = '*') then
begin
{ 0 * x -> 0; x * 0 -> 0 }
if (((p1 <> nil)
and (p1^.kieu = kieuSo)
and (p1^.data = '0'))
or ((p2 <> nil)
and (p2^.kieu = kieuSo)
and (p2^.data = '0'))) then
begin
XoaCay(p1);
p1 := nil;
XoaCay(p2);
p2 := nil;
p := TaoTreeNode2('0', kieuSo, nil, nil);
end

{ 1 * x -> x }
else if ((p1 <> nil)
and (p1^.kieu = kieuSo)
and (p1^.data = '1')) then
begin
XoaCay(p1);
p1 := nil;
p := p2;
end

{ x * 1 -> x }
else if ((p2 <> nil)
and (p2^.kieu = kieuSo)
and (p2^.data = '1')) then
begin
XoaCay(p2);
p2 := nil;
p := p1;
end

else
begin
p := TaoTreeNode2(cay^.data, cay^.kieu, p1, p2);
end;

end

else if (cay^.data = '/') then
begin
{ 0 / x -> 0}
if ((p1 <> nil)
and (p1^.kieu = kieuSo)
and (p1^.data = '0')) then
begin
XoaCay(p1);
p1 := nil;
XoaCay(p2);
p2 := nil;
p := TaoTreeNode2('0', kieuSo, nil, nil);
end

else
begin
p := TaoTreeNode2(cay^.data, cay^.kieu, p1, p2);
end;

end

else if (cay^.data = '^') then
begin
{ x ^ 0 -> 1 }
if ((p2 <> nil)
and (p2^.kieu = kieuSo)
and (p2^.data = '0')) then
begin
XoaCay(p1);
p1 := nil;
XoaCay(p2);
p2 := nil;
p := TaoTreeNode2('1', kieuSo, nil, nil);
end

{ x ^ 1 -> x }
else if ((p2 <> nil)
and (p2^.kieu = kieuSo)
and (p2^.data = '1')) then
begin
XoaCay(p2);
p2 := nil;
p := p1;
end

{ 0 ^ x -> 0 }
else if ((p1 <> nil)
and (p1^.kieu = kieuSo)
and (p1^.data = '0')) then
begin
XoaCay(p1);
p1 := nil;
XoaCay(p2);
p2 := nil;
p := TaoTreeNode2('0', kieuSo, nil, nil);
end

{ 1 ^ x -> 1 }
else
if ((p1 <> nil)
and (p1^.kieu = kieuSo)
and (p1^.data = '1')) then
begin
XoaCay(p1);
p1 := nil;
XoaCay(p2);
p2 := nil;
p := TaoTreeNode2('1', kieuSo, nil, nil);
end

else
begin
p := TaoTreeNode2(cay^.data, cay^.kieu, p1, p2);
end;

end

else
begin
p := TaoTreeNode2(cay^.data, cay^.kieu, p1, p2);
end;
end

else
begin
p := TaoTreeNode2(cay^.data, cay^.kieu, p1, p2);
end;

end;

DonGianCayBieuThuc := p;
end;

begin { DaoHam }
clrscr;
DocBieuThuc(s);
{writeln('s: "' + s + '"');}
{s := '123 * 456';}
xauToken := TaoCacToken(s);
InCacToken(xauToken);

{ TaoCayChoBieuThuc() se thay doi tham so -> copy ra 1 bien ra truoc khi goi }
cacToken := xauToken;

cayChinh := TaoCayChoBieuThuc(cacToken);
writeln('CayChinh:');
InCay(cayChinh);
write('CayChinh: ');
InBieuThuc(cayChinh);
writeln('');

cayDaoHam := TaoCayDaoHam(cayChinh);
writeln('CayDaoHam:');
InBieuThuc(cayDaoHam);
writeln('');
{InCay(cayDaoHam);}

cayDaoHamMoi := DonGianCayBieuThuc(cayDaoHam);
writeln('CayDaoHamMoi:');
InCay(cayDaoHamMoi);
write('BieuThucDaoHam: ');
InBieuThuc(cayDaoHamMoi);
writeln('');

XoaCacToken(xauToken);

writeln('Xoa cay ...');
XoaCay(cayChinh);
writeln('');

XoaCay(cayDaoHam);
writeln('');

XoaCay(cayDaoHamMoi);
writeln('');

end. {DaoHam }

[unfriendlyboy]

Thx, để em về nghiên kíu đã :) ;)