Toán ✅ (ĐÃ XÁC MINH)

Algorithm – Chuyển biểu thức trung tố sang tiền tố và hậu tố bằng Stack

Các biểu thức đại số được sử dụng hằng ngày đều được biểu diễn dưới dạng trung tố (infix). Cách biểu diễn này rất dễ hiểu với con người vì hầu hết các toán tử (+, -, *, /) đều là toán tử hai ngôi và chúng phân cách giữa hai toán hạng với nhau. Tuy nhiên đối với máy tính, để tính được giá trị của một biểu thức đại số theo dạng này không đơn giản như ta vẫn làm. Để khắc phục điều đó, máy tính cần chuyển cách biểu diễn các biểu thức đại số từ trung tố sang một dạng khác là tiền tố hoặc hậu tố. Trong bài này tôi sẽ giới thiệu kĩ thuật để giúp máy tính thực hiện điều này thông qua ngôn ngữ minh họa C#.

Thế nào là biểu thức tiền tố, trung tố và hậu tố

Trong đoạn giới thiệu trên có lẽ bạn cũng hình dung được thế nào là biểu thức trung tố, hiểu đơn giản tức là toán tử sẽ được đặt giữa hai toán hạng, dĩ nhiên đây phải là toán tử hai ngôi. Vậy dựa vào vị trí của của toán tử, liệu ta có thể biểu diễn biểu thức đại số dưới dạng khác? Câu trả lời là được, và như đã nói, ta có ba cách là biểu thức tiền tố (prefix), trung tố (infix) và hậu tố (postfix). Hãy xem một chút giới thiệu về cách biểu diễn biểu thức tiền tố và hậu tố để hiểu rõ hơn về chúng.

–       Prefix: Biểu thức tiền tố được biểu diễn bằng cách đặt toán tử lên trước các toán hạng. Cách biểu diễn này còn được biết đến với tên gọi “ký pháp Ba Lan” do nhà toán học Ba Lan Jan Łukasiewicz phát minh năm 1920. Với cách biểu diễn này, thay vì viết x+y như dạng trung tố, ta sẽ viết +xy. Tùy theo độ ưu tiên của toán tử mà chúng sẽ được sắp xếp khác nhau, bạn có thể xem một số ví dụ ở phía sau phần giới thiệu này.

–       Postfix: Ngược lại với cách Prefix, tức là các toán tử sẽ được đặt sau các toán hạng. Cách biểu diễn này được gọi là “ký pháp nghịch đảo Ba Lan” hoặc được viết tắt là RPN (Reverse Polish notation), được phát minh vào khoảng giữa thập kỷ 1950 bởi một triết học gia và nhà khoa học máy tính Charles Hamblin người Úc.

Một số ví dụ:

InfixPrefixPostfix
x+y+xyxy+
x+y-z-+xyzxy+z –
x+y*z+x*yzxyz*+
x+(y-z)+x-yzxyz-+

Phương pháp chuyển từ biểu thức trung tố sang tiền tố và hậu tố

Có hai cách để chuyển một biểu thức từ trung tố sang hai loại còn lại đó là dùng :

–       Stack

–       Expression Tree (cây biểu thức)

Việc dùng Stack thông dụng hơn có ưu điểm là dễ thiết lập, đơn thuần còn dùng Expression Tree sẽ giúp việc quy đổi được dễ hiểu và trực quan hơn tuy nhiên lại mất thời hạn thiết lập. Trong bài viết này tôi sẽ chỉ trình diễn kĩ thuật sử dụng Stack, kĩ thuật dùng Expression Tree sẽ được ra mắt trong bài viết sau .
Việc thiết lập những thuật toán quy đổi này bằng C # có một lợi điểm là C # tương hỗ sẵn những collection, ngoài những chúng còn có năng lực truy vấn và lọc tài liệu nếu như bạn dùng C # 3 trở lên. Bên cạnh đó kĩ thuật Regular Expression cũng được sử dụng để làm giảm những câu lệnh so sánh và thao tác chuỗi .

Độ ưu tiên của các toán tử

