Chuyển một bài toán từ trung tố sang tiền tố năm 2024

1. Khái niệm

Một phép toán hai ngôi trên tập hợp X là một ánh xạ f: X×X → X cho (a,b) → f(a,b) thuộc A. Ánh xạ f khi đó thường được ký hiệu bởi *, được gọi là toán tử, các phần tử a, b được gọi là các hạng tử (còn gọi là toán hạng). Khi viết biểu thức biểu diễn phép toán đó ta có thể đặt ký hiệu toán tử ở trước (ký pháp tiền tố), sau (ký pháp hậu tố) hoặc giữa (ký pháp trung tố) các toán hạng. Thông thường trong các biểu thức đại số và số học, ta viết ký hiệu phép toán giữa hai hạng tử, đó là ký pháp trung tố. Ví dụ: a + b, a * b,... Khi một biểu thức có nhiều phép toán, ta dùng các cặp dấu ngoặc "(", ")" và thứ tự ưu tiên các phép toán để chỉ rõ thứ tự thực hiện các phép toán. (Các phép toán đều quy về phép toán 2 ngôi.) Ta cũng có thể viết hai hạng tử trước và kí hiệu toán tử sau. Chẳng hạn: a + b viết là a b +, a * b viết là a b * Cũng có thể viết toán tử trước, hai toán hạng sau. Chẳng hạn: a + b viết là + a b, a * b viết là * a b Về lý thuyết, ký pháp tiền tố và ký pháp hậu tố còn có thể được mở rộng cho các phép toán ba ngôi hoặc nhiều hơn mà vẫn không phải dùng tới dấu ngoặc để thể hiện độ ưu tiên các phép toán, tương tự với hàm số đa biến, còn ký pháp trung tố thì không thể. Tuy nhiên, trong thực tế không có nhiều phép toán đa ngôi và ký pháp trung tố vẫn được dùng rộng rãi vì thói quen. Ví dụ: + a b c có thể được hiểu là tổng của 3 số a, b và c trong ký pháp tiền tố. Tương tự, f a b c có thể được hiểu là hàm f của 3 biến a, b và c trong ký pháp tiền tố. Tóm lại: - Tiền tố: Viết toán tử trước toán hạng - Hậu tố: Viết toán tử sau toán hạng - Trung tố: Viết toán tử giữa hai toán hạng. Chú ý: Với cách biểu diễn dạng trung tố, ta có các trường hợp sau: - Trung tố đầy đủ dấu ngoặc: Tất cả toán tử và toán hạng đều ở dạng 2 ngôi và đặt trong một cặp dấu ngoặc. - Trung tố không đầy đủ dấu ngoặc: Chỉ có một số cặp toán hạng và toán tử là có dấu ngoặc. - Trung tố không có dấu ngoặc: Biểu thức không chứa bất kỳ dấu ngoặc nào. Để tính biểu thức của hai dạng trung tố ở sau ta cần xét đến tính ưu tiên của toán tử. Nguyên tắc ưu tiên là *, /, % ưu tiên hơn + và -.

1. Bài toán Chuyển biểu thức M = M1M2M3...Mn từ dạng trung tố đầy đủ dấu ngoặc sang hậu tố (N).

2. Nhận xét - Vì M ở dạng trung tố đầy đủ dấu ngoặc nên chắc chắn mọi toán tử hai ngôi đều nằm trong một cặp dấu ngoặc. - Ta sẽ phải thực hiện phép toán khi gặp dấu ngoặc đóng đầu tiên.

3. Ý tưởng Duyệt từ M từ trái qua phải: - Nếu gặp toán hạng thì đưa toán hạng đó vào biểu thức đích N. - Nếu gặp toán tử thì đưa vào một ngăn xếp (stack) S nào đó đã khởi tạo từ trước. - Gặp dấu ngoặc mở ("(") thì bỏ qua, gặp dấu ngoặc đóng (")") thì lấy toán tử từ đỉnh của S đưa vào biểu thức đích N.

4. Giải thuật

