Chuyển phép toán trung tố sang tiền tố
Solution: Trước khi thảo luận về thuật toán, trước tiên chúng ta hãy xem định nghĩa của các biểu thức infix, prefix và postfix. Show Infix: Biểu thức infix là một ký tự đơn hoặc một toán tử, được tiến hành bởi một chuỗi infix và theo sau là một chuỗi Infix khác. Prefix: Biểu thức tiền tố là một ký tự đơn hoặc một toán tử, theo sau là hai chuỗi tiền tố. Mọi chuỗi tiền tố dài hơn một biến đơn chứa một toán tử, toán hạng thứ nhất và toán hạng thứ hai. Postfix: Một biểu thức hậu tố (còn được gọi là Ký hiệu đánh bóng ngược) là một ký tự đơn hoặc một toán tử, đứng trước hai chuỗi hậu tố. Mỗi chuỗi hậu tố dài hơn một biến đơn chứa các toán hạng đầu tiên và thứ hai theo sau bởi một toán tử. Các khái niệm tiền tố và hậu tố là các phương pháp viết biểu thức toán học không có dấu ngoặc đơn. Thời gian để đánh giá một hậu tố và biểu thức tiền tố là O (n), n là số phần tử trong mảng. Bây giờ, chúng ta hãy tập trung vào thuật toán. Trong các biểu thức infix, ưu tiên toán tử là ngầm định trừ khi chúng ta sử dụng dấu ngoặc đơn. Do đó, đối với thuật toán chuyển đổi tiền tố sang hậu tố, chúng ta phải xác định độ ưu tiên của toán tử (hoặc mức độ ưu tiên) bên trong thuật toán. Bảng cho thấy mức độ ưu tiên và tính liên kết của chúng (thứ tự đánh giá) giữa các toán tử. Các tính chất quan trọng:
Algorithm
Để hiểu rõ hơn, chúng ta hãy theo dõi từng bước chuyển đổi của một ví dụ: A * B- (C + D) + E Problem-3Đối với một mảng đã cho có n ký hiệu thì có bao nhiêu hoán vị ngăn xếp? Solution: Số hoán vị ngăn xếp với n ký hiệu được biểu diễn bằng số Catalan và mình sẽ trình bày điều này trong chương Dynamic Programming. Problem-4Thảo luận về cách tính toán một biểu thức postfix sử dụng Stack? Solution: Algorithm:
Ví dụ: Hãy để chúng tôi xem thuật toán trên hoạt động như thế nào bằng cách sử dụng một ví dụ. Giả sử rằng chuỗi postfix là 123 * + 5-. Ban đầu ngăn xếp trống. Bây giờ, ba ký tự đầu tiên được quét là 1, 2 và 3, là các toán hạng. Chúng sẽ được đẩy vào ngăn xếp theo thứ tự đó. Ký tự tiếp theo được quét là “”, là một toán tử. Do đó, chúng tôi pop hai phần tử trên cùng khỏi ngăn xếp và thực hiện phép toán “” với hai toán hạng. Toán hạng thứ hai sẽ là phần tử đầu tiên được pop. Giá trị của biểu thức (2 * 3) đã được tính bằng (6) được đẩy vào ngăn xếp. Ký tự tiếp theo được quét là “+”, là một toán tử. Do đó, chúng tôi pop hai phần tử trên cùng khỏi ngăn xếp và thực hiện phép toán “+” với hai toán hạng. Toán hạng thứ hai sẽ là phần tử đầu tiên được xuất hiện. Giá trị của biểu thức (1 + 6) đã được tính bằng (7) được đẩy vào ngăn xếp. Ký tự tiếp theo được quét là “5”, được thêm vào ngăn xếp. Ký tự tiếp theo được quét là “-”, là một toán tử. Do đó, chúng tôi pop hai phần tử trên cùng khỏi ngăn xếp và thực hiện phép toán “-” với hai toán hạng. Toán hạng thứ hai sẽ là phần tử đầu tiên được xuất hiện. Giá trị của biểu thức (7-5) đã được tính bằng (2) được đẩy vào ngăn xếp. Bây giờ, vì tất cả các ký tự đã được quét, phần tử còn lại trong ngăn xếp (sẽ chỉ có một phần tử trong ngăn xếp) sẽ được trả về. Kết quả cuối cùng:
Problem-5Chúng ta có thể đánh giá biểu thức infix với các ngăn xếp trong một lần quét không? Solution: Sử dụng 2 ngăn xếp, chúng ta có thể đánh giá một biểu thức infix trong 1 lần vượt qua mà không cần chuyển đổi thành hậu tố. Algorithm: Trong sách tác giả viết hơi khó hiểu, hoặc có thể in bị thiếu, ở bước 3 c => i. Nên mình có tham khảo thêm ở đây:
Problem-6Làm thế nào để thiết kế một ngăn xếp sao cho getMinimum() phải là O(1)O (1)? Solution: Lấy một ngăn xếp bổ trợ duy trì mức tối thiểu của tất cả các giá trị trong ngăn xếp. Ngoài ra, giả sử rằng mỗi phần tử của ngăn xếp nhỏ hơn các phần tử bên dưới của nó. Để đơn giản, chúng ta hãy gọi là ngăn xếp phụ tối thiểu ngăn xếp. Khi chúng ta pop ngăn xếp chính, cũng pop ngăn xếp tối thiểu. Khi chúng tôi push ngăn xếp chính, hãy push phần tử mới hoặc mức tối thiểu hiện tại, tùy theo giá trị nào thấp hơn. Tại bất kỳ thời điểm nào, nếu chúng ta muốn nhận giá trị nhỏ nhất, thì chúng ta chỉ cần trả về phần tử trên cùng từ ngăn xếp min. Hãy để chúng tôi lấy một ví dụ và tìm ra nó. Ban đầu, chúng ta hãy giả sử rằng chúng ta đã đẩy 2, 6, 4, 1 và 5. Dựa trên thuật toán nói trên, ngăn xếp tối thiểu sẽ giống như sau: Sau khi pop hai lần, chúng tôi nhận được: Dựa trên thảo luận ở trên, bây giờ chúng ta hãy viết mã các hoạt động push, pop và GetMinimum().
Time complexity: O(1). Space complexity: O(n) [for Min stack].\ Problem-7Đối với Problem-6, liệu có thể cải thiện độ phức tạp của không gian không? Solution: Yes. Vấn đề chính của cách tiếp cận trước là, đối với mỗi thao tác đẩy, chúng tôi cũng đẩy phần tử trên lên ngăn xếp tối thiểu (hoặc phần tử mới hoặc phần tử tối thiểu hiện có). Điều đó có nghĩa là, chúng tôi đang đẩy các phần tử tối thiểu trùng lặp vào ngăn xếp. Bây giờ, chúng ta hãy thay đổi thuật toán để cải thiện độ phức tạp của không gian. Chúng tôi vẫn có ngăn xếp tối thiểu, nhưng chúng ta chỉ pop ra khỏi nó khi giá trị chúng tôi bật ra từ ngăn xếp chính bằng với giá trị trên ngăn xếp tối thiểu. Chúng tôi chỉ đẩy lên ngăn xếp min khi giá trị được đẩy lên ngăn xếp chính nhỏ hơn hoặc bằng giá trị min hiện tại. Trong thuật toán đã sửa đổi này cũng vậy, nếu chúng ta muốn có giá trị nhỏ nhất thì chúng ta chỉ cần trả về phần tử trên cùng từ ngăn xếp min. Ví dụ: lấy phiên bản gốc và đẩy lại 1 lần nữa, chúng tôi sẽ nhận được: Pop từ cả 2 ngăn xếp vì 1==1, để lại: Tiếp theo chỉ pop từ main stack, vì 5 > 1: Lần tiếp theo sẽ pop cả 2 stacks vì 1 == 1: Lưu ý: Sự khác biệt chỉ là trong hoạt động push và pop.
Problem-8Cho một mảng các ký tự được tạo thành với các kí tự a và b. Chuỗi được đánh dấu bằng ký tự đặc biệt X đại diện cho giữa danh sách (ví dụ: ababa… ababXbabab… ..baaa). Kiểm tra xem chuỗi có phải là palindrome hay không. Solution: Đây là một trong những thuật toán đơn giản nhất. Những gì chúng ta làm là, bắt đầu hai chỉ mục, một ở đầu chuỗi và một ở cuối chuỗi. Mỗi lần so sánh xem các giá trị ở cả hai chỉ mục có giống nhau hay không. Nếu các giá trị không giống nhau thì chúng ta nói rằng chuỗi đã cho không phải là palindrome, nếu các giá trị giống nhau thì tăng chỉ số bên trái và giảm chỉ số bên phải. Tiếp tục quá trình này cho đến khi cả hai chỉ mục gặp nhau ở giữa (tại X) hoặc nếu chuỗi không phải là palindrome.
Time Complexity: O(n). Space Complexity: O(1). Problem-9Đối với Problem-8, nếu đầu vào nằm trong danh sách được liên kết đơn thì làm cách nào để kiểm tra xem các phần tử trong danh sách có tạo thành palindrome hay không (Điều đó có nghĩa là không thể di chuyển lùi lại). Solution: Tham khảo Problem 39, mình đã có trình bày về vấn đề này Problem-10Chúng ta có thể giải quyết Problem-8 bằng cách sử dụng ngăn xếp không? Solution: Yes Algorithm
Problem-11Cho một ngăn xếp, làm thế nào để đảo ngược nội dung của ngăn xếp chỉ sử dụng các thao tác ngăn xếp (push và pop)? Solution: Sử dụng đệ quy Algorithm
Time Complexity: O(n2). Space Complexity: O(n), for recursive stack. Problem-12Chỉ ra cách triển khai một queue một cách hiệu quả bằng cách sử dụng hai stack. Phân tích thời gian chạy của các hoạt động hàng đợi. Solution: Mình sẽ trình bày trong chương queue Problem-13Chỉ ra cách triển khai một stack một cách hiệu quả bằng cách sử dụng hai queue. Phân tích thời gian chạy của các hoạt động hàng đợi. Solution: Mình sẽ trình bày trong chương queue Problem-14Làm cách nào để triển khai hai stack chỉ sử dụng một array? Các quy trình ngăn xếp của chúng ta không nên chỉ ra một ngoại lệ trừ khi mọi vị trí trong mảng được sử dụng? |