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ề
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 Ebook-Document tại: https://www.facebook.com/Ebook-Document-652588761864731