Một trong những điều quan trọng trước khi khởi đầu là phải thống kê giám sát được độ ưu tiên của những toán tử trong biểu thức nhập vào. Để đơn thuần ta chỉ xét những toán tử hai ngôi và thường dùng gồm có : multiply ( + ), subtract ( – ), multiply ( * ), divide ( / ), Modulo ( % ). Theo đó những toán tử “ *, /, % ” có cùng độ ưu tiên và cao hơn hai toán tử “ +, – ”. Như vậy ta có phương pháp lấy độ ưu tiên toán tử như sau :

public static int GetPriority(string op)
{
    if (op == "*" || op == "/" || op == "%")
        return 2;
    if (op == "+" || op == "-")
        return 1;
    return 0;
}

Định dạng lại biểu thức Infix trước khi chuyển đổi

Các biểu thức Infix khi nhập vào có thể dư thừa các khoảng trắng, các kí tự không phù hợp hoặc viết sai cú pháp. Phần kiểm tra cú pháp bạn có thể làm riêng hoặc để luôn trong các thuật toán chuyển đổi. Trong phần này tôi chỉ trình bày việc định dạng để các phần tử của biểu thức (toán tử, toán hạng) phải được phân cách với nhau bằng một khoảng trắng. Các phần tử này tôi sẽ gọi là một token.

public static void FormatExpression(ref string expression)
{
    expression = expression.Replace(" ", "");
    expression = Regex.Replace(expression, @"\+|\-|\*|\/|\%|\^|\)|\(", delegate(Match match)
    {
        return " " + match.Value + " ";
    });
    expression = expression.Replace("  ", " ");
    expression = expression.Trim();
}

Như bạn thấy tôi tiên phong tôi vô hiệu hết khoảng chừng trắng khỏi chuỗi expression sau đó sử dụng phương pháp Replace của Regular expression để tìm kiếm những toán tử và những dấu ngoặc đơn để thêm khoảng chừng trắng vào hai đầu mỗi kí tự tìm thấy .

Phương thức Replace() tôi sử dụng trên có tham số thứ 3 là một delegate kiểu MatchEvaluator để xử lý các kết quả tìm được trong chuỗi. Cách viết trên tôi sử dụng kĩ thuật anonymous method, bạn có thể dùng lambda expression để viết và sử dụng phương thức Format() của lớp String để mã lệnh ngắn gọn hơn như sau:

expression = Regex.Replace(expression, @"\+|\-|\*|\/|\%|\^|\)|\(", match =>
    String.Format(" {0} ", match.Value)
);

Hai dòng sau dùng để cắt những khoảng chừng trắng nằm sát nhau và những khoảng chừng trắng nằm ở hai đầu chuỗi. Nguyên nhân có những khoảng chừng trắng liền nhau là do trong biểu thức hoàn toàn có thể sẽ Open những toán tử và dấu ngoặc đơn nằm sát nhau .

Các phương thức kiểm tra toán tử và toán hạng

Trong thuật toán quy đổi này ta cần có những phương pháp kiểm tra xem một thành phần của chuỗi có phải là toán tử hoặc toán hạng không. Thay vì sử dụng những cấu trúc if hoặc switch dài dòng và phiền phức khi tăng trưởng, ta sẽ dùng Regex để kiểm tra .

Ngoài ra vì chuỗi nhập vào là một biểu thức đại số, nên các toán hạng ta sẽ xét không chỉ là các chữ số mà còn có chữ cái từ a-z và A-Z.

Có một quy tắc nữa là khi dùng vần âm thì chỉ được cho phép duy nhất một vần âm đại diện thay mặt cho một toán hạng, còn khi dùng chữ số thì hoàn toàn có thể nhiều chữ số ghép thành một toán hạng .

private static bool IsOperator(string str)
{
    return Regex.Match(str, @"\+|\-|\*|\/|\%").Success;
}
public static bool IsOperand(string str)
{
    return Regex.Match(str, @"^\d+$|^([a-z]|[A-Z])$").Success;
}

Chuyển biểu thức Infix sang Postfix

Lý do tôi trình diễn thuật toán chuyển sang postfix trước vì thuật toán này thông dụng và dễ setup hơn, bạn cũng sẽ thấy sự tương đương của thuật toán này với thuật toán chuyển từ infix sang prefix khi tôi trình diễn ở phần sau .
Thuật toán để chuyển một biểu thức Infix sang dạn Prefix :
Đọc từng token trong biểu thức infix từ trái qua phải, với mỗi token ta thực thi những bước sau :

