Bài tập Ngăn xếp(Stack)

1. The Next Greater Element (Samsung, Amazon). Ta gọi NGE(i) của một mảng A[] là phần tử lớn hơn A[i] đầu tiên bên phải A[i]; NGE(i) = -1 nếu i là phần tử cuối cùng của mảng hoặc bên phải A[i] không có phần tử nào lớn hơn A[i]. Cho mảng A[] gồm n phần tử, hãy in ra NGE(i) của mỗi phần tử với độ phức tạp thời gian O(n).
Input: 4
13 7 6 12
Output:
-1
12
12
-1
Code tham khảo:Tải về
2.Bracket Numbers (Flipkart). Cho biểu thức exp độ dài n chứa đựng một số ký tự ‘(‘, ‘)’. Hãy in ra số thứ tự của các cặp ‘(‘, ‘)’ khi phân tích biểu thức.
Input:
(a + (b *c) ) + (d/e)
( ( () ) ( () ) )
Output:
1 2 2 1 3 3
1 2 3 3 2 4 5 5 4 1
Code tham khảo:Tải về
3. Prefix to Infix Conversion. Có ba dạng biểu diễn cho các biểu thức số học và logic:
Infix (trung tố): Biểu diễn biểu thức dưới dạng trung tố là phép biểu diễn biểu thức trong đó phép toán được đặt giữa hai toán hạng. Ví dụ (A+B) * (C-D).
Prefix (tiền tố): Biểu diễn biểu thức dưới dạng tiền tố là phép biểu diễn biểu thức trong đó phép toán được đặt trước hai toán hạng. Ví dụ *+AB-CD (tương ứng với biểu thức trung tố (A+B)*(C-D). Postfix (hậu tố): Biểu diễn biểu thức dưới dạng hậu tố là phép biểu diễn biểu thức trong đó phép toán được đặt sau hai toán hạng. Ví dụ AB+CD-* (tương ứng với biểu thức trung tố (A+B)*(C-D). Hãy viết chương trình chuyển đổi biểu thức biểu diễn dưới dạng tiền tố về dạng trung tố.
Input:
*+AB-CD
*-A/BC-/AKL
Output:
((A+B)*(C-D))
((A-(B/C))*((A/K)-L)
Code tham khảo:Tải về
4. Prefix to Postfix Conversion. Có ba dạng biểu diễn cho các biểu thức số học và logic:
Infix (trung tố): Biểu diễn biểu thức dưới dạng trung tố là phép biểu diễn biểu thức trong đó phép toán được đặt giữa hai toán hạng. Ví dụ (A+B) * (C-D).
Prefix (tiền tố): Biểu diễn biểu thức dưới dạng tiền tố là phép biểu diễn biểu thức trong đó phép toán được đặt trước hai toán hạng. Ví dụ *+AB-CD (tương ứng với biểu thức trung tố (A+B)*(C-D). Postfix (hậu tố): Biểu diễn biểu thức dưới dạng hậu tố là phép biểu diễn biểu thức trong đó phép toán được đặt sau hai toán hạng. Ví dụ AB+CD-* (tương ứng với biểu thức trung tố (A+B)*(C-D). Hãy viết chương trình chuyển đổi biểu thức biểu diễn dưới dạng tiền tố về dạng hậu tố.
Input:
*+AB-CD
*-A/BC-/AKL
Output:
AB+CD-*
ABC/-AK/L-*
Code tham khảo:Tải về
5. Postfix to Prefix Conversion. Có ba dạng biểu diễn cho các biểu thức số học và logic:
Infix (trung tố): Biểu diễn biểu thức dưới dạng trung tố là phép biểu diễn biểu thức trong đó phép toán được đặt giữa hai toán hạng. Ví dụ (A+B) * (C-D).
Prefix (tiền tố): Biểu diễn biểu thức dưới dạng tiền tố là phép biểu diễn biểu thức trong đó phép toán được đặt trước hai toán hạng. Ví dụ *+AB-CD (tương ứng với biểu thức trung tố (A+B)*(C-D). Postfix (hậu tố): Biểu diễn biểu thức dưới dạng hậu tố là phép biểu diễn biểu thức trong đó phép toán được đặt sau hai toán hạng. Ví dụ AB+CD-* (tương ứng với biểu thức trung tố (A+B)*(C-D). Hãy viết chương trình chuyển đổi biểu thức biểu diễn dưới dạng hậu tố về dạng tiền tố.
Input:
AB+CD-*
ABC/-AK/L-*
Output:
*+AB-CD
*-A/BC-/AKL
Code tham khảo:Tải về
6. Postfix to Infix Conversion. Có ba dạng biểu diễn cho các biểu thức số học và logic:
Infix (trung tố): Biểu diễn biểu thức dưới dạng trung tố là phép biểu diễn biểu thức trong đó phép toán được đặt giữa hai toán hạng. Ví dụ (A+B) * (C-D).
Prefix (tiền tố): Biểu diễn biểu thức dưới dạng tiền tố là phép biểu diễn biểu thức trong đó phép toán được đặt trước hai toán hạng. Ví dụ *+AB-CD (tương ứng với biểu thức trung tố (A+B)*(C-D). Postfix (hậu tố): Biểu diễn biểu thức dưới dạng hậu tố là phép biểu diễn biểu thức trong đó phép toán được đặt sau hai toán hạng. Ví dụ AB+CD-* (tương ứng với biểu thức trung tố (A+B)*(C-D). Hãy viết chương trình chuyển đổi biểu thức biểu diễn dưới dạng hậu tố về dạng trung tố.
Input:
ABC++
AB*C+
Output:
(A+(B+C)
((A*B)+C)
Code tham khảo:Tải về
7. Infix to Postfix Conversion. Có ba dạng biểu diễn cho các biểu thức số học và logic:
Infix (trung tố): Biểu diễn biểu thức dưới dạng trung tố là phép biểu diễn biểu thức trong đó phép toán được đặt giữa hai toán hạng. Ví dụ (A+B) * (C-D).
Prefix (tiền tố): Biểu diễn biểu thức dưới dạng tiền tố là phép biểu diễn biểu thức trong đó phép toán được đặt trước hai toán hạng. Ví dụ *+AB-CD (tương ứng với biểu thức trung tố (A+B)*(C-D). Postfix (hậu tố): Biểu diễn biểu thức dưới dạng hậu tố là phép biểu diễn biểu thức trong đó phép toán được đặt sau hai toán hạng. Ví dụ AB+CD-* (tương ứng với biểu thức trung tố (A+B)*(C-D). Hãy viết chương trình chuyển đổi biểu thức biểu diễn dưới dạng trung tố về dạng hậu tố.
Input:
(A+(B+C)
((A*B)+C)
Output:
ABC++
AB*C+
Code tham khảo:Tải về
8. Evaluation Prefix Expression. Có ba dạng biểu diễn cho các biểu thức số học và logic:
Infix (trung tố): Biểu diễn biểu thức dưới dạng trung tố là phép biểu diễn biểu thức trong đó phép toán được đặt giữa hai toán hạng. Ví dụ (A+B) * (C-D).
Prefix (tiền tố): Biểu diễn biểu thức dưới dạng tiền tố là phép biểu diễn biểu thức trong đó phép toán được đặt trước hai toán hạng. Ví dụ *+AB-CD (tương ứng với biểu thức trung tố (A+B)*(C-D). Postfix (hậu tố): Biểu diễn biểu thức dưới dạng hậu tố là phép biểu diễn biểu thức trong đó phép toán được đặt sau hai toán hạng. Ví dụ AB+CD-* (tương ứng với biểu thức trung tố (A+B)*(C-D). Hãy viết chương trình chuyển tính toán giá trị của biểu thức tiền tố.
Input:
-+8/632
-+7*45+2
Output:
8
25
Code tham khảo:Tải về
9. Evaluation Postfix Expression. Có ba dạng biểu diễn cho các biểu thức số học và logic:
Infix (trung tố): Biểu diễn biểu thức dưới dạng trung tố là phép biểu diễn biểu thức trong đó phép toán được đặt giữa hai toán hạng. Ví dụ (A+B) * (C-D).
Prefix (tiền tố): Biểu diễn biểu thức dưới dạng tiền tố là phép biểu diễn biểu thức trong đó phép toán được đặt trước hai toán hạng. Ví dụ *+AB-CD (tương ứng với biểu thức trung tố (A+B)*(C-D). Postfix (hậu tố): Biểu diễn biểu thức dưới dạng hậu tố là phép biểu diễn biểu thức trong đó phép toán được đặt sau hai toán hạng. Ví dụ AB+CD-* (tương ứng với biểu thức trung tố (A+B)*(C-D). Hãy viết chương trình chuyển tính toán giá trị của biểu thức hậu tố.
Input:
231*+9-
875*+9-
Output:
-4
34
Code tham khảo:Tải về
10. Redundant Brackets. Cho biểu thức số học, hãy cho biết biểu thức số học có dư thừa các cặp ký hiệu ‘(’,’) ‘ hay không?
Input:
((a+b))
(a + (b)/c)
(a + b*(c-d))
Output:
YES
YES
NO
Code tham khảo:Tải về
11. Reverse Word (Amazon). Cho một xâu ký tự bao gồm nhiều từ trong xâu. Hãy đảo ngược từng từ trong xâu?
Input:
ABC DEF
123 456
Output:
CBA FED
321 654
Code tham khảo:Tải về

Ngoài ra bạn đọc có thể tham khảo các bài viết về thuật toán và lập trình tại VietAlgo's Blog.

Nếu thấy tài liệu có ích hi vọng các bạn ủng hộ trang web bằng cách like và theo dõi địa chỉ page chính thức của Tài Liệu Blog tại: https://www.facebook.com/TaiLieuBlog/

Bài tập Ngăn xếp(Stack)