پایتون

جلسه ۹۲: آیا Palindrome است؟ در پایتون

در این درس یاد میگیریم که بررسی کنیم یک singly linked list را، از این جهت که آیا Palindrome است یا نه. اگر یک linked list ویژگی Palindrome داشته باشد به این معناست که، دیتا های موجود در این linked list چه از ابتدا خوانده شوند و چه از انتها، محتوای یکسانی را به ما بدهند. ما کدنویسی این مسئله را خواهیم داشت.اول از همه، یادبگیریم که یک Palindrome جیست. Palindrome یک کلمه یا عبارتی است که چه از اول بخوانیم به سمت جلو، و چه از انتها برعکس بخوانیم، به یک عبارت میرسیم. به عنوان مثال قاچاق در فارسی یک  Palindrome است. مثال های زیادی را هم میتوان برای عبارات غیر Palindrome زد. مثلا  سلام، امتحان و …در این درس با استفاده از سه راهکار ارائه شده، این مسئله یعنی بررسی Palindrome بودن، را پیاده‌سازی میکنیم.با اولین راهکار کار را ادامه میدهیم:

راهکار اول: استفاده از string

پیاده سازی

def is_palindrome(self):
  # Solution 1:
  s = ""
  p = self.head 
  while p:
    s += p.data
    p = p.next
  return s == s[::-1]

توضیحات

اولین راهکار استفاده از string است. در خط ۳، s به عنوان یک string خالی تعریف شده است. و مقدار p را self.head در خط ۴ قرار داده ایم. در خط ۵ نیز یک حلقه while تا زمانی که p به مقدار None برسد، تکرار را انجام میدهد. در حلقه while دیتاهای نود فعلی در خط ۶ با s ترکیب شده و در جلوی آن قرار میگیرد. مقدار p در هر حلقه نیز به نود بعدی آپدیت میشود. در نهایت در خط ۸ یک عبارت Boolean را برمیگردانیم.
s == s[::-1]
عبارت شرطی بالا بررسی میکند که آیا s با مقدار معکوس شده‌ آن برابر است یا نه. که این خروجی True یا False خواهد بود. [۱-::]S یک راهکار برای معکوس سازی string است. 

راهکار دوم: استفاده از stack ها

راهکار دوم مقداری از راهکار اول متفاوت است. در راهکار دوم ما از یک stack استفاده میکنیم، اما از خود کلاس stack استفاده نمیکنیم، بلکه از یک لیست به همراه توابع append و  pop خواهیم کرد، که خیلی شبیه توابع push و pop در stack ها هستند.در این متد، در linked list حرکت میکنیم اما نود ها را به یک stack میدهیم.

پیاده سازی

کد زیر را ببینید:
def is_palindrome(self):
  # Solution 2:
  p = self.head
  s = []
  while p:
    s.append(p.data)
    p = p.next
  p = self.head
  while p:
    data = s.pop()
    if p.data != data:
      return False
    p = p.next
  return True

توضیحات

در خطوط ۴-۳ ما p و s را به عنوان self.head و [] تعریف کرده‌ایم. s یک لیست پایتون است که ما به عنوان یک stack از آن استفاده میکنیم. در خط ۵، یک حلقه while میسازیم& که در خط ۶ هر نودی که این حلقه روی آن حرکت میکند را به s اضافه (append or push) میکند.مقدار p نیز در هر تکرار حلقه آپدیت میشود(خط ۷).در خط ۸ مقدار p را به self.head نسبت داده ایم که میخواهیم linked list را دوباره روی آن به کمک یک while دیگر، در خط ۹ حرکت دهیم. در حلقه while، یک عضو از s را pop میکنیم و در متغیر data ذخیره میکنیم. میدانیم که عملیات pop اخرین عضوی که در لیست اضافه شده است را به ما میدهد. در نتیجه، ما در هر تکرار حلقه یک عضو از ابتدای linked list میگیریم و یک عضو هم از انتهای s. چراکه لیست را از انتها میخوانیم و linked list را از ابتدا شروع به خواندن نود ها میکنیم. دز خط ۱۱ این موضوع را بررسی میکنیم که آیا p.data با data برابر است یا نه. اگر برابر بود به سراغ نود بعدی با اپدیت کردن p به p.next میرویم(خط ۱۳). به عبارت دیگر، اگر p.data برابر data در هر تکرار حلقه نبود، مقدار False را بعنوان خروجی متد برمیگردانیم(خط ۱۲) در واقع زمانی به این خروجی میرسیم که، مقدار نودی که از ابتدا خوانده میشود با مقدار داده‌ای که از انتهای لیست خوانده میشود برابر نباشد. اگر این تکرار بدون اتفاق افتادن شرط خارج شدن، تا انتهای linked list انجام شد، درنهایت خروجی True را بعد از حلقه while در خط ۱۴ برمیگردانیم.این تمام چیزی بود که در مورد راهکار دوم وجود داشت. اکنون به سراغ راهکار آخر میرویم.

