Computer >> Máy Tính >  >> Lập trình >> Ruby

Cách sử dụng ngăn xếp trong Ruby để giải quyết vấn đề

Nếu bạn không có bằng CS (Khoa học Máy tính), bạn có thể cảm thấy như mình đang bỏ lỡ điều gì đó…

Hoặc bạn có thể cảm thấy như CS quá trừu tượng để hữu ích…

Hoặc Ruby đã làm tất cả công việc khó khăn cho bạn…

Dù bằng cách nào…

Sẽ rất hữu ích nếu bạn hiểu những kiến ​​thức cơ bản về cấu trúc dữ liệu như hàm băm, ngăn xếp và hàng đợi.

Trong bài đăng này :

Bạn sẽ khám phá cách sử dụng ngăn xếp trong Ruby.

Một khái niệm khoa học máy tính thực tế mà bạn có thể bắt đầu áp dụng ngay bây giờ!

Hiểu về ngăn xếp trong Ruby

Ngăn xếp trong Ruby là gì?

Ngăn xếp là một cấu trúc dữ liệu mà bạn có thể sử dụng làm danh sách "việc cần làm". Bạn tiếp tục lấy các phần tử từ ngăn xếp và xử lý chúng cho đến khi ngăn xếp trống.

Đây là hình ảnh trình bày.

Đẩy 5 vào ngăn xếp trống :

5

Đẩy 3 vào ngăn xếp :

3
5

Đẩy số 9 vào ngăn xếp :

9
3
5

Lấy một mục từ ngăn xếp :

3
5

Điều quan trọng cần lưu ý ở đây là các mục mới được thêm vào đầu ngăn xếp . Theo kiểu “Last-In First-Out” (LIFO). Có nghĩa là khi bạn lấy (bật) một mục từ ngăn xếp, nó sẽ là mục cuối cùng được đẩy vào đó.

Một cách khác để hình dung cách thức hoạt động là suy nghĩ về một chồng đĩa. Nếu bạn đặt một đĩa lên trên đĩa khác, bạn không thể lấy đĩa dưới cùng ra mà không lấy đĩa trên ra trước.

Đó là tất cả những gì bạn đang làm với một ngăn xếp, đẩy mọi thứ lên trên cùng hoặc bật mọi thứ ra. Không có lập chỉ mục .

Hãy xem một số ví dụ mã về cách có thể sử dụng mã này.

Cách làm phẳng một mảng bằng cách sử dụng ngăn xếp

Một ví dụ cổ điển về ngăn xếp là sử dụng chúng để làm phẳng một mảng. Nói cách khác, chuyển đổi mảng nhiều chiều thành mảng một chiều.

Đây là một ví dụ :

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

arr.flatten

Trong Ruby, chúng tôi có phương thức flatten thực hiện điều này cho bạn. Nhưng nếu bạn không có phương pháp này thì sao? Và phương pháp này hoạt động như thế nào?

Đây là nơi ngăn xếp xuất hiện!

Ruby triển khai phương thức push &pop , vì vậy chúng ta có thể coi một mảng như một ngăn xếp.

Lưu ý:Cả push &<< là cùng một phương pháp. Tôi sẽ sử dụng << trong các ví dụ mã của tôi.

Ý tưởng là xem qua mọi phần tử và kiểm tra xem nó là một mảng hay một cái gì đó khác. Nếu nó là một mảng thì chúng ta sẽ push các phần tử bên trong mảng này trở lại ngăn xếp.

Điều xảy ra là chúng ta tiếp tục loại bỏ các lớp mảng (như một củ hành tây) cho đến khi không còn lớp nào. Điều này sẽ để lại cho chúng ta một mảng phẳng.

Đây là mã :

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]

Bạn sẽ thấy không có pop gọi phương thức trong mã này.

Điều này là do tôi đang để each thực hiện công việc khó khăn để lấy các mục từ ngăn xếp và đưa chúng vào thuật toán của tôi. Cũng lưu ý cách thứ tự của các phần tử không được duy trì khi thực hiện mọi việc theo cách này.

Một phiên bản 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]

Vì chúng tôi đang sử dụng pop bây giờ, thay vì để each làm điều của nó, chúng tôi đang nhận được mảng phẳng theo đúng thứ tự ... Nhưng ngược lại.

Điều này tiết lộ một thuộc tính thú vị của ngăn xếp :

Bất kể danh sách những thứ bạn đưa vào, nó sẽ trở lại theo cùng một thứ tự nhưng ngược lại.

Mẹo:Array#flatten phương thức nhận đối số, cho phép bạn xác định số lượng lớp lồng nhau mà bạn muốn loại bỏ (theo mặc định là tất cả chúng).

Giải quyết vấn đề dấu ngoặc cân bằng

Đây là một ví dụ khác và không có phương thức Ruby tương đương nào để làm điều này cho bạn!

Đó cũng là một vấn đề kinh điển khác trong khoa học máy tính ...

Tên là:

Đối sánh dấu ngoặc đơn cân đối.

Ý tưởng là bạn được cung cấp một chuỗi và bạn cần xác thực xem dấu ngoặc đơn có hợp lệ không.

Ví dụ, giả sử bạn đang viết một chương trình đánh giá toán học. Bạn muốn đảm bảo đầu vào hợp lệ trước khi xử lý.

Ví dụ (Đầu vào hợp lệ):

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

Ví dụ (Đầu vào không hợp lệ):

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

Bạn có thể sử dụng một ngăn xếp để theo dõi bất kỳ dấu ngoặc nào bạn đã tìm thấy trong đầu vào và sau đó khi bạn tìm thấy một dấu ngoặc đơn mới, bạn kiểm tra phần trên cùng của ngăn xếp để đảm bảo rằng nó khớp với dấu ngoặc đóng.

Nếu không có kết quả phù hợp có nghĩa là bạn có thông tin đầu vào 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 khác mà bạn sẽ nhận thấy là tôi đã kết thúc valid_parentheses này phương thức với stack.empty? . Điều đó để đảm bảo rằng chúng tôi không kết thúc bằng dấu ngoặc đơn.

Nếu tất cả các dấu ngoặc đơn được đóng đúng cách thì ngăn xếp sẽ trống 🙂

Ví dụ 3 (chỉ đường)

Thêm một ví dụ nữa để đảm bảo bạn hiểu cách áp dụng điều này.

Trong trường hợp này, chúng tôi được cung cấp một bộ chỉ đường và chúng tôi được thông báo rằng chúng tôi cần phải tối ưu hóa nó để tiết kiệm thời gian cho khách du lịch.

Đây là một tập hợp ví dụ:

["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST"]

Bạn sẽ nhận thấy rằng nếu bạn đi về phía bắc rồi đi về phía nam thì bạn sẽ đến cùng một nơi (giả sử rằng cả hai hướng đều có khoảng cách như nhau). Đó là những gì chúng ta cần tối ưu hóa và chúng ta có thể làm điều đó bằng cách sử dụng ngăn xếp.

Ví dụ :

input      = ["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST"]
directions = []

opposites = {
  "NORTH" => "SOUTH",
  "SOUTH" => "NORTH",
  "EAST"  => "WEST",
  "WEST"  => "EAST"
}

input.each do |dir|
  opposites[dir] == directions.last ? directions.pop : directions << dir
end

p directions

Kết luận

Tôi hy vọng bạn đã học được điều gì đó mới và bạn bắt đầu tìm cách sử dụng ngăn xếp để giải quyết các thách thức lập trình.

Đừng quên chia sẻ bài đăng này để nhiều người có thể đọc cái này!