Practical Computer Science in Ruby: Using Stacks to Solve Problems

Trong bài viết này tôi muốn cho các bạn thấy một khái niệm về Computer science thực tế mà bạn có thể bắt đầu thực hiện ngay bây giờ.

Stack

Stack là 1 cấu trúc dữ liệu mà bạn có thể sử dụng như danh sách các việc cần làm. Bạn cứ lấy các phần tử trong stack cho đến khi stack rỗng.

Push 5 into an empty stack:
5
Push 3 into the stack:
3
5
Push 9 into the stack:
9
3
5
Take one item from the stack:
3
5

Các giá trị mới được đẩy vào stack thì được đẩy vào top of the stack. Stack tuân theo quy tắc Last In First Out điều đấy có nghĩa là khi bạn lấy một phần tử trong stack thì sẽ lấy phần tử cuối cùng mà bạn vừa đưa vào. Nó giống như kiểu 1 chồng đĩa, bạn không thể lấy cái cuối cùng mà không phải nhấc những cái trên nó. Để áp dụng chúng ta hãy xem một số ví dụ về cách sử dụng stack trong lập trình.

Example 1 (flatten)

Trong Array của ruby có method là flatten nó có tác dụng biến mảng đa chiều về mảng 1 chiều.

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

Tại sao method này có thể làm được điều đó. Ý tưởng được đưa ra là duyệt qua tất cả các phần tử trong mảng đầu vào và kiểm tra xem nó là 1 mảng con hay là 1 cái gì đấy. Nếu là mảng thì chúng ta thực hiện đẩy các phần tử trong mảng con vào 1 stack . Thực hiện cho đến khi hết phần tử trong mảng đầu vào. Kết quả cho ra là mảng 1 chiều trong được lưu trữ trong stack.

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, 4, 5]

Hoặc 1 cách khác 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]

Tip: The Array#flatten method takes an argument, which lets you define how many layers of nesting you would like to remove (by default all of them).

Example 2 (balanced parenthesis)

Và tiếp theo là 1 ví dụ cổ điển trong compute science Bạn đưa vào 1 chuỗi, và kiểm tra chuỗi hợp lệ bằng việc thông qua các dấu đóng mở ngoặc.

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

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

Ý tưởng bài toán: Sử dụng một ngăn xếp để lưu trữ các dấu ngoặc ở chuỗi đầu vào, và khi tìm thấy một dấu ngoặc mới, kiểm tra lại đầu stack để chắc chắn nó là phù hợp với dấu ngoặc đóng.

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

Conclusion

Tôi hy vọng rằng bạn đã học được 1 điều gì đấy mới mẻ, và có thể bắt đầu sử dụng stack để giải quyết các vấn đề lập trình.

http://www.blackbytes.info/2017/03/computer-science-in-ruby-stacks/