stacks, ערימות וחידות

ערימה stack היא מבנה נתונים שעובד לפי העיקרון של אחרון נכנס ראשון יוצא (Last-In-First-Out) LIFO. משמעות הדבר שהפריט האחרון שנוסף לערימה הוא הראשון שיוסר ממנה.

אנחנו יכולים להוסיף פריטים רק לראשה של-stack ערימה, ואם אנחנו רוצים להסיר פריטים אנחנו חייבים גם כן להסיר מראש הערימה. אתה יכול לחשוב על ערימת ספרים המונחת על השולחן: אתה יכול להוסיף ספר לראש הערימה, ואם אתה רוצה להסיר ספר אתה יכול להסיר מראש הערימה.

משתמשים ב-stacks ערימות בשביל פונקציות שאפשר להחזיר אחורנית undo/redo בדפדפן או בעורכי טקסט (דוגמת וורד) "undo stack" כאשר כל שינוי למסמך נוסף לראש הערימה, וניתן לחזור אחורנית על ידי כך שמסירים בכל פעם את השינוי האחרון שנמצא בראש הערימה.

כשאנחנו מיישמים stack בקוד להוספת פריט לראש הערימה אנחנו קוראים push ולהסרת פריט pop.

נראה דוגמה לקוד בשביל יישום ערימה stack פשוטה מבוססת רשימה list של פייתון:

# create an empty list to represent the stack
stack = []  

# push some items onto the stack
stack.append('apple')
stack.append('banana')
stack.append('cherry')

# pop an item off the top of the stack
top_item = stack.pop()

print(top_item)  # output: 'cherry'
print(stack)     # output: ['apple', 'banana']

• יצרנו רשימה ריקה שקראנו לה "stack" והיא מתפקדת בתור הערימה התכנותית stack. בהמשך, הוספנו 3 פריטים לערימה באמצעות המתודה append() (לא באמצעות push? לא. כי אנחנו עובדים עם רשימה ולא עם קוד ייעודי שעושה stack. אבל רגע, תיכף נגיע לזה). לבסוף הסרנו את הפריט אשר בראש הערימה באמצעות המתודה pop() שגם החזירה את הפריט אותו הסרנו. הדפסנו את הפריט שהוסר מראש הערימה כמו גם את חלקה של הערימה שנותר אחרי הסרת הפריט מראש הערימה.

יישום של Stack באמצעות קלאס collections.deque

יישום של stack באמצעות list של פייתון אינו אופטימלי בגלל שרשימות של פייתון הם דינמיות, המקום שהם תופסות בזיכרון המחשב משתנה על פי הצורך, ושינויים אילה צורכים משאבי מחשוב.

כדי לפתור את הבעיה, אפשר להשתמש במבנה נתונים ייעודי של פייתון דוגמת הקלאס collections.deque. קלאס זה מיועד מראש לעבוד בתור stack ערימה מה שמאפשר לו להיות יעיל יותר עבור הוספת והסרת פריטים, בלי צורך להקצות זיכרון בתהליך יקר כמו שפייתון מפעיל בשביל רשימות מתארכות.

להלן דוגמה ליישום הקלאס collections.deque לצורך יישום stack:

from collections import deque

stack = deque()

stack.append('apple')
stack.append('banana')
stack.append('cherry')

# pop an item off the top of the stack
top_item = stack.pop()

print(top_item)  # output: 'cherry'
print(stack)     # output: deque(['apple', 'banana'])

בשביל ליישם Stack אנחנו צריכים מספר מתודות לכן נשתמש בקלאס עוטף wrapper class שנקרא לו Stack בתוכו ניצור את המתודות הדרושות לנו שיהיו מבוססות על הקלאס collections.deque

from collections import deque

class Stack:
    def __init__(self):
        self.items = deque()

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if len(self.items) > 0:
            return self.items.pop()
        else:
            return None

    def peek(self):
        if len(self.items) > 0:
            return self.items[-1]
        else:
            return None

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)

    def __str__(self):
        return f"{self.items}"

הקלאס Stack שכתבנו כולל את המתודות:

