Bài tập chuyển trung tố ssang hậu tố năm 2024

Void trungtosanghau[] { //doc ki tu x cua bt tu trai sang phai if [x = ‘[“] push [‘[‘] If [x = toán hạng] ghi vào kq If [x = toán tử]// giả sử t { If [stack! =rỗng] { while [đưt[t2]>=đưt[t1] {

//t2 ở đỉnh stack Pop[t2]; Ghi t2 vào kq Push [t1] } } If [stack =rỗng || dưt[t2] 3] or not [A > 0]

1. [[A > 0] or [A < 0]] and [B * B - 4 * A * C < 0]

Bài 4: Viết chương trình tính biểu thức logic dạng RPN với các toán tử and, or, not và các toán hạng là TRUE hay FALSE.

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

Thuật toán chuyển đổi biểu thức từ trung tố sang hậu tố:

−

Nếu gặp 1 toán hạng [con số hoặc biến] thì nó ghi vào kết quả[chuỗi kết quả là biểu thức trung tố].

−

Nếu gặp dấu mở ngoặc thì đưa nó vào stack.

−

Nếu gặp 1 toán tử [ví dụ là t1] thì thực hiện 2 bước sau:

o

Nếu stack không rỗng, hoặc còn toán tử t2 ở đỉnhngăn xếp và độ ưu tiên của t1 nhỏ hơn hay bằng độ ưutiên của t2 thì lấy t2 ra khỏi ngăn xếp và ghi vào kết quả.

o

Nếu stack rỗng hoặc toán tử t2 ở đỉnh stack có độưu tiên thấp hơn t1 thì ghi [push] t1 vào ngăn xếp

−

Nếu gặp dấu đóng ngoặc thì cứ lấy các tất cả các toán tửtrong ngăn xếp ra và ghi vào kết quả cho đến khi lấy được dấumở ngoặc ra khỏi ngăn xếp.

−

Khi đã duyệt hết biểu thức trung tố, lần lượt lấy tất cả toánhạng [nếu có] từ ngăn xếp và ghi vào chuỗi kết quả.

Ví dụ:

chuyển đổi biểu thức trung tố sau sang hậu tố:3+4*2/[1-5]Kết quả là: 3 4 2 * 1 5 - / +

Quá trình làm việc của thuật toán như sau:

Ký tựStack Trình tự làm việcKết quả3{Empty}Đầu vào là 1 toánhạng [số] nênchương trình ghivào kết quả3++Do stack rỗng vàtoán tử “+” ở đỉnh stack nên ghitoán tử “+” vàongăn xếp34+Toán hạng tiếptheo nên vẫn đưara kết quả3 4*+ *Toán tử “+” ở đỉnh stack có độưu tiên thấp hơntoán tử “*” nên“*” được ghi vào3 4

1