Khoa học máy tính trong Ruby: Sử dụng stacks để giải quyết vấn đề

Nếu như bạn không có bằng cấp về Computer Science (CS), bạn có thể sẽ cảm thấy rằng mình đang bỏ lỡ một điều gì đó, hoặc bạn sẽ cảm thấy CS nó là một cái gì đó rất trìu tượng... Hoặc là Ruby đã làm những việc khó cho bạn, và bạn chỉ việc sử dụng chúng...

Trong bài viết này tôi sẽ cho các bạn thấy một khái niệm CS thực tế với Ruby mà bạn có thể thực hành nó ngay bây giờ, đó là việc sử dụng stacks để giải quyết vấn đề. Stacks không còn xa lạ với developers, tuy nhiên trong bài viết tôi cũng sẽ giới thiệu lại về stacks vì chúng ta đang sử dụng stack để giải quyết vấn đề.

The Stack

Stack (ngăn xếp) là một cấu trúc dữ liệu mà bạn có thể sử dụng như “to-do” list. Bạn lấy các phần tử từ stack và xử lý chúng cho tới khi stack trống.

Dưới đây là một ví dụ: Đầu tiên, đẩy 1 vào stack trống ta sẽ được một stack với 1 phần tử 1 Sau đó tiếp tục push 2 vào stack

2
1

Tiếp tục đẩy 3 vào stack

3
2
1

Rồi ta lấy một phần tử trong stack ra ta còn lại 2 phần tử

2
1

Một điều lớn cần lưu ý ở đây là các phần tử mới được thêm vào thì sẽ được xếp ở đầu của stack. Với phong cách “Last-In First-Out” (LIFO) (vào sau ra trước), nó có nghĩa là khi bạn lấy một phần tử (pop) từ stack, nó sẽ là phàn tử cuối cùng được đẩy vào stack.

Một cách khác để hình dung cách hoạt động của stack là tưởng tượng về một chồng đĩa. Có một chồng đĩa, khi bạn để một cái đĩa khác lên chồng đĩa, bạn không thể lấy cái đĩa bên dưới nó ra mà không lấy nó trước.

Đó là tất cả những gì bạn làm với stack ở đây, đẩy mọi thứ lên đầu và lấy nó ra. Không hề có indexing ở đây.

Hãy xem một số ví dụ và cách chúng sử dụng như thế nào.

1. Ví dụ 1: flatten

Một ví dụ điển hình là method flatten trong array. Hay nói cách khác là chuyển một mảng đa chiều thành mảng một chiều.

arr = [1,2,3,[4,5],6]
 
arr.flatten

Trong Ruby có method flatten đã làm cho bạn điều này. Nhưng nếu giả sử bạn không có phương thức này thì sao? Và cách hoạt động của method này như thế nào?

Đây là thời điểm dùng stack

Ruby cung cấp 2 methods là push (<<) & pop, vì vậy chúng ta có thể đối xử với một mảng như là một stack.

Ý tưởng là chúng ta sẽ đi qua các phần tử, check xem nó có phải là một mảng không, nếu là mảng thì sẽ đẩy các phần tử bên trong mảng này lại stack. Điều xảy ra là chúng tôi tiếp tục loại bỏ các lớp mảng (giống như bóc vỏ hành tây vậy), cho đến khi không còn gì, lúc đó chúng ta sẽ được một mảng đã được flattened.

Cùng xem mã code dưới đây

arr  = [1,2,3,[[4],5],6]
flat = []
 
arr.each do |thing|
  if thing.is_a? Array
    thing.each { |i| arr << i }
  else
    flat << thing
  end
end
 
p flat
# [1, 2, 3, 6, 5, 4]

Có thể thấy rằng tôi không sử dụng pop ở trên và thứ tự các phần tử không còn được giữ nguyên sau khi được flattened vì ở đây đã sử dụng each để lấy các phần tử trong stack và dùng chúng cho thuật toán của tôi.

Một version khác là sử dụng until & empty?:

until arr.empty?
  thing = arr.pop
 
  if thing.is_a? Array
    thing.each { |i| arr << i }
  else
    flat << thing
  end
end
 
p flat
# [6, 5, 4, 3, 2, 1]

từ khi sử dụng pop thay vì each chúng ta đã nhận được một mảng đã được flattened theo thứ tự chính xác theo một cách đảo ngược.

TIP: Method Array#flatten có nhận vào một argument cho phép định nghĩa số array layer mà bạn muốn bỏ đi

arr  = [1,2,3,[[4],5],6]
arr.flatten 1
# [1, 2, 3, [4], 5, 6]

2. Ví dụ 2: Check valid cú pháp (thiếu dấu ngoặc đơn, nhọn ...)

Dưới đây là một ví dụ khác, mà Ruby không có phương pháp nào sẵn hỗ trợ cho bạn. Và nó cũng là một vấn đề cổ điển trong CS: các dấu ngoặc đưa ra có valid hay không (như là mở ngoặc mà không đóng, đóng khôn mở, hoặc mở trước đóng ..)

Ý tưởng là bạn có một string và bạn cần check xem nó có valid về mặt cú pháp dấu ngoặc (đơn, nhọn,...) hay không.

Ví dụ bạn đang viết một chương trình với các phương thức toán học. Bạn muốn chắc chắn đầu vào là hợp lệ trước khi thực thi nó.

Valid input:

input = "1 + (4 + 6) * 2"

Invalid input:

input = "1 + (4 + 6 * 2"

Bạn có thể sử dụng stack để theo dõi bất kì dấu ngoặc nào bạn gặp trong input và sau đó khi bạn thấy một dấu ngoặc mới, bạn kiểm tra phía trên cùng của stack để chắc chắn rằng nó là dấu ngoặc đóng phù hợp với dấu trước đó.

Nếu không có ngoặc nào tương ứng có nghĩa là đầu vào của bạn không hợp lệ.

ví dụ:

PARENS = {
  "(" => ")",
  "{" => "}",
  "[" => "]"
}
 
OPENING_PARENS = PARENS.keys
CLOSING_PARENS = PARENS.values
 
def valid_parentheses(string)
  stack  = []
 
  string.each_char do |ch|
    if OPENING_PARENS.include?(ch)
      stack << ch
    elsif CLOSING_PARENS.include?(ch)
      ch == PARENS[stack.last] ? stack.pop : (return false)
    end
  end

  stack.empty?
end
 
p valid_parentheses("(){}[]") # true
p valid_parentheses("[(])")   # false

Một điều mà bạn nhận thấy là tôi kết thúc method valid_parentheses với lệnh stack.empty? để chắc chắn rằng chúng ta không kết thúc với một dấu ngoặc không được đóng.

Nếu tất cả dấu ngoặc đều được đóng một cách chính xác thì stack phải trống rỗng.

Kết luận

Qua 2 ví dụ trên hy vọng bạn sẽ học được những điều mới và biết được cách sử dụng stack để giải quyết vấn đề gặp phải.