• push() - מוסיף פריט לראש הערימה
• pop() - מסיר פריט מראש הערימה ומחזיר אותו. אם הערימה ריקה מחזיר None
• peek() - מאפשר להציץ ולראות מה הפריט בראש הערימה בלי להסיר אותו
• size() - מחזיר את מספר הפריטים בערימה
• is_empty() - מחזיר True אם הערימה ריקה. אחרת מחזיר False.
• __str__ - מחזיר ייצוג טקסטואלי של האובייקט.

הקוד הבא בוחן את הקלאס Stack:

my_stack = Stack()
my_stack.push(1)
my_stack.push(42)


print(my_stack) # deque([1, 42])
print(my_stack.peek()) # 42
print(my_stack) # deque([1, 42])
print(my_stack.pop()) # 42
print(my_stack) # deque([1])
print(my_stack.size()) # 1
print(my_stack.is_empty()) # False
print(my_stack.pop()) # 1
print(my_stack.pop()) # None
print(my_stack.is_empty()) # True

כיצד להשתמש ב-Stack להפיכת סדר התווים במחרוזת?

ניתן להפוך את כיוונם של התווים במחרוזת באמצעות פייתון בדרכים פשוטות. השיטה הפשוטה ביותר משתמשת ב-slicing:

s = "Stacks are fun"
print(s[::-1])

• דרך זו היא יעילה ביותר מבחינה תכנותית. אפשר להשתמש גם בפונקציה reversed.

אבל במדריך זה אנחנו לומדים על שימוש ב-stack. אז נשתמש במה שלמדנו כדי להפוך מחרוזת ולקבל את התווים שלה בסדר הפוך. אתה מוזמן לנסות בעצמך. זה לא מסובך כל מה שצריך הוא להבין ש-stack מאפשר להפוך את כיוונם של רצפים כי סדר השליפה הוא הפוך מסדר ההוספה לערימה.

עכשיו תנסה בעצמך לפתח קוד פייתון אשר משתמש בקלאס Stack כדי להפוך מחרוזות. תשתדל לעשות את זה מבלי להציץ בפתרון.

אם אתה רוצה להיעזר בפתרון הרי הוא לפניך. איך הופכים את כיוונה של מחרוזת על ידי שימוש ב-stack?

def reverse_string(s):
  """
  Reverses a string using a stack.

  Args:
    s: The string to reverse.

  Returns:
    The reversed string.
  """

  # Create a stack to store the characters of the string.
  stack = Stack()

  # Iterate over the characters of the string.
  for c in s:
    # Push the character onto the stack.
    stack.push(c)

  # Iterate over the stack, popping off characters and appending them to a new string.
  reversed_string = ""
  while stack.size():
    reversed_string += stack.pop()

  # Return the reversed string.
  return reversed_string

נבחן את הפונקציה:

print(reverse_string("Python")) # prints "nohtyP"
print(reverse_string("P")) # prints "P"
print(reverse_string("")) # prints
print(reverse_string("100")) # prints "001"

נסביר: הפונקציה "reverse_string" קולטת מחרוזת אותה היא צריכה להחזיר בסדר הפוך. היא משתמשת ב-stacks לאחסון תווי המחרוזת. בשלב ראשון, הפונקציה עוברת על כל תווי המחרוזת על פי הסדר המקורי שלהם, ודוחפת אותם אל תוך הערימה stack. בשלב שני, הערימה מתרוקנת לפי סדר, מראש הערימה ועד לבסיסה. כל פריט שהיא מחזירה הוא תו שמתווסף למחרוזת reversed_string אותה הפונקציה מחזירה.

כיצד להשתמש ב-Stack לזיהוי פלינדרומים?

פלינדרום הוא כל רצף - מילה, ביטוי, מספר - שניתן לקרוא אותו מההתחלה לסוף ומהסוף להתחלה ובכל זאת לקבל את אותו דבר. דוגמאות לפלינדרומים בעברית הם: "שמש", "לבלב", "מוּם תַּחַת מוּם", "ילד נתן דלי". באנגלית: "madam", "kayak", "racecar", "civic" או המשפט: "A man, a plan, a canal: Panama". אפשר גם בספרות: 7777 או תאריכים 11/11/11, 2/2/22

אנחנו יכולים להשתמש ב-Stack כדי לזהות האם מחרוזת היא פלינדרום.