Code:`Input: M: Biểu thức trung tố đầy đủ dấu ngoặc.

1. Khởi tạo stack S = {}; // Stack S rỗng.
2. Khởi tạo biểu thức đích N = ""; // N chưa có phần tử nào.
3. for i:=1 to |M| do
4. if (Mi là Toán hạng) then N:=N+Mi; // Đưa Mi vào N
5. if (Mi là Toán tử) then PUSH(Mi,S); // Đưa Mi vào ngăn xếp S
6. if (Mi là ")" ) then POP(S,a); // Lấy giá trị trên đỉnh của S đưa vào a N:=N+a; // Thêm a vào N Output: N: Biểu thức hậu tố.`

5. Ví dụ

Code:` Input: M = (10-(3*((14-2)/(2+4)))) sang hậu tố (ở đây M có số phần tử là n=21)

• Khởi tạo: S={}; N="";
• M1 = "(", bỏ qua
• M2 = "10", S={}; N="10";
• M3 = "-", S={-}; N="10";
• M4 = "(", S={-}; N="10";
• M5 = "3", S={-}; N="10, 3";
• M6 = "", S={-, }; N="10, 3";
• M7 = "(", S={-, *}; N="10, 3";
• M8 = "(", S={-, *}; N="10, 3";
• M9 = "14", S={-, *}; N="10, 3, 14";
• M10 = "-", S={-, *, -}; N="10, 3, 14";
• M11 = "2", S={-, *, -}; N="10, 3, 14, 2";
• M12 = ")", S={-, *}; N="10, 3, 14, 2, -";
• M13 = "/", S={-, *, /}; N="10, 3, 14, 2, -";
• M14 = "(", S={-, *, /}; N="10, 3, 14, 2, -";
• M15 = "2", S={-, *, /}; N="10, 3, 14, 2, -, 2";
• M16 = "+", S={-, *, /, +}; N="10, 3, 14, 2, -, 2";
• M17 = "4", S={-, *, /, +}; N="10, 3, 14, 2, -, 2, 4";
• M18 = ")", S={-, *, /}; N="10, 3, 14, 2, -, 2, 4, +";
• M19 = ")", S={-, *}; N="10, 3, 14, 2, -, 2, 4, +, /";
• M20 = ")", S={-}; N="10, 3, 14, 2, -, 2, 4, +, /, *";
• M21 = ")", S={}; N="10, 3, 14, 2, -, 2, 4, +, /, , -"; Output: N = 10 3 14 2 - 2 4 + / - `

1. Bài toán Chuyển biểu thức M = M1M2M3...Mn từ dạng trung tố không đầy đủ dấu ngoặc sang hậu tố (N).

2. Nhận xét - Vì M ở dạng trung tố không đầy đủ dấu ngoặc nên khi gặp toán tử ta cần xét đến độ ưu tiên của toán tử.

3. Ý tưởng Duyệt từ M từ trái qua phải: - Nếu gặp toán hạng thì đưa toán hạng đó vào biểu thức đích N. - Nếu gặp dấu ngoặc mở ("(") thì đưa vào một ngăn xếp (stack) S nào đó đã khởi tạo từ trước. - Nếu gặp dấu ngoặc đóng (")") thì lần lượt lấy các toán tử từ đỉnh của S đưa vào biểu thức đích N cho đến khi gặp dấu ngoặc đóng (")") đầu tiên, loại bỏ luôn dấu ngoặc đóng đó ra khỏi stack. - Nếu gặp toán tử có độ ưu tiên cao hơn toán tử hiện có trên đỉnh stack thì đưa nó vào stack. - Nếu gặp toán tử có độ ưu tiên thấp hơn hoặc bằng toán tử hiện tại trên đinh stack thì lấy toán tử trên đỉnh stack ra đưa vào biểu thức đích N, đồng thời đưa toán tử đó vào đỉnh stack. - Khi xét hết các phần tử của biểu thức M, lần lượt lấy các toán tử có trong stack ra biểu thức đích N.

4. Giải thuật