رهکار سوم: استفاده از دو اشاره‌گر

در این متد، ما دو اشاره‌گر p و q داریم. p به طور پیش فرض به مقدار head مرتبط است و q نیز به انتهای linked list. سپس، بخش data هر کدام از این نود ها که p و q به آن ها اشاره دارند، را بررسی میکنیم. و اگر این دو با هم برابر باشند، p را یک نود جلو میبریم و q را نیز یک نود به عقب برمیگردانیم و اینکار تا زمانی که p  و q به یکجا برسند و یا از هم عبور کنند، ادامه خواهد داشت/

پیاده‌سازی

اکنون به کد زیر میرویم و آنرا بررسی میکنیم:
def is_palindrome(self):
  if self.head:
    p = self.head 
    q = self.head 
    prev = []
    
    i = 0
    while q:
      prev.append(q)
      q = q.next
      i += 1
    q = prev[i-1]

    count = 1

    while count <= i//2 + 1:
      if prev[-count].data != p.data:
        return False
      p = p.next
      count += 1
    return True
  else:
    return True

توضیحات

در خط ۲، بررسی میکنیم که آیا linked list خالی است یا نه. اگر خالی بود به خط ۲۳-۲۲ میرود و مقدار True را برمیگرداند. در حالت دیگر، ما مقادیر p و q را به مقدار head نسبت میدهیم.(خطوط ۴-۳) و prev هم یک لیست خالی است. prev به ما کمک میکند تا q بتواند به نود قبلی خودش در هر تکرار حلقه while برگردد(خط ۱۶).در خط ۷، مقدار i نیز به ۰ تعیین شده است. حلقه while ای که در خط ۸ حضور دارد کمک میکند که q به انتهای linked list ما برسد. در حین انجام این کار، ما نود ها را در خط ۹ به انتهای prev اضافه میکنیم و همچنین مقدار q را به q.next در هر تکرار حلقه برای حرکت کردن روی نودها، تبدیل میکنیم(خط ۱۰). در این حلقه که تا زمان None نشدن q کار میکند، ما مقدار i را یکی در هر تکرار افزایش میدهیم. i در خط ۱۲ به ما کمک میکند که q به آخرین نود اشاره کند. چراکه در prev در محل i-1، آخرین نود ذخیره میشود.اکنون هر دوی p و q به محل های مدنظر ما رسیده‌اند. حال به سراغ آخرین حلقه این بخش میرویم(در خط ۱۶). شرطی که در این حلقه while استفاده شده است، از count استفاده شده، که در خط ۱۴ مقدار ۱ به آن داده شده است. این حلقه تا زمانی کار میکند که مقدار count کمتر یا مساوی i//2+1 باشد. در حلقه while، در خط ۱۷ بررسی میکنیم که آیا  عبارت [این عبارت نوشته نشد] برابر p.data است یا نه. اول از همه ببینیم که منظور از عبارت [این عبارت نوشته نشد] چیست. به طور پایه‌ای میتوان گفت که آن، نودی از نودهای prev است و  این نود بسته به index ای که مشخص کرده‌ایم یعنی –count– دارد، که در اولین حلقه این مقدار ۱- است به عبارت دیگر اخرین المان linked list. این موضوع مشخص میکند که ما نودهای ابتدا و انتها را مقایسه میکنیم و بررسی میکنیم که آیا آن ها با هم برابرند یا نه. اگر برابر نبودند مقدار false برگردانده میشود(خط ۱۸). اگر با هم برابر بودند به سراغ تکرار بعدی میرویم و مقادیر p را به p.next آپدیت میکنیم. همچنین مقدار count را هم یک مرتبه بیشتر میکنیم. در نتیجه در تکرار دوم حلقه، ما نود های دوم از ابتدا و نود دوم از انتها را بررسی خواهیم کرد. اگر  در کل این تکرار ها شرایط خارج شدن از متد به وجود نیامد و از while خارج شویم، مقدار True را در خط ۲۱ به عنوان یک تاییدیه برای palindrome بودن، میدهیم.در کدهای زیر شما متد is_palindrome را میبینید که به عنوان یکی از متدهای کلاس LinkedList استفاده شده است. یک ورودی integer میگیرد، که مشخص میکند کدام راهکار را  برای انجام این عملیات، میخواهیم انتخاب کنیم. به عنوان مثال اگر ورودی این متد ۱ باشد، راهکار اول برای حل این مسئله استفاده خواهد شد. ما میخواهیم متد را روی دو مثال radar و abc امتحان و ارزیابی کنیم. این متد باید برای مثال اول خروجی True بدهد و برای مثال دوم خروجی Flase. اکنون میتوانید داده‌های خودتان را با استفاده از این متد تست کنید.
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.head = None

    def print_list(self):
        cur_node = self.head
        while cur_node:
            print(cur_node.data)
            cur_node = cur_node.next

    def append(self, data):
        new_node = Node(data)

        if self.head is None:
            self.head = new_node
            return

        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    def prepend(self, data):
        new_node = Node(data)

        new_node.next = self.head
        self.head = new_node

    def insert_after_node(self, prev_node, data):

        if not prev_node:
            print("Previous node does not exist.")
            return 

        new_node = Node(data)

        new_node.next = prev_node.next
        prev_node.next = new_node

    def delete_node(self, key):

        cur_node = self.head

        if cur_node and cur_node.data == key:
            self.head = cur_node.next
            cur_node = None
            return

        prev = None 
        while cur_node and cur_node.data != key:
            prev = cur_node
            cur_node = cur_node.next

        if cur_node is None:
            return 

        prev.next = cur_node.next
        cur_node = None

    def delete_node_at_pos(self, pos):
        if self.head:
            cur_node = self.head

            if pos == 0:
                self.head = cur_node.next
                cur_node = None
                return

            prev = None
            count = 1
            while cur_node and count != pos:
                prev = cur_node 
                cur_node = cur_node.next
                count += 1

            if cur_node is None:
                return 

            prev.next = cur_node.next
            cur_node = None

    def len_iterative(self):

        count = 0
        cur_node = self.head

        while cur_node:
            count += 1
            cur_node = cur_node.next
        return count

    def len_recursive(self, node):
        if node is None:
            return 0
        return 1 + self.len_recursive(node.next)

    def swap_nodes(self, key_1, key_2):

        if key_1 == key_2:
            return 

        prev_1 = None 
        curr_1 = self.head 
        while curr_1 and curr_1.data != key_1:
            prev_1 = curr_1 
            curr_1 = curr_1.next

        prev_2 = None 
        curr_2 = self.head 
        while curr_2 and curr_2.data != key_2:
            prev_2 = curr_2 
            curr_2 = curr_2.next

        if not curr_1 or not curr_2:
            return 

        if prev_1:
            prev_1.next = curr_2
        else:
            self.head = curr_2

        if prev_2:
            prev_2.next = curr_1
        else:
            self.head = curr_1

        curr_1.next, curr_2.next = curr_2.next, curr_1.next

    def print_helper(self, node, name):
        if node is None:
            print(name + ": None")
        else:
            print(name + ":" + node.data)

    def reverse_iterative(self):

        prev = None 
        cur = self.head
        while cur:
            nxt = cur.next
            cur.next = prev
            
            self.print_helper(prev, "PREV")
            self.print_helper(cur, "CUR")
            self.print_helper(nxt, "NXT")
            print("\n")

            prev = cur 
            cur = nxt 
        self.head = prev

    def reverse_recursive(self):

        def _reverse_recursive(cur, prev):
            if not cur:
                return prev

            nxt = cur.next
            cur.next = prev
            prev = cur 
            cur = nxt 
            return _reverse_recursive(cur, prev)

        self.head = _reverse_recursive(cur=self.head, prev=None)

    def merge_sorted(self, llist):
    
        p = self.head 
        q = llist.head
        s = None
    
        if not p:
            return q
        if not q:
            return p

        if p and q:
            if p.data <= q.data:
                s = p 
                p = s.next
            else:
                s = q
                q = s.next
            new_head = s 
        while p and q:
            if p.data <= q.data: s.next = p s = p p = s.next else: s.next = q s = q q = s.next if not p: s.next = q if not q: s.next = p return new_head def remove_duplicates(self): cur = self.head prev = None dup_values = dict() while cur: if cur.data in dup_values: # Remove node: prev.next = cur.next cur = None else: # Have not encountered element before. dup_values[cur.data] = 1 prev = cur cur = prev.next def print_nth_from_last(self, n, method): if method == 1: #Method 1: total_len = self.len_iterative() cur = self.head while cur: if total_len == n: #print(cur.data) return cur.data total_len -= 1 cur = cur.next if cur is None: return elif method == 2: # Method 2: p = self.head q = self.head count = 0 while q: count += 1 if(count>=n):
                    break
                q = q.next
                
            if not q:
                print(str(n) + " is greater than the number of nodes in list.")
                return

            while p and q.next:
                p = p.next
                q = q.next
            return p.data

    def rotate(self, k):
        if self.head and self.head.next:
            p = self.head 
            q = self.head 
            prev = None      
            count = 0
            
            while p and count < k:
                prev = p
                p = p.next 
                q = q.next 
                count += 1
            p = prev
            while q:
                prev = q 
                q = q.next 
            q = prev 

            q.next = self.head 
            self.head = p.next 
            p.next = None

    def count_occurences_iterative(self, data):
        count = 0
        cur = self.head
        while cur:
            if cur.data == data:
                count += 1
            cur = cur.next
        return count 

    def count_occurences_recursive(self, node, data):
        if not node:
            return 0 
        if node.data == data:
            return 1 + self.count_occurences_recursive(node.next, data)
        else:
            return self.count_occurences_recursive(node.next, data)

    def is_palindrome_1(self):
        # Solution 1:
        s = ""
        p = self.head 
        while p:
            s += p.data
            p = p.next
        return s == s[::-1]
    
    def is_palindrome_2(self):
        # Solution 2:
        p = self.head 
        s = []
        while p:
             s.append(p.data)
             p = p.next
        p = self.head
        while p:
            data = s.pop()
            if p.data != data:
                return False
            p = p.next
        return True
    
    def is_palindrome_3(self):
        if self.head:
            p = self.head 
            q = self.head 
            prev = []
            
            i = 0
            while q:
                prev.append(q)
                q = q.next
                i += 1
            q = prev[i-1]
        
            count = 1

            while count <= i//2 + 1:
                if prev[-count].data != p.data:
                    return False
                p = p.next
                count += 1
            return True
        else:
            return True

    def is_palindrome(self,method):
        if method == 1:
            return self.is_palindrome_1()
        elif method == 2:
            return self.is_palindrome_2()
        elif method == 3:
            return self.is_palindrome_3()
    

# Example palindromes:
# RACECAR, RADAR

# Example non-palindromes:
# TEST, ABC, HELLO

llist = LinkedList()


llist_2 = LinkedList()
llist_2.append("A")
llist_2.append("B")
llist_2.append("C")

print(llist.is_palindrome(1))
print(llist.is_palindrome(2))
print(llist.is_palindrome(3))
print(llist_2.is_palindrome(1))
print(llist_2.is_palindrome(2))
print(llist_2.is_palindrome(3))
امیدواریم که توانسته باشید هر سه راه را، درک کنید و از آن ها استفاده کنید.

نوشته های مشابه

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

دکمه بازگشت به بالا