זה השלב שבו אני ממליץ לעצור ולנסות לכתוב פונקציה שמזהה פלינדרומים. לחשוב למה אפשר לזהות פלינדרומים על ידי שימוש ב- stack, ולהשתמש בקלאס Stack כדי לפתור את הבעיה. אחרי שאתם מסיים לכתוב את הפתרון תנסה אותו על מחרוזות שונות כאילו שהם פלינדרומים וכאלו שאינם ותראה שאתה מקבל את התוצאה שאתה מצפה לה.

אחרי שניסית לפתור לבד אתה מוזמן להציץ בפתרון:

def is_palindrome(s):
  """
  Determines if a string is a palindrome.

  Args:
    s: The string to check.

  Returns:
    True if the string is a palindrome, False otherwise.
  """

  # Create a stack to store the characters of the string.
  stack = Stack()

  # Iterate over the characters of the string.
  for c in s:
    # Push the character onto the stack.
    stack.push(c)

  # Iterate over the stack, popping off characters and appending them to a new string.
  reversed_string = ""
  while not stack.is_empty():
    reversed_string += stack.pop()

  # Return True if the reversed string is equal to the original string, False otherwise.
  return reversed_string == s

נבחן את הפונקציה:

strings = ['madam', 'kayak' , '22/2/22', 'no', 'sir']
for s in strings:
   print(f"'{s}' is {'' if is_palindrome(s) else 'not'} a palindrome")

התוצאה:

'madam' is  a palindrome
'kayak' is a palindrome
'22/2/22' is  a palindrome
'no' is not a palindrome
'sir' is not a palindrome

הפונקציה "is_palindrome" מקבלת מחרוזת כקלט ומחזירה ערך בוליאני. True אם המחרוזת היא פלינדרום, ו-False אם לא. הפונקציה עובדת על ידי יצירת ערימה stack אשר מאחסנת את התווים של המחרוזת. התווים מאוחסנים לפי סדר אחד מעל לשני בערימה, כאשר מגיעים לתו האחרון במחרוזת, הפונקציה מסירה את הפריטים בסדר ההפוך, ומוסיפה כל תו שהיא מסירה למחרוזת חדשה "reversed_string". את המחרוזת ההפוכה היא משווה למחרוזת המקורית. תוצא השוואה זו היא הפלט שהפונקציה מפיקה.

חשוב לציין שדרכים יעילות הרבה יותר לזיהוי פלינדרומים בפייתון משתמשות בפונקציות הפנימיות של השפה שהם תמיד הרבה יותר מהירות:

# Use the ::-1 slice syntax to reverse the string
print(input == input[::-1]) # True

אפשר גם:

# 1. Use the reversed() function
# makes a list out of the string then reverses it
# 2. then join the reversed list back together to a string
print(input == "".join(reversed(input))) # True

כיצד להשתמש ב-Stack לזיהוי האם הסוגריים בביטוי הם מאוזנים?

אחת הדרכים בהם עורכי טקסט ו-IDE למיניהם עוזרים למתכנתים היא בכך שהם מתריאים במידה והסוגריים אינם מאוזנים בקוד שאנחנו כותבים. סוגריים מאוזנים משמעותם שכל סוגר פותח יש לו גם סוגר מאותו סוג שסוגר אותו. לדוגמה:

[(a + b) * c]

הוא ביטוי שבו הסוגריים מאוזנים.

לעומת זאת הביטוי:

(a + b) * c)

הוא דוגמה למקרה בו הסוגריים אינם מאוזנים.

המשימה היא לכתוב קוד המבוסס על הקלאס Stack אותו כתבנו לעיל שיצליח לזהות עבור ביטוי שניתן לו כקלט האם הסוגריים בו הם מאוזנים אם לאו.

אתה מוזמן לנסות לבד.

זה הפתרון שאני מציע, אתה מוזמן להציץ בו אחרי שתנסה לפתור לבד:

