[Tutorial] – Bài tập biểu thức (4)

  • Nội dung phần 4:

Ở bài tập biểu thức 2, lớp Expression đã được trang bị khả năng trả về chuỗi biểu thức biểu diễn nó (xem hình 1).

Hình 1 – Phương thức toString trả về chuỗi biểu thức biểu diễn đối tượng Expression

Thông thường, chuỗi biểu diễn biểu thức ở dạng trung tố. Tuy nhiên trong toán học, có nhiều cách biểu diễn chuỗi biểu thức khác nhau (xem bảng 1).

Bảng 3.1 – Các cách biểu diễn chuỗi biểu thức.
Cách biểu diễn Mô tả Ví dụ
Trung tố (infix) Toán tử nằm giữa các toán hạng.
Là cách biểu diễn thông dụng.
Toán tử cần có độ ưu tiên và phải dùng dấu
ngoặc để thay đổi độ ưu tiên này.
2 * ( ( 3 + 4 ) / 5 )
Tiền tố (prefix) Toán tử đứng trước, các toán hạng đứng sau.
Là cách biểu diễn của ngôn ngữ Lisp.
Toán tử không cần độ ưu tiên và không cần
dùng dấu ngoặc
* 2 / + 3 4 5
Hậu tố (postfix) Toán tử đứng sau, các toán hạng đứng trước.
Là cách biểu diễn Ba Lan Ngược (Reversed
Polish Notation).
Toán tử không cần độ ưu tiên và không cần
dùng dấu ngoặc
2 3 4 + 5 / *

Nhiệm vụ của bạn là hãy đề xuất một phương án cải tiến phương thức toString nhằm thỏa mãn các tiêu chí:
i) Hỗ trợ nhiều cách biểu diễn chuỗi biểu thức khác nhau.
ii) Trong tương lai, khi cần bổ sung một cách biểu diễn chuỗi biểu thức mới (nằm ngoài bảng 1), bạn không phải chỉnh sửa lại những gì đã cài đặt

  • Sơ đồ lớp:

so do bieu thuc 4

 

==> Sourcecode (link bitbucket – project tổng hợp)

 

Advertisements

[Tutorial] – Bài tập biểu thức (3)

  • Nội dung phần 3

Tiếp tục xét ngữ cảnh lớp Expression như đã giải trong bài tập biểu thức 2, bạn được giao phát triển thêm một số yêu cầu mở rộng như sau:

i.  Đơn thức có hệ số a hoặc số mũ n bằng 0 sẽ tự động được chuyển thành hằng số tương ứng. Hãy thay đổi cách khởi tạo đơn thức để thực hiện được điều này.
ii.  Hằng số 0 (zero) là một giá trị đặc biệt cần được áp đặt duy nhất (dùng chung) trên toàn ứng dụng. Hãy bổ sung lớp hằng số để thực hiện đượcđiều này.

  • Sơ đồ lớp: (so với bài 2, ngoài bổ sung theo yêu cầu, có chút điều chỉnh lại phương thức ExprString() thành phương thức toString() )

Expression3

[Tutorial] – Bài tập biểu thức (2)

  • Nội dung phần 2:

Xét ngữ cảnh lớp Expression được tổ chức phân cấp như đã giải trong bài tập biểu thức 1, bạn được giao phát triển thêm một số yêu cầu mở rộng như sau:

i.   Hãy trang bị cho đối tượng Expression khả năng trả về chuỗi biểu thức biểu diễn nó.
ii. Việc tính đạo hàm cho những biểu thức lồng nhau nhiều cấp có thể mất nhiều thời gian.

