วิธีใช้ Stacks ใน Ruby เพื่อแก้ปัญหา

แนวคิดคือการตรวจสอบทุกองค์ประกอบและตรวจสอบว่าเป็นอาร์เรย์หรืออย่างอื่น ถ้าเป็นอาร์เรย์ เราจะ พุช องค์ประกอบภายในอาร์เรย์นี้กลับเข้าสู่สแต็ก

สิ่งที่เกิดขึ้นคือเราลบเลเยอร์อาร์เรย์ (เช่น หัวหอม) ออกไปเรื่อยๆ จนกว่าจะไม่เหลือ สิ่งนี้จะทำให้เรามีอาร์เรย์ที่แบนราบ

นี่คือรหัส :

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]

คุณจะสังเกตเห็นว่าไม่มี ป๊อป เรียกเมธอดในโค้ดนี้

นี่เป็นเพราะฉันปล่อยให้ แต่ละ ทำงานหนักเพื่อนำไอเท็มจากสแต็ก &ป้อนให้กับอัลกอริทึมของฉัน สังเกตด้วยว่าลำดับขององค์ประกอบไม่ได้รับการดูแลเมื่อทำสิ่งนี้ด้วยวิธีนี้

รุ่นอื่นใช้ จนถึง &ว่างเปล่า? :

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]

เนื่องจากเราใช้ pop ตอนนี้แทนที่จะปล่อยให้ แต่ละ ทำตามนั้น เราจะได้อาร์เรย์แบบแบนในลำดับที่ถูกต้อง... แต่ในทางกลับกัน

เผยให้เห็นคุณสมบัติที่น่าสนใจของสแต็ค :

รายการสิ่งของที่คุณใส่เข้าไปก็จะกลับมาในลำดับเดิมแต่กลับกัน

เคล็ดลับ:Array#flatten เมธอดรับอาร์กิวเมนต์ ซึ่งให้คุณกำหนดจำนวนเลเยอร์ที่คุณต้องการลบ (โดยค่าเริ่มต้นทั้งหมด)

การแก้ปัญหาวงเล็บสมดุล

นี่เป็นอีกตัวอย่างหนึ่ง &ไม่มีวิธี Ruby ที่เทียบเท่าในการทำเช่นนี้สำหรับคุณ!

ยังเป็นอีกปัญหาคลาสสิกในวิทยาการคอมพิวเตอร์...

ชื่อ:

จับคู่วงเล็บสมดุล

แนวคิดคือคุณได้รับสตริง &คุณต้องตรวจสอบว่าวงเล็บถูกต้องหรือไม่

ตัวอย่างเช่น สมมติว่าคุณกำลังเขียนโปรแกรมประเมินผลคณิตศาสตร์ คุณต้องการให้แน่ใจว่าข้อมูลที่ป้อนนั้นถูกต้องก่อนดำเนินการ

ตัวอย่าง (ข้อมูลที่ถูกต้อง):

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

ตัวอย่าง (อินพุตไม่ถูกต้อง):

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

คุณสามารถใช้สแต็กเพื่อติดตามวงเล็บที่คุณพบในอินพุต จากนั้นเมื่อคุณพบวงเล็บใหม่ ให้ตรวจสอบด้านบนของสแต็กเพื่อให้แน่ใจว่าตรงกับวงเล็บปิด

หากไม่มีข้อมูลที่ตรงกันแสดงว่าคุณป้อนข้อมูลไม่ถูกต้อง

ตัวอย่าง :

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

อีกสิ่งหนึ่งที่คุณจะสังเกตได้คือฉันจบ valid_parentheses . นี้แล้ว เมธอดด้วย stack.empty? . เพื่อให้แน่ใจว่าเราจะไม่ลงท้ายด้วยวงเล็บเปิด

หากวงเล็บทั้งหมดปิดอย่างถูกต้อง สแต็กก็ควรว่างเปล่า 🙂

ตัวอย่างที่ 3 (ทิศทาง)

อีกหนึ่งตัวอย่างเพื่อให้แน่ใจว่าคุณเข้าใจวิธีการใช้สิ่งนี้

ในกรณีนี้ เราได้รับชุดเส้นทาง &เราได้รับแจ้งว่าเราจำเป็นต้องปรับให้เหมาะสมเพื่อประหยัดเวลานักเดินทางของเรา

นี่คือชุดตัวอย่าง:

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

คุณจะสังเกตได้ว่าถ้าคุณไปทางเหนือแล้วลงใต้ คุณจะไปอยู่ที่เดียวกัน (สมมติว่าทั้งสองทิศทางมีระยะทางเท่ากัน) นั่นคือสิ่งที่เราต้องเพิ่มประสิทธิภาพและเราสามารถทำได้โดยใช้สแต็ก

ตัวอย่าง :

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

บทสรุป

ฉันหวังว่าคุณจะได้เรียนรู้สิ่งใหม่ๆ และคุณเริ่มมองหาวิธีใช้สแต็คเพื่อแก้ปัญหาการเขียนโปรแกรม

อย่าลืม แชร์โพสต์นี้ เพื่อให้คนอ่านมากขึ้น!