– Nếu là toán hạng : cho ra output .
– Nếu là dấu mở ngoặc “ ( “ : cho vào stack
– Nếu là dấu đóng ngoặc “ ) ” : lấy những toán tử trong stack ra và cho vào output cho đến khi gặp dấu mở ngoặc “ ( “. ( Dấu mở ngoặc cũng phải được đưa ra khỏi stack )
– Nếu là toán tử :

  • Chừng nào ở đỉnh stack là toán tử và toán tử đó có độ ưu tiên lớn hơn hoặc bằng toán tử hiện tại thì lấy toán tử đó ra khỏi stack và cho ra output.
  • Đưa toán tử hiện tại vào stack

Sau khi duyệt hết biểu thức infix, nếu trong stack còn thành phần thì lấy những token trong đó ra và cho lần lượt vào output .

Hãy xem ví dụ sau để hiểu rõ hơn thuật toán này .

Chúng ta sẽ chuyển biểu thức A*B+C*((D-E)+F)/G từ dạng Infix sang dạng Postfix:

TokenStackOutput
A{Empty}A
**A
B*A B
++A B *
C+A B * C
*+ *A B * C
(+ * (A B * C
(+ * ( (A B * C
D+ * ( (A B * C D
+ * ( ( –A B * C D
E+ * ( ( –A B * C D E
)+ * (A B * C D E –
++ * ( +A B * C D E –
F+ * ( +A B * C D E – F
)+ *A B * C D E – F +
/+ /A B * C D E – F + *
G+ /A B * C D E – F + * G
{Empty}A B * C D E – F + * G / +

Dựa theo thuật toán trên, ta setup một phương pháp tương ứng trên C # .

public static string Infix2Postfix(string infix)
{
    FormatExpression(ref infix);

    IEnumerable str = infix.Split(' ');
    Stack stack = new Stack();
    StringBuilder postfix = new StringBuilder();

    foreach (string s in str)
    {
        if (IsOperand(s))
            postfix.Append(s).Append(" ");
        else if (s == "(")
            stack.Push(s);
        else if (s == ")")
        {
            string x = stack.Pop();
            while (x != "(")
            {
                postfix.Append(x).Append(" ");
                x = stack.Pop();
            }
        }
        else// IsOperator(s)
        {
            while (stack.Count > 0 && GetPriority(s) <= GetPriority(stack.Peek()))
                postfix.Append(stack.Pop()).Append(" ");
            stack.Push(s);
        }
    }

    while (stack.Count > 0)
        postfix.Append(stack.Pop()).Append(" ");

    return postfix.ToString();
}

Chuyển biểu thức Infix sang Prefix

Không có nhiều sự độc lạ giữa việc chuyển từ Infix sang Prefix với Infix sang Postfix, hầu hết là sự đổi khác thứ tự duyệt từ phải sang trái thay vì từ trái sang phải. Và thay vì duyệt theo hướng ngược lại như thế bạn hoàn toàn có thể triển khai một quy đổi nhỏ để đảo ngược biểu thức nhập vào .
Chú ý là tôi sử dụng “ đảo ngược biểu thức ” thay vì ” đảo ngược chuỗi ”, việc đảo ngược này phải giữ nguyên được giá trị của những toán hạng, ví dụ bạn không hề đảo ngược 12 thành 21 được. Hơn nữa vì chuỗi đã đảo ngược nên những dấu ngoặc đơn cũng phải được hiểu ngược lại. Cụ thể ta có ví dụ sau :

Chuyển biểu thức Infix A*B+C*((D-E)+F)/G sang dạng Prefix

Đầu tiên ta đảo ngược biểu thức trên thành G/)F+)E-D((*C+B*A, sau đó ta thực hiện các bước trong thuật toán sau:

Đọc từng token trong biểu thức infix từ trái qua phải, với mỗi token ta triển khai những bước sau :
– Nếu là toán hạng : cho ra output .
– Nếu là dấu đóng ngoặc “ ) “ : cho vào stack
– Nếu là dấu mở ngoặc “ ( ” : lấy những toán tử trong stack ra và cho vào output cho đến khi gặp dấu đóng ngoặc “ ) “. ( Dấu đóng ngoặc cũng phải được đưa ra khỏi stack )
– Nếu là toán tử :

  • Chừng nào ở đỉnh stack là toán tử và toán tử đó có độ ưu tiên lớn hơn toán tử hiện tại thì lấy toán tử đó ra khỏi stack và cho ra output.
  • Đưa toán tử hiện tại vào stack

Sau khi duyệt hết biểu thức infix, nếu trong stack còn thành phần thì lấy những token trong đó ra và cho lần lượt vào output. Cuối cùng là đảo ngược biểu thức một lần nữa và ta sẽ thu được hiệu quả .

public static string Infix2Prefix(string infix)
        {
            List prefix = new List();
            Stack stack = new Stack();

            FormatExpression(ref infix);

            IEnumerable enumer = infix.Split(' ').Reverse();

            foreach (string s in enumer)
            {
                if (IsOperand(s))
                    prefix.Add(s);
                else if (s == ")")
                    stack.Push(s);
                else if (s == "(")
                {
                    string x = stack.Pop();
                    while (x != ")")
                    {
                        prefix.Add(x);
                        x = stack.Pop();
                    }
                }
                else// if (IsOperator(s))
                {
                    while (stack.Count > 0 && GetPriority(s) < GetPriority(stack.Peek()))
                        prefix.Add(stack.Pop());
                    stack.Push(s);
                }
            }

            while (stack.Count > 0)
                prefix.Add(stack.Pop());

            StringBuilder str = new StringBuilder();
            for (int i = prefix.Count - 1; i >= 0; i--)
            {
                str.Append(prefix[i]).Append(" ");
            }

            return str.ToString();
   }

Ngoài cách viết lại nguyên một phương pháp quy đổi như trên, ta hoàn toàn có thể sử dụng lại phương pháp Infix2Postfix ( ) để quy đổi sau khi đảo ngược biểu thức infix, đồng thời đảo ngược hai kí tự “ ( “ và “ ) ” cho nhau .

Một số điểm lưu ý

Một số biểu thức prefix và postfix hoàn toàn có thể được tạo ra khác nhau nhưng thực ra giá trị của chúng là bằng nhau và biểu thức infix bắt đầu cũng là tương tự nhau. Nguyên nhân là một biểu thức đại số có nhiều cách để để tính giá trị khi độ ưu tiên của những toán tử là bằng nhau :
Ví dụ bạn hoàn toàn có thể tính x + y-z bằng cách nhóm chúng lại thành

(x+y)-z (1)

hoặc

x+(y-z) (2)

Thông thường tất cả chúng ta ưu tiên cách tính số ( 1 ) từ trái qua .
Điểm tạo nên sự độc lạ là cách tất cả chúng ta so sánh độ ưu tiên của những toán tử, ví dụ thay vì viết dấu “ < ” trong đoạn mã này, ta hoàn toàn có thể sửa thành “ < = ”, giá trị của chúng vẫn không đổi khác :

//…
while (stack.Count > 0 && GetPriority(s) < GetPriority(stack.Peek()))

prefix. Add ( stack. Pop ( ) ) ;
stack. Push ( s ) ;
/ / …

Kiểm tra kết quả

Để kiểm tra tác dụng có đúng chuẩn không, bạn hoàn toàn có thể dùng một dịch vụ quy đổi trực tuyến tại địa chỉ http://scriptasylum.com/tutorials/infix_postfix/infix_postfix.html. Trang web cũng sẽ thực thi giám sát giá trị của biểu thức sau khi quy đổi. Như tác dụng của biểu thức dưới đây là 111 .

infix2postfix_online

Ngoài ra bạn cũng có thể dùng chương trình Y2 Expression Converter Demo của tôi viết để minh họa việc chuyển đổi từ infix sang prefix và postfix.

Y2 Expression Converter Demo 1.0.0

Xem ra mắt và tải Demo + Soucecode tại đây
https://vietlike.vn

Bình chọn

Share this:

Thích bài này:

Thích

Đang tải …

VIETLIKE.VN

CEO: Công ty TNHH Công Nghệ Truyền Thông Ez Media.

Trả lời

Email của bạn sẽ không được hiển thị công khai.

Back to top button