Với những biểu thức như vậy, sẽ không hiệu quả nếu mỗi lần tính đạo hàm, việc tính toán được thực hiện lại toàn bộ. Hãy đề xuất một giải pháp để nâng cao tốc độ tính đạo hàm của những biểu thức lồng nhau.

  • Nhận xét:

    • Câu a: chỉ cần thêm 1 phương thức toString() (có thể bổ sung vào lớp Expression, lớp con kế thừa lại hoặc là override phương thức toString() từ lớp Object có sẵn trong ngôn ngữ lập trình) -> trong bài 2 này tôi tự tạo cho Expression 1 phương thức mới ExpString();
    • Câu b: Việc tính toán kiểu đệ qui trong composite được thực hiện lại -> dùng biến tạm lưu trữ lại giá trị của đạo hàm -> khi cần chỉ cần gọi lại (nếu có), nếu chưa có thì tính đạo hàm, và cũng lưu vào biến tạm => bổ sung vào lớp Expression thuộc tính _deriveExpr (kiểu Expression) ==> bổ sung phương thức getDerive() để lấy giá trị _deriveExpr.
    <br />
    Expression getDerive(){<br />
        if(_deriveExpr == null){<br />
            _deriveExpr = derive();<br />
        }<br />
        return _deriveExpr;<br />
    }<br />
    
    • ==> Phát sinh vấn đề: ở hàm main (tức là người dùng) đang gọi phương thức derive() cho việc tính đạo hàm  -> làm thế nào cập nhật được lại chức năng tính đạo hàm của chương trình (bây giờ hàm tính đạo hàm là getDerive()) ==> đổi tên các phương thức derive() trong các lớp con thành getDerive() và ngược lại.
    • ==> Lại có vấn đề: bây giờ trong lớp Expression có 2 phương thức tính đạo hàm là derive()getDerive(), người dùng có thể gọi được cả 2 phương thức sao –> để getDerive() thành protected
    • ==> Chúng ta đang dùng mẫu template method.
  • Sơ đồ lớp:

Expression2

  • Cài đặt (C#):

Continue reading

[Tutorial] – Bài tập biểu thức (1)

  • Nội dung phần 1:

xLib là bộ thư viện lập trình hỗ trợ các tính toán trên biểu thức một biến. Lớp đối tượng chính của xLib là lớp Expression, đại diện cho một biểu thức một biến. Mọi tính toán trên biểu thức đều được cung cấp thông qua lớp đối tượng này. Hiện tại lớp Expression cung cấp hai tính toán thông dụng trên biểu thức là tính giá trị và tính đạo hàm (xem hình 1)

Expression

(Hình 1 – Lớp đối tượng Expression của xLib)

Là thành viên của nhóm phát triển xLib, bạn hãy đề xuất một cách tổ chức lớp Expression sao cho việc việc xử lý tính giá trị và tính đạo hàm thỏa mãn hai tiêu chí:

i) Có thể tính đạo hàm cho các loại biểu thức khác nhau (xem bảng 1).
ii) Trong tương lai, khi cần bổ sung công thức đạo hàm cho một loại biểu thức mới (nằm ngoài bảng 1), không phải chỉnh sửa những tính toán đã cài đặt cho lớp Expression

Bảng 1 – Công thức tính đạo hàm cho biểu thức một biến.
Loại biểu thức Dạng biểu thức Công thức tính đạo hàm
Biểu thức hằng (hằng số) C (với C là hằng số) 0
Biểu thức đơn (đơn thức) Ax^N (với hệ số A, số mũ N) (AN) x^(N-1)
Biểu thức tổng u + v (với u, v là một biểu thức) u’ + v’
Biểu thức tích u * v (với u, v là một biểu thức) u’v + uv’
Biểu thức chia u / v (với u, v là một biểu thức) (u’v – uv’) / v2
  • Ý tưởng:
    • Các biểu thức trên đều kế thừa từ Expression
    • Đa biểu thức bao gồm nhiều biểu thức đơn, và có thể phân tích như một cây nhị phân, và máy tính chỉ xử lý 1 lần 1 toán tử ==> (đa thức chỉ cần lưu trữ 2 biểu thức đơn (đa) + toán tử)==> 1 đối tượng (class)
    • Mẫu composite
  • Sơ đồ lớp:

expression1

  •  Cài đặt:

Continue reading