Algorithm – Tính giá trị của biểu thức tiền tố và hậu tố

Việc tính giá trị của một biểu thức toán học ở dạng trung tố trong máy tính thông thường sẽ được chuyển sang dạng ký pháp nghịch đảo Ba Lan (hậu tố) để việc tính toán được dễ dàng. Bạn có thể xem lại thuật toán chuyển đổi từ trung tố sang hậu tố trong bài viết “Chuyển biểu thức trung tố sang tiền tố và hậu tố bằng Stack” của tôi, và tải project mẫu tại đây. Trong bài viết này, tôi sẽ trình bày phương pháp tính giá trị của một biểu thức tiền tố và hậu tố bằng Stack. Bạn có thể sẽ cần áp dụng kiến thức dưới đây nếu muốn tạo ra một cây biểu thức (expression tree) từ các dạng biểu thức này.

Tính giá trị của biểu thức hậu tố (postfix)

Trong bài trước tôi cũng đã giới thiệu việc máy tính tính toán biểu thức hậu tố rất đơn giản cho nên chúng ta mới cần chuyển từ trung tố sang hậu tố. Có thể mô tả cách tính toán này chỉ bằng một chuỗi thao tác đơn giản lặp lại cho đến khi chỉ còn một toán hạng kết quả.

Quy tắc tính như sau:

Lặp qua các token của của biểu thức postfix từ trái qua phải:

-       Nếu là toán hạng: push vào stack

-       Nếu là toán tử: pop hai toán hạng trong stack ra và tính giá trị của chúng dựa vào toán tử này. Push kết quả đó lại vào stack.

Phần tử còn sót lại trong stack sau vòng lặp chính là kết quả của biểu thức.

Ví dụ biểu thức trung tố 6*3-1 có kết quả là 17, chuyển sang hậu tố ta được:

6 3 * 1 -

Lặp từ trái qua phải của biểu thức

-       6:         push vào Stack

-       3:         push vào Stack

-       *:          pop 6 và 3 ra rồi tính 6*3=18, push 18 vào Stack

-       1:         push 1 vào Stack

-       -:          pop 18 và 1 ra rồi tính 18-1=17, push 17 vào Stack

Như vậy ta đã tính xong giá trị của biểu thức trên. Phiên bản cài đặt thuật toán bằng C# như sau:

public static float EvaluatePostfix(string postfix)
{
    Stack<float> stack = new Stack<float>();
    postfix = postfix.Trim();

    IEnumerable<string> enumer = postfix.Split(' ');

    foreach (string s in enumer)
    {
        if (IsOperand(s))
            stack.Push(float.Parse(s));
        else
        {
            float x = stack.Pop();
            float y = stack.Pop();

            switch (s)
            {
                case "+": y += x; break;
                case "-": y -= x; break;
                case "*": y *= x; break;
                case "/": y /= x; break;
                case "%": y %= x; break;
            }
            stack.Push(y);
        }
    }
    return stack.Pop();
}

Tính giá trị biểu thức tiền tố

Tương tự như với cách làm trên nhưng với chiều ngược lại. Vì biểu thức không chứa dấu ngoặc đơn nên việc cài đặt thuật toán này gần như giống với thuật toán áp dụng cho biểu thức hậu tố.

public static float EvaluatePrefix(string prefix)
{
    Stack<float> stack = new Stack<float>();
    prefix = prefix.Trim();

    IEnumerable<string> enumer = prefix.Split(' ').Reverse();

    foreach (string s in enumer)
    {
        if (IsOperand(s))
            stack.Push(float.Parse(s));
        else
        {
            float y = stack.Pop();
            float x = stack.Pop();

            switch (s)
            {
                case "+": y += x; break;
                case "-": y -= x; break;
                case "*": y *= x; break;
                case "/": y /= x; break;
                case "%": y %= x; break;
            }
            stack.Push(y);
        }
    }
    return stack.Pop();
}

Bạn hãy chú ý đến thứ tự của các toán hạng được pop ra khỏi stack vì các phép tính %, / và – yêu cầu phải đúng thứ tự các toán hạng.

