[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#):

Expression.cs

<br />
namespace xLib<br />
{<br />
    public abstract class Expression<br />
    {<br />
        private Expression _deriveExp = null;</p>
<p>        public abstract double evaluate(double x);<br />
        public Expression derive()<br />
        {<br />
            if (_deriveExp == null)<br />
            {<br />
                _deriveExp = getDerive();<br />
            }<br />
            return _deriveExp;<br />
        }</p>
<p>        protected abstract Expression getDerive();<br />
        public abstract string ExpString();<br />
    }<br />
}<br />

ConstExpr.cs

<br />
namespace xLib<br />
{<br />
    public class ConstExpr: Expression<br />
    {<br />
        private double _value;</p>
<p>        public ConstExpr(double value)<br />
        {<br />
            _value = value;<br />
        }</p>
<p>        public override double evaluate(double x)<br />
        {<br />
            return _value;<br />
        }</p>
<p>        protected override Expression getDerive()<br />
        {<br />
            return new ConstExpr(0);<br />
        }</p>
<p>        public override string ExpString()<br />
        {<br />
            return _value + &quot;&quot;;<br />
        }<br />
    }<br />
}<br />

MonomialExpr.cs

<br />
namespace xLib<br />
{<br />
    public class MonomialExpr: Expression<br />
    {<br />
        private double _a;<br />
        private double _n;</p>
<p>        public MonomialExpr(double a, double n)<br />
        {<br />
            _a = a;<br />
            _n = n;<br />
        }</p>
<p>        public override double evaluate(double x)<br />
        {<br />
            return _a * Math.Pow(x, _n);<br />
        }</p>
<p>        protected override Expression getDerive()<br />
        {<br />
            return new MonomialExpr(_a * _n, _n - 1);<br />
        }</p>
<p>        public override string ExpString()<br />
        {<br />
            return _a + &quot;x^&quot; + _n;<br />
        }<br />
    }<br />
}<br />

BinaryExpr.cs

<br />
namespace xLib<br />
{<br />
    public abstract class BinaryExpr: Expression<br />
    {<br />
        protected Expression _expr1;<br />
        protected Expression _expr2;</p>
<p>        public BinaryExpr(Expression e1, Expression e2)<br />
        {<br />
            _expr1 = e1;<br />
            _expr2 = e2;<br />
        }</p>
<p>        public abstract override double evaluate(double x);<br />
        protected abstract override Expression getDerive();<br />
        public abstract override string ExpString();<br />
    }<br />
}<br />

AddExpr.cs

<br />
namespace xLib<br />
{<br />
    public class AddExpr: BinaryExpr<br />
    {<br />
        public AddExpr(Expression e1, Expression e2)<br />
            : base(e1, e2)<br />
        {<br />
        }</p>
<p>        public override double evaluate(double x)<br />
        {<br />
            return base._expr1.evaluate(x) +<br />
                   base._expr2.evaluate(x);<br />
        }</p>
<p>        protected override Expression getDerive()<br />
        {<br />
            return new AddExpr(base._expr1.derive(),<br />
                               base._expr2.derive());<br />
        }</p>
<p>        public override string ExpString()<br />
        {<br />
            string s;<br />
            s = &quot;(&quot;+ base._expr1.ExpString() + &quot;) + (&quot; + base._expr2.ExpString() + &quot;)&quot;;<br />
            return s;<br />
        }<br />
    }<br />
}<br />

MulExpr.cs

<br />
namespace xLib<br />
{<br />
    public class MulExpr: BinaryExpr<br />
    {<br />
        public MulExpr(Expression e1, Expression e2)<br />
            : base(e1, e2)<br />
        {<br />
        }</p>
<p>        public override double evaluate(double x)<br />
        {<br />
            return base._expr1.evaluate(x) *<br />
                   base._expr2.evaluate(x);<br />
        }</p>
<p>        protected override Expression getDerive()<br />
        {<br />
            return new AddExpr(<br />
                        new MulExpr(<br />
                            base._expr1.derive(),<br />
                            base._expr2),<br />
                        new MulExpr(<br />
                            base._expr1,<br />
                            base._expr2.derive()));<br />
        }</p>
<p>        public override string ExpString()<br />
        {<br />
            return &quot;(&quot; + base._expr1.ExpString() + &quot;) * (&quot; + base._expr2.ExpString() + &quot;)&quot;;<br />
        }<br />
    }<br />
}<br />

DivExpr.cs

<br />
namespace xLib<br />
{<br />
    public class DivExpr: BinaryExpr<br />
    {<br />
        public DivExpr(Expression e1, Expression e2)<br />
            : base(e1, e2)<br />
        {<br />
        }</p>
<p>        public override double evaluate(double x)<br />
        {<br />
            double value = base._expr2.evaluate(x);</p>
<p>            if (value == 0)<br />
                throw new DivideByZeroException();</p>
<p>            return base._expr1.evaluate(x) / value;<br />
        }</p>
<p>        protected override Expression getDerive()<br />
        {<br />
            return new DivExpr(<br />
                        new AddExpr(<br />
                            new MulExpr(<br />
                                base._expr1.derive(),<br />
                                base._expr2),<br />
                            new MulExpr(<br />
                                new ConstExpr(-1),<br />
                                new MulExpr(<br />
                                    base._expr1,<br />
                                    base._expr2.derive()))),<br />
                        new MulExpr(<br />
                            base._expr2,<br />
                            base._expr2));<br />
        }</p>
<p>        public override string ExpString()<br />
        {<br />
            return &quot;(&quot;+ base._expr1.ExpString() + &quot;) / (&quot; + base._expr2.ExpString() + &quot;)&quot;;<br />
        }<br />
    }<br />
}<br />

Hàm main()

<br />
using xLib;<br />
namespace ExpressionDemo<br />
{<br />
    public class Program<br />
    {<br />
        public static void Main()<br />
        {<br />
            //(((x^2 + 2) / (x + 1)) + 10) / (x^2 + 5)</p>
<p>            Expression exp3 = new DivExpr(<br />
                                    new AddExpr(<br />
                                        new MonomialExpr(1, 2),<br />
                                        new ConstExpr(2)),<br />
                                    new AddExpr(<br />
                                        new MonomialExpr(1, 1),<br />
                                        new ConstExpr(1)));<br />
            Expression exp4 = new DivExpr(<br />
                                new AddExpr(<br />
                                    exp3,<br />
                                    new ConstExpr(10)),<br />
                                new AddExpr(<br />
                                    new MonomialExpr(1, 2),<br />
                                    new ConstExpr(5)));</p>
<p>            double result2 = exp4.evaluate(2);<br />
            Expression expResult = exp4.derive();</p>
<p>            String s0 = exp4.ExpString();<br />
            System.Console.WriteLine(s0);</p>
<p>            string s = expResult.ExpString();</p>
<p>            System.Console.WriteLine(s);<br />
        }<br />
    }<br />
}<br />

 

–> Xem tiếp phần 3

Advertisements