Code:` Input: M: Biểu thức trung tố không đầy đủ dấu ngoặc.

int UT(x){ // x là một phần tử của M if ((x="*") OR (x="/") OR (x="%")) ruturn 2; if ((x="+") OR (x="-")) ruturn 1; }

1. Khởi tạo stack S = {}; // Stack S rỗng.
2. Khởi tạo biểu thức đích N = ""; // N chưa có phần tử nào.
3. for i:=1 to |M| do
4. if (Mi là Toán hạng) N:=N+Mi; // Đưa Mi vào N
5. if (Mi là Toán tử) if UT(Top(S)>=UT(Mi){ Pop(S,x); N:=N+x; Push(Mi,S); }
6. if (Mi là ")" ){ x=""; while(x<>"("){ N:=N+x; // Thêm x vào N POP(S,x); // Lấy giá trị trên đỉnh của S đưa vào x } }
7. while !IsEmpty(S){ Pop(S,x); if x<>"(" N:=N+x; } Output: N: Biểu thức hậu tố.

`

5. Ví dụ

Code:` Input: M = 10-3*(14-2)/(2+4) sang hậu tố (ở đây M có số phần tử là n=15)

• Khởi tạo: S={}; N="";
• M1 = "10", S={}; N="10";
• M2 = "-", S={-}; N="10";
• M3 = "3", S={-}; N="10, 3";
• M4 = "", S={-, }; N="10, 3";
• M5 = "(", S={-, *, (}; N="10, 3";
• M6 = "14", S={-, *, (}; N="10, 3, 14";
• M7 = "-", S={-, *, (, -}; N="10, 3, 14";
• M8 = "2", S={-, *, (, -}; N="10, 3, 14, 2";
• M9 = ")", S={-, *}; N="10, 3, 14, 2, -";
• M10 = "/", S={-, /}; N="10, 3, 14, 2, -, *";
• M11 = "(", S={-, /, (}; N="10, 3, 14, 2, -, *";
• M12 = "2", S={-, /, (}; N="10, 3, 14, 2, -, *, 2";
• M13 = "+", S={-, /, (, +}; N="10, 3, 14, 2, -, *, 2";
• M14 = "4", S={-, /, (, +}; N="10, 3, 14, 2, -, *, 2, 4";
• M15 = ")", S={-, /}; N="10, 3, 14, 2, -, *, 2, 4, +";
• M16 = "", S={}; N="10, 3, 14, 2, -, *, 2, 4, +, /, -";

Output: N = 10 3 14 2 - * 2 4 + / -

`

1. Bài toán Chuyển biểu thức M = M1M2M3...Mn từ dạng trung tố không có dấu ngoặc sang hậu tố (N).

2. Nhận xét - Đây là trường hợp riêng của trường hợp M không đầy đủ dấu ngoặc (trong quá trình xét không gặp dấu ngoặc nào), ta vẫn cần xét đến độ ưu tiên của toán tử.

3. Ý tưởng Duyệt từ M từ trái qua phải: - Nếu gặp toán hạng thì đưa toán hạng đó vào biểu thức đích N. - Nếu gặp toán tử có độ ưu tiên cao hơn toán tử hiện có trên đỉnh stack thì đưa nó vào stack. - Nếu gặp toán tử có độ ưu tiên thấp hơn hoặc bằng toán tử hiện tại trên đinh stack thì lấy toán tử trên đỉnh stack ra đưa vào biểu thức đích N, đồng thời đưa toán tử đó vào đỉnh stack. - Khi xét hết các phần tử của biểu thức M, lần lượt lấy các toán tử có trong stack ra biểu thức đích N.

4. Giải thuật

Code:` Input: M: Biểu thức trung tố có dấu ngoặc.

int UT(x){ // x là một phần tử của M if ((x="*") OR (x="/") OR (x="%")) ruturn 2; if ((x="+") OR (x="-")) ruturn 1; }

1. Khởi tạo stack S = {}; // Stack S rỗng.
2. Khởi tạo biểu thức đích N = ""; // N chưa có phần tử nào.
3. for i:=1 to |M| do
4. if (Mi là Toán hạng) N:=N+Mi; // Đưa Mi vào N
5. if (Mi là Toán tử) if UT(Top(S)>=UT(Mi){ Pop(S,x); N:=N+x; Push(Mi,S); }
6. while !IsEmpty(S){ Pop(S,x); N:=N+x; } Output: N: Biểu thức hậu tố.

`

