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.

https://yinyangit.wordpress.com