http://yinyangit.wordpress.com


About these ads

20 thoughts on “Algorithm – Tính giá trị của biểu thức tiền tố và hậu tố

  1. Lúc viết chương trình demo Y2 Expression Converter tôi chỉ có một mục đích là minh họa cho việc chuyển đổi các dạng biểu thức. Bạn có thể sử dụng hai thuật toán mà tôi cung cấp trên để bổ sung chức năng tính giá trị vào chương trình nếu muốn.
    Thân!

    Trả lời
  2. anh có thể viết 1 chương trình tính toán cơ bản bằng cách nhập biểu thức vào textfield rồi cho ra kết quả làm mẫu không ?
    ngoài ra có vẻ thuật toán này thiếu trường hợp dấu ngoặc và độ ưu tiên của toán tử :D

    Trả lời
  3. Mã nguồn đã có sẵn nếu bạn muốn tạo thì chỉ vẽ control rồi thêm các đoạn mã cần thiết vào thôi. Trên đây là thuật toán để tính giá trị của biểu thức ở dạng prefix và postfix nên tất nhiên biểu thức sẽ không còn các dấu ngoặc đơn.

    Trả lời
  4. ồ, xin lỗi :D do đọc tiêu đề không kĩ. nhầm rằng bài viết này hướng dẫn chuyển đổi kiêm tính toán.
    Cho mình hỏi thêm dòng này trong java tương ứng sẽ thế nào :)
    IEnumerable str = infix.Split(‘ ‘);

    Cảm ơn!
    Các bài viết rất hay, rất cụ thể

    Trả lời
  5. Bài viết rất hay, chi tiết, cảm ơn anh nhiều!
    Hôm vừa rồi thầy cho bài tập nội dung như trên nhưng viết bằng C, sau mấy ngày ngấu nghiến thuật toán và code của anh = C# mới viết được cái chương trình nho nhỏ (console) =.=. Đây là mã nguồn mình viết http://www.mediafire.com/?qsgzp29z0p2zyg5 vẫn còn chưa khắc phục được lỗi chia cho 0, toán tử –, ^. Anh có thể hướng dẫn viết 1 chương trình nhỏ nhỏ tương tự như calc của windows dùng VC++ được không a? Thanks!

    Trả lời
  6. các ví dụ về calc trên mạng có khá nhiều, hơn nữa mình cũng đang trong thời gian bận và VC++ thì không thuộc chuyên môn chính. Bạn có thể thấy hầu hết chương trình mình viết đều bằng C# để tiết kiệm thời gian.
    Chúc bạn học tốt!

    Trả lời
  7. Em mới học C#, đã hiểu về việc chuyển đổi bằng ký pháp balan, nhưng ko biết gì về stack, mà đọc demo của anh em ko hiểu cách dùng nó (có thể anh dùng trên form nên hơi rối, em chỉ mới tìm hiểu đến console thôi).

    Anh YinYang có thể demo giúp em cái này trên console đc ko ạh, nó sẽ hiển thị nhập chuỗi biểu thức, mình nhập xong nó xuất kết quả trên console luôn. Em chỉ cần anh code giúp em 4 phép + – * / thôi. Anh có thể gửi qua email của em: symaci@yahoo.com.vn hoặc up lên mediafire cũng đc ạh, cảm ơn anh nhiều lắm !!

    Trả lời
    • Dùng Windows Form chỉ để minh họa các bước chuyển đổi trực quan hơn cho dễ hiểu. Các phương thức mình viết không phụ thuộc vào Form hay Console. Bạn chỉ cần copy ra và gọi bình thường.
      Thân!

      Trả lời
      • cảm ơn anh, em đã gọi đc các phương thức của anh rồi, cho em hỏi thêm là anh có viết bài nào về cách dùng stack ko ạ, nếu có thì cho em xin link để nghiên cứu cho dễ ^^

  8. Pingback: Algorithm – Tạo và sử dụng cây biểu thức (expression tree) « Nguyễn Ngọc Vạn's Blog

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s