5. Ví dụ

Code:` Input: M = 10-3*14-2/2+4 sang hậu tố (ở đây M có số phần tử là n=11)

• Khởi tạo: S={}; N="";
• M1 = "10", S={}; N="10";
• M2 = "-", S={-}; N="10";
• M3 = "3", S={-}; N="10, 3";
• M4 = "", S={-, }; N="10, 3";
• M5 = "14", S={-, *}; N="10, 3, 14";
• M6 = "-", S={-, -}; N="10, 3, 14, *";
• M7 = "2", S={-, -}; N="10, 3, 14, *, 2";
• M8 = "/", S={-, -, /}; N="10, 3, 14, *, 2";
• M9 = "2", S={-, -, /}; N="10, 3, 14, *, 2, 2";
• M10 = "+", S={-, -, +}; N="10, 3, 14, *, 2, 2, /";
• M11 = "4", S={-, -, +}; N="10, 3, 14, *, 2, 2, /, 4";
• M12 = "", S={}; N="10, 3, 14, *, 2, 2, /, 4, +, -, -";

Output: N = 10 3 14 * 2 2 / 4 + - -

`

1. Bài toán Tính giá trị biểu thức M = M1M2M3...Mn ở dạng trung tố đầy đủ dấu ngoặc.

2. Nhận xét - Ta nên sử dụng một stack để lưu trữ các kết quả tính toán trung gian.

3. Ý tưởng Duyệt từ M từ trái qua phải: - Nếu gặp dấu ngoặc mở ("(") thì bỏ qua. - Nếu gặp toán hạng hoặc toán tử thì đưa chúng vào stack. - Nếu gặp dấu ngoặc đóng (")") thì lấy 3 phần tử trên đỉnh stack (gồm 2 toán hạng và một toán tử) rồi thực hiện phép toán, kết quả lại cất vào đỉnh stack. - Khi xét hết M, giá trị cuối cùng trên đỉnh stack chính là kết quả tính toán biểu thức M.

4. Giải thuật

Code:` Input: M: Biểu thức trung tố đầy đủ dấu ngoặc.

1. Khởi tạo stack S = {}; // Stack S rỗng.
2. for (i=1;i<=|M|;i++){
3. if (Mi là Toán hạng hoặc Toán tử) Push(Mi,S); // Đưa Mi vào S.
4. if (Mi =")"){ Pop(S,a); // a phải là một toán hạng do M ở dạng đầy đủ dấu ngoặc. Pop(S,x); // x phải là một toán tử do M ở dạng đầy đủ dấu ngoặc. Pop(S,b); // b phải là một toán hạng do M ở dạng đầy đủ dấu ngoặc. Push((bxa),S); // Tính giá trị bxa, kết quả lại đưa vào S. } }
5. Pop(S,Result); Output: Result.

`

5. Ví dụ

Code:` Câu I, Đề thi tuyển sinh cao học năm 2013 Input: M = (10-(3*((14-2)/(2+4))))

• Khởi tạo: S={};
• M1="(" Bỏ qua S={}
• M2="10" Đưa 10 vào S S={10}
• M3="-" Đưa - vào S S={10, -}
• M4="(" Bỏ qua S={10, -}
• M5="3" Đưa 3 vào S S={10, -, 3}
• M6="" Đưa vào S S={10, -, 3, *}
• M6="(" Bỏ qua S={10, -, 3, *}
• M7="(" Bỏ qua S={10, -, 3, *}
• M8="14" Đưa 14 vào S S={10, -, 3, *, 14}
• M9="-" Đưa - vào S S={10, -, 3, *, 14, -}
• M10="2" Đưa 2 vào S S={10, -, 3, *, 14, -, 2}
• M11=")" Tính 14-2=12 rồi vào S S={10, -, 3, *, 12}
• M12="/" Đưa / vào S S={10, -, 3, *, 12, /}
• M13="(" Bỏ qua S={10, -, 3, *, 12, /}
• M14="2" Đưa 2 vào S S={10, -, 3, *, 12, /, 2}
• M15="+" Đưa + vào S S={10, -, 3, *, 12, /, 2, +}
• M16="4" Đưa 4 vào S S={10, -, 3, *, 12, /, 2, +, 4}
• M17=")" Tính 2+4=6 rồi vào S S={10, -, 3, *, 12, /, 6}
• M18=")" Tính 12/6=2 rồi vào S S={10, -, 3, *, 2}
• M19=")" Tính 3*2=6 rồi vào S S={10, -, 6}
• M20=")" Tính 10-6=4 rồi vào S S={4}
• M21="" Kết thúc việc tính toán S={4}

Output: Result=4

`

