Bài viết sưu tầm

Thuậttoán: Chuyển biểu thức P ở dạng trung tố sang dạng hậu tố kết quả là Q:

Bước1:Khởi gán:  Q = ” ” ;

      Thêm cặp dấu đóng mở () trước P: P= ”(” + P +”)”;

      Khởi tạo ngăn xếp S=rỗng

Bước 2: Xé ttừng phần tử X  thuộc P (từtráisang phải):

                  - Nếu X  là dấu ”(”  thì thêm "(” vào ngăn xếp S: PUSH(S,X);

                  - Nếu X là toán hạng thì thêm vào Q: Q= Q+X;

                  - Nếu X  là dấu đóng ngoặc ”)” thì lấy các phần tử trong ngăn xếp ra và thêm vào Q cho đến khi gặp dấu mở ngoặc ”(”.

                     (Lưuý dấu mở ngoặc ”(” cũng lấy ra khỏi S nhưng không cho vào Q.)

                 - Nếu X là toán tử:

                    + Lấy các toán tử có độ ưu tiên >= X ra khỏi S, thêm vào Q nếu có.

                    + Thêm X vào S.

Bước3:Trảvề Q.