def is_balanced(s):
  """
  Determines if the parentheses in a string are balanced.

  Args:
    s: The string to check.

  Returns:
    True if the parentheses are balanced, False otherwise.
  """

  # Create a stack to store the opening parentheses.
  opening_brackets = []

  # Iterate over the characters in the string.
  for c in s:
    # If the character is an opening parenthesis, push it onto the stack.
    if c in "([{":
      opening_brackets.append(c)

    # If the character is a closing parenthesis, pop the topmost element from the stack.
    elif c in ")]}":
      if not opening_brackets:
        return False
      top = opening_brackets.pop()
      if c == ")" and top != "(":
        return False
      if c == "]" and top != "[":
        return False
      if c == "}" and top != "{":
        return False

  # If the stack is not empty, then there are unmatched opening parentheses.
  if opening_brackets:
    return False

  # The parentheses are balanced.
  return True

נבדוק:

print(is_balanced("()")) # True
print(is_balanced(")")) # False
print(is_balanced("(")) # False
print(is_balanced("(()")) # False
print(is_balanced("())")) # False
print(is_balanced("A[(B)*X]")) # True
print(is_balanced("{C+A[(B)*X]")) # False
print(is_balanced("{C+A[(B)*X]}")) # True

נסביר:

ה-Stack מאחסן את הסוגריים הפותחים. בכל פעם שהפונקציה מזהה סוגר פותח ")]}" היא מוסיפה אותו לראש הערימה. בכל פעם שהפונקציה מזהה סוגר מסיים "([{" הסוגר הפותח המקביל מוסר מראש הערימה. אם הערימה ריקה כאשר הפונקציה מסיימת לעבור על כל הביטוי, המסקנה היא שהסוגריים מאוזנים. אם הערימה stack אינה ריקה אז הסוגריים אינם מאוזנים.

נוכל להשתמש בפונקציה "is_balanced" לפתרון מגוון בעיות, דוגמת:

• וידוא ביטוי מתמטי
• פרסינג של מסמכי XML ו-JSON
• בדיקה של קוד מחשב

שימוש ב-stack בשביל להמיר מספר לייצוגו הבינארי

אחד האלגוריתמים המשמש להמרת מספר עשרוני לייצוג הבינארי שלו היא לחלק ב-2, לזכור את השארית ואת מנת החלוקה לחלק שוב ב-2. חוזרים על התהליך עד שמגיעים למנת חלוקה 0. אחרי שמסיימים לחלק, מחברים יחדיו את השאריות למחרוזת המבטאת את הייצוג הבינארי.

לדוגמה, נהפוך את המספר 25 לייצוגו הבינארי.

צעד 1: נחלק את המספר 25 ב-2 ונרשום לעצמנו את מנת החלוקה ואת השארית:

25 ÷ 2 = 12 remainder 1

צעד 2: נחלק את מנת החלוקה מהצעד הקודם ב-2 ונרשום לעצמנו את מנת החלוקה ואת השארית:

12 ÷ 2 = 6 remainder 0

נחזור על 2:

6 ÷ 2 = 3 remainder 0

נחזור על 2:

3 ÷ 2 = 1 remainder 1

נחזור על 2:

1 ÷ 2 = 0 remainder 1

צעד 3: אין לנו אפשרות יותר לחלק כי מנת החלוקה היא 0 אז נחבר את השאריות מהצעדים הקודמים מהסוף להתחלה:

11001

נסכם את האלגוריתם להפיכת מספר לייצוגו הבינארי:

1. נחלק מספר ב-2 ונרשום את מנת החלוקה quotient ואת השארית remainder (שהיא בהכרח 0 או 1)
2. נחזור על חלוקה ב-2 עד שנקבל מנת חלוקה שהיא 0.
3. נקרא את השאריות מהסוף להתחלה ונחבר מהם את הייצוג הבינארי של המספר.

אפשר לעשות ייצוג בינארי באמצעות stack בגלל התכונה שלו שהוא הופך את הפלט שמזינים אליו.

נסה לכתוב פונקציה המשתמשת ב-stack כדי להמיר מספר לייצוג בינארי.

פתרון אחד לתרגיל מופיע להלן (עדיף להשתמש בו רק אחרי שניסית לפתור בעצמך):

def intToBin(i, stack, isMinus = False):
   """
   Convert an integer to its binary representation.


   Args:
       i: The integer to convert.
       stack: The stack to use in the process.
       isMinus: Is the integer a minus.


   Returns:
       A binary representation of the input integer.
   """
  
   # Check if the integer is negative
   if i < 0:
       isMinus = True
       i = abs(i)
  
   # Base case
   if i == 0:
       # If the number is negative, push a "-" sign to the stack
       if isMinus:
           stack.push("-")
       # If the stack has only "-" sign, remove it
       if stack.size() == 1 and stack.peek() == "-":
           stack.pop()
       # If the stack is empty, push 0 to the stack
       if stack.is_empty():
           stack.push(0)
          
       # Pop all items from the stack and concatenate them
       # to form the binary representation
       ret = ""
       while not stack.is_empty():
           s = stack.pop()
           ret += str(s)
       return ret
  
   # Recursive case
   # Divide the integer by 2 to get the quotient and remainder
   quotient = i // 2
   remainder = i % 2
   # print(f"i = {i} | quotient = {quotient} | remainder = {remainder}")
   # Push the remainder to the stack
   stack.push(remainder)
   # print(f"stack = {stack.__str__()}")
   # Recursively call the function with the quotient
   return intToBin(quotient, stack, isMinus)

נבחן את הקוד על ידי שימוש ב-assert המשמש לדיבוג קוד ולאיתור שגיאות לוגיות בזמן הפיתוח:

# Test cases
stack = Stack()
assert intToBin(0, stack) == "0"
assert intToBin(1, stack) == "1"
assert intToBin(2, stack) == "10"
assert intToBin(3, stack) == "11"
assert intToBin(4, stack) == "100"
assert intToBin(5, stack) == "101"
assert intToBin(6, stack) == "110"
assert intToBin(7, stack) == "111"
assert intToBin(8, stack) == "1000"
assert intToBin(9, stack) == "1001"
assert intToBin(10, stack) == "1010"
assert intToBin(11, stack) == "1011"
assert intToBin(12, stack) == "1100"
assert intToBin(13, stack) == "1101"
assert intToBin(14, stack) == "1110"
assert intToBin(15, stack) == "1111"
assert intToBin(-1, stack) == "-1"
assert intToBin(-2, stack) == "-10"
assert intToBin(-3, stack) == "-11"
assert intToBin(-4, stack) == "-100"
assert intToBin(-5, stack) == "-101"
assert intToBin(-6, stack) == "-110"
assert intToBin(-7, stack) == "-111"
assert intToBin(-8, stack) == "-1000"
assert intToBin(-9, stack) == "-1001"
assert intToBin(-10, stack) == "-1010"
assert intToBin(-11, stack) == "-1011"
assert intToBin(-12, stack) == "-1100"
assert intToBin(-13, stack) == "-1101"
assert intToBin(-14, stack) == "-1110"
assert intToBin(-15, stack) == "-1111"
print("All tests passed")

• הפונקציה "intToBin" ממירה מספר לייצוגו הבינארי בעזרת stack. היא יודעת להתמודד עם מספרים חיוביים ושליליים.
• הפונקציה משתמשת ברקורסיה.
• במקרה הבסיס base case הפונקציה בודקת אם הקלט הוא 0. אם זה המצב והקלט הוא שלילי הפונקציה דוחפת "-" ל-stack. במידה וה-stack ריק היא דוחפת 0 ל-stack. לבסוף, הפונקציה מסירה את הפריטים מראש הערימה ועד לתחתיתה ומחברת אותם כדי לקבל את הקלט של הייצוג הבינארי.
• במקרה הרקורסיבי, הפונקציה מחלקת את הקלט ב-2 כדי לקבל את מנת החלוקה ושארית. היא דוחפת את השארית ל-stack ואז קוראת באופן רקורסיבי לפונקציה עבור מנת החלוקה. התהליך הרקורסיבי נמשך עד שהפונקציה מגיעה למקרה הבסיס.

מדריכים נוספים בסדרה ללימוד פייתון

פתרון בעיית הקיטבג knapsack באמצעות תכנות דינמי

אלגוריתם Selection Sort מיון בחירה

אלגוריתם חיפוש בינארי - מהבנה ליישום

לכל המדריכים בסדרה ללימוד פייתון

אהבתם? לא אהבתם? דרגו!

0 הצבעות, ממוצע 0 מתוך 5 כוכבים