1. Bài toán Tính giá trị biểu thức M = M1M2M3...Mn ở dạng trung tố không đầy đủ dấu ngoặc.

2. Nhận xét - Ta nên sử dụng hai stack để lưu trữ các kết quả tính toán trung gian. Stack Sh lưu trữ các toán hạng, stack St lưu trữ các toán tử và dấu ngoặc mở. - Vì biểu thức M ở dạng Trung tố không đầy đủ dấu ngoặc nên ta cần xét đến độ ưu tiên của các toán tử.

3. Ý tưởng Giả sử M được cho ở dạng đúng (nghĩa là dấu ngoặc phải đi với nhau từng đôi một, các phần tử chỉ gồm toán tử, toán hạng hoặc dấu ngoặc). Khởi tạo 2 stack: Sh và St. Duyệt từ M từ trái qua phải: - Nếu gặp dấu ngoặc mở ("(") thì đưa vào St. - Nếu gặp toán hạng thì đưa vào Sh. - Nếu gặp toán tử có độ ưu tiên cao hơn toán tử hiện có trên đỉnh St thì đưa nó vào St. - Nếu gặp toán tử có độ ưu tiên thấp hơn hoặc bằng toán tử hiện có trên đỉnh St thì lấy toán tử trên đỉnh St cùng hai toán hạng trên đỉnh Sh, thực hiện phép toán rồi cất kết quả vào Sh. - Nếu gặp dấu ngoặc đóng (")") thì lấy toán tử trên đỉnh St cùng 2 toán hạng trên đỉnh Sh, thực hiện phép toán, kết quả cất vào Sh. Cứ thực hiện như vậy cho đến khi gặp dấu ngoặc mở đầu tiên trên St, loại bỏ luôn dấu ngoặc mở này ra khỏi St. - Khi xét hết M, lần lượt lấy một toán tử trên St và 2 toán hạng trên Sh, thực hiện phép toán, kết quả cất vào Sh cho đến khi Sh chỉ còn một phần tử (hay đến khi St rỗng).

4. Giải thuật

Code:` Input: M: Biểu thức trung tố không đầy đủ dấu ngoặc.

int UT(x){ // x là một phần tử của M if x thuộc {*, /, %} return 2; if x thuộc {+, -} return 1; if x = "(" return 0 }

1. Khởi tạo stack Sh = St = {}; // Stack Sh, St rỗng.
2. for (i=1;i<=|M|;i++){
3. if (Mi là Toán hạng) Push(Mi,Sh); // Đưa Mi vào Sh.
4. if (Mi="(") Push(Mi,St); // Đưa Mi vào St.
5. if (Mi là Toán tử){ while ((St<>{}) AND (UT(Mi)<=UT(Top(St))){ Pop(Sh,a); // a là một toán hạng lấy từ Sh. Pop(St,x); // x là một toán tử lấy từ St. Pop(Sh,b); // b là một toán hạng lấy từ Sh. Push((bxa),Sh); // Tính giá trị bxa, kết quả lại đưa vào Sh. } Push(Mi,St) // Cất toán tử đang xét vào St. }
6. if (Mi=")"){ while (Top(St)<>"("){ Pop(Sh,a); // a là một toán hạng lấy từ Sh. Pop(St,x); // x là một toán tử lấy từ St. Pop(Sh,b); // b là một toán hạng lấy từ Sh. Push((bxa),Sh); // Tính giá trị bxa, kết quả lại đưa vào Sh. } Pop(St,a); // Loại bỏ luôn dấu ngoặc mở gặp phải đầu tiên. }
7. while (St<>{}){ //Thực hiện chừng nào St rỗng, khi đó Sh chắc chắn chỉ còn một phần tử. Pop(Sh,a); // a là một toán hạng lấy từ Sh. Pop(St,x); // x là một toán tử lấy từ St. Pop(Sh,b); // b là một toán hạng lấy từ Sh. Push((bxa),Sh); // Tính giá trị bxa, kết quả lại đưa vào Sh. }
8. Pop(Sh,Result); // Lấy phần tử cuối cùng của Sh ra kết quả. Output: Result.

`

5. Ví dụ

Code:` Input: M = 10-3*(14-2)/(2+4)

• Khởi tạo: Sh={};St={};
• M1="10" Đưa 10 vào Sh Sh={10} St={}
• M2="-" Đưa - vào St Sh={10} St={-}
• M3="3" Đưa 3 vào Sh Sh={10, 3} St={-}
• M4="" Đưa vào St Sh={10, 3} St={-, *}
• M5="(" Đưa ( vào St Sh={10, 3} St={-, *, (}
• M6="14" Đưa 14 vào Sh Sh={10, 3, 14} St={-, *, (}
• M7="-" Đưa - vào St Sh={10, 3, 14} St={-, *, (, -}
• M8="2" Đưa 2 vào Sh Sh={10, 3, 14, 2} St={-, *, (, -}
• M9=")" Tính 14-2=12 rồi vào Sh, loại bỏ luôn ( ở St Sh={10, 3, 12} St={-, *}
• M10="/" Tính 3*12=36 rồi đưa vào Sh, đưa / vào St Sh={10, 36} St={-, /}
• M11="(" Đưa ( vào St Sh={10, 36} St={-, /, (}
• M12="2" Đưa 2 vào Sh Sh={10, 36, 2} St={-, /, (}
• M13="+" Đưa + vào St Sh={10, 36, 2} St={-, /, (, +}
• M14="4" Đưa 4 vào Sh Sh={10, 36, 2, 4} St={-, /, (, +}
• M15=")" Tính 2+4=6 rồi vào Sh, loại bỏ luôn ( ở St Sh={10, 36, 6} St={-, /}
• Top(St)="/" Tính 36/6=6 rồi đưa vào Sh Sh={10, 6} St={-}
• Top(St)="-" Tính 10-6=4 rồi đưa vào Sh Sh={4} St={}
• Top(St)="" Dừng

Output: Result=Top(Sh) = 4

`

1. Bài toán Tính giá trị biểu thức M = M1M2M3...Mn ở dạng trung tố không có dấu ngoặc.

2. Nhận xét - Có thể sử dụng luôn thủ tục tính toán biểu thức ở dạng Trung tố không đầy đủ dấu ngoặc để thực hiện vì đây chỉ là trường hợp đặc biệt của trường hợp không đầy đủ dấu ngoặc. - Ta vẫn nên sử dụng hai stack để lưu trữ các kết quả tính toán trung gian. Stack Sh lưu trữ các toán hạng, stack St lưu trữ các toán tử. - Vì biểu thức M ở dạng Trung tố có không dấu ngoặc nên ta cần xét đến độ ưu tiên của các toán tử.

3. Ý tưởng Giả sử M được cho ở dạng đúng (nghĩa là các phần tử chỉ gồm toán tử và toán hạng ). Khởi tạo 2 stack: Sh và St. Duyệt từ M từ trái qua phải: - Nếu gặp toán hạng thì đưa vào Sh. - Nếu gặp toán tử có độ ưu tiên cao hơn toán tử hiện có trên đỉnh St thì đưa nó vào St. - Nếu gặp toán tử có độ ưu tiên thấp hơn hoặc bằng toán tử hiện có trên đỉnh St thì lấy toán tử trên đỉnh St cùng hai toán hạng trên đỉnh Sh, thực hiện phép toán rồi cất kết quả vào Sh. Đưa toán tử đang xét vào St. - Khi xét hết M, lần lượt lấy một toán tử trên St và 2 toán hạng trên Sh, thực hiện phép toán, kết quả cất vào Sh cho đến khi Sh chỉ còn một phần tử (hay đến khi St rỗng).

4. Giải thuật

Code:` Input: M = (10-(3*((14-2)/(2+4)))) sang hậu tố (ở đây M có số phần tử là n=21)

• Khởi tạo: S={}; N="";
• M1 = "(", bỏ qua
• M2 = "10", S={}; N="10";
• M3 = "-", S={-}; N="10";
• M4 = "(", S={-}; N="10";
• M5 = "3", S={-}; N="10, 3";
• M6 = "", S={-, }; N="10, 3";
• M7 = "(", S={-, *}; N="10, 3";
• M8 = "(", S={-, *}; N="10, 3";
• M9 = "14", S={-, *}; N="10, 3, 14";
• M10 = "-", S={-, *, -}; N="10, 3, 14";
• M11 = "2", S={-, *, -}; N="10, 3, 14, 2";
• M12 = ")", S={-, *}; N="10, 3, 14, 2, -";
• M13 = "/", S={-, *, /}; N="10, 3, 14, 2, -";
• M14 = "(", S={-, *, /}; N="10, 3, 14, 2, -";
• M15 = "2", S={-, *, /}; N="10, 3, 14, 2, -, 2";
• M16 = "+", S={-, *, /, +}; N="10, 3, 14, 2, -, 2";
• M17 = "4", S={-, *, /, +}; N="10, 3, 14, 2, -, 2, 4";
• M18 = ")", S={-, *, /}; N="10, 3, 14, 2, -, 2, 4, +";
• M19 = ")", S={-, *}; N="10, 3, 14, 2, -, 2, 4, +, /";
• M20 = ")", S={-}; N="10, 3, 14, 2, -, 2, 4, +, /, *";
• M21 = ")", S={}; N="10, 3, 14, 2, -, 2, 4, +, /, , -"; Output: N = 10 3 14 2 - 2 4 + / - `0

5. Ví dụ

Code:` Input: M = (10-(3*((14-2)/(2+4)))) sang hậu tố (ở đây M có số phần tử là n=21)

• Khởi tạo: S={}; N="";
• M1 = "(", bỏ qua
• M2 = "10", S={}; N="10";
• M3 = "-", S={-}; N="10";
• M4 = "(", S={-}; N="10";
• M5 = "3", S={-}; N="10, 3";
• M6 = "", S={-, }; N="10, 3";
• M7 = "(", S={-, *}; N="10, 3";
• M8 = "(", S={-, *}; N="10, 3";
• M9 = "14", S={-, *}; N="10, 3, 14";
• M10 = "-", S={-, *, -}; N="10, 3, 14";
• M11 = "2", S={-, *, -}; N="10, 3, 14, 2";
• M12 = ")", S={-, *}; N="10, 3, 14, 2, -";
• M13 = "/", S={-, *, /}; N="10, 3, 14, 2, -";
• M14 = "(", S={-, *, /}; N="10, 3, 14, 2, -";
• M15 = "2", S={-, *, /}; N="10, 3, 14, 2, -, 2";
• M16 = "+", S={-, *, /, +}; N="10, 3, 14, 2, -, 2";
• M17 = "4", S={-, *, /, +}; N="10, 3, 14, 2, -, 2, 4";
• M18 = ")", S={-, *, /}; N="10, 3, 14, 2, -, 2, 4, +";
• M19 = ")", S={-, *}; N="10, 3, 14, 2, -, 2, 4, +, /";
• M20 = ")", S={-}; N="10, 3, 14, 2, -, 2, 4, +, /, *";
• M21 = ")", S={}; N="10, 3, 14, 2, -, 2, 4, +, /, , -"; Output: N = 10 3 14 2 - 2 4 + / - `1

1. Bài toán Tính giá trị biểu thức M = M1M2M3...Mn ở dạng hậu tố.

2. Nhận xét - Do M ở dạng hậu tố nên ta không cần quan tâm đến độ ưu tiên của các toán tử. - Ta vẫn dùng 1 ngăn xếp để lưu kết quả trính toán trung gian.

3. Ý tưởng Giả sử M được cho ở dạng đúng (nghĩa là các phần tử chỉ gồm toán tử và toán hạng). Khởi tạo stack: S. Duyệt từ M từ trái qua phải: - Nếu gặp toán hạng thì đưa vào ngăn xếp S. - Nếu gặp toán tử thì lấy hai phần tử trên đỉnh ngăn xếp, thực hiện phép toán rồi đưa kết quả trở lại ngăn xếp. - Thực hiện cho đến khi vét cạn hết tất cả phần tử của M.

4. Giải thuật

Code:` Input: M = (10-(3*((14-2)/(2+4)))) sang hậu tố (ở đây M có số phần tử là n=21)

• Khởi tạo: S={}; N="";
• M1 = "(", bỏ qua
• M2 = "10", S={}; N="10";
• M3 = "-", S={-}; N="10";
• M4 = "(", S={-}; N="10";
• M5 = "3", S={-}; N="10, 3";
• M6 = "", S={-, }; N="10, 3";
• M7 = "(", S={-, *}; N="10, 3";
• M8 = "(", S={-, *}; N="10, 3";
• M9 = "14", S={-, *}; N="10, 3, 14";
• M10 = "-", S={-, *, -}; N="10, 3, 14";
• M11 = "2", S={-, *, -}; N="10, 3, 14, 2";
• M12 = ")", S={-, *}; N="10, 3, 14, 2, -";
• M13 = "/", S={-, *, /}; N="10, 3, 14, 2, -";
• M14 = "(", S={-, *, /}; N="10, 3, 14, 2, -";
• M15 = "2", S={-, *, /}; N="10, 3, 14, 2, -, 2";
• M16 = "+", S={-, *, /, +}; N="10, 3, 14, 2, -, 2";
• M17 = "4", S={-, *, /, +}; N="10, 3, 14, 2, -, 2, 4";
• M18 = ")", S={-, *, /}; N="10, 3, 14, 2, -, 2, 4, +";
• M19 = ")", S={-, *}; N="10, 3, 14, 2, -, 2, 4, +, /";
• M20 = ")", S={-}; N="10, 3, 14, 2, -, 2, 4, +, /, *";
• M21 = ")", S={}; N="10, 3, 14, 2, -, 2, 4, +, /, , -"; Output: N = 10 3 14 2 - 2 4 + / - `2

5. Ví dụ

Code:` Input: M = (10-(3*((14-2)/(2+4)))) sang hậu tố (ở đây M có số phần tử là n=21)

• Khởi tạo: S={}; N="";
• M1 = "(", bỏ qua
• M2 = "10", S={}; N="10";
• M3 = "-", S={-}; N="10";
• M4 = "(", S={-}; N="10";
• M5 = "3", S={-}; N="10, 3";
• M6 = "", S={-, }; N="10, 3";
• M7 = "(", S={-, *}; N="10, 3";
• M8 = "(", S={-, *}; N="10, 3";
• M9 = "14", S={-, *}; N="10, 3, 14";
• M10 = "-", S={-, *, -}; N="10, 3, 14";
• M11 = "2", S={-, *, -}; N="10, 3, 14, 2";
• M12 = ")", S={-, *}; N="10, 3, 14, 2, -";
• M13 = "/", S={-, *, /}; N="10, 3, 14, 2, -";
• M14 = "(", S={-, *, /}; N="10, 3, 14, 2, -";
• M15 = "2", S={-, *, /}; N="10, 3, 14, 2, -, 2";
• M16 = "+", S={-, *, /, +}; N="10, 3, 14, 2, -, 2";
• M17 = "4", S={-, *, /, +}; N="10, 3, 14, 2, -, 2, 4";
• M18 = ")", S={-, *, /}; N="10, 3, 14, 2, -, 2, 4, +";
• M19 = ")", S={-, *}; N="10, 3, 14, 2, -, 2, 4, +, /";
• M20 = ")", S={-}; N="10, 3, 14, 2, -, 2, 4, +, /, *";
• M21 = ")", S={}; N="10, 3, 14, 2, -, 2, 4, +, /, , -"; Output: N = 10 3 14 2 - 2 4 + / - `3

Permissions in this forum:

Bạn không có quyền trả lời bài viết