جلسه ۷۷: تعیین تعادل در براکت ها در پایتون

در این درس یاد میگیرید که چگونه با استفاده از stack متوجه شوید که یک string، تعادل براکت دارد یا نه.در این درس بررسی میکنیم که مجموعه‌ای از براکت‌ها تعادل دارند یا نه. اینکار را به کمک ساختمان داده‌های stack که درس قبلی یاد گرفته‌ایم انجام میدهیم.اول از همه بررسی کنیم که یک مجموعه براکت تعادل دار چگونه است.یک مجموعه براکت تعادل دار، مجموعه براکتی هستند که تعداد و نوع براکت های باز و بسته با هم مطابفت داشته باشد و همچنین به درسی در یک string از براکت ها قرار بگیرد.

مثال هایی از براکت های تعادل دار

• { }
• { } { }
• ( ( { [ ] } ) )

مثال هایی از براکت هایی که تعادل ندارند

• ( ( )
• { { { ) } ]
• [ ] [ ] ] ]

الگوریتم

اسلاید های زیر را برای اینکه متوجه شوید روش ما برای حل این مسئله چیست، بررسی کنید.

بر اساس چیزی که در بالا دیدید الگوریتم ما بدین صورت است:

• ما روی کاراکترهای string در حلقه حرکت میکنیم.
• اگر یک براکت باز دیدیم، آن را به stack اضافه (push)میکنیم.
• اگر به براکت بسته رسیدیم، آخریم عضو stack را pop میکنیم و با این براکت بسته  مقایسه میکنیم. اگر از یک نوع بودند، مسئله تا اینجا درست است و ادامه میدهیم. در غیر اینصورت متوجه میشویم که براکت ها تعادل ندارند.
• stack در انتهای عملیات باید خالی بشود، اگر هم المان هایی هنوز در stack وجود داشته باشد، مشخص کننده این است که براکت ها تعادل ندارند.

تاکنون مثالی برای برای هر دوی براکت هایی که تعادل دارند و آن هایی که تعادل ندارند را دیدید، حال به بخش موارد خاص میرویم.

موارد خاص

مثال  ((:اگر ما یه یک براکت بسته برسیم ولی المانی در stack برای بررسی نداشتیم چه میشود؟ به عنوان مثال، در موردی که بالا بررسی کردیم، ما هیچ پرانتز بازی نداشتیم، اما ما به پرانتز بسته برخوردیم. در این مورد متوجه شدیم که در string، براکت ها تعادل ندارند. بنابراین ما باید خالی بودن stack را هم بررسی و پیاده‌سازی کنیم.اکنون که ایده مناسبی از الگوریتم بدست آوردید، ما به پیاده‌سازی آن در پایتون میپردازیم.اول از همه با تابع is_paren_balanced شروع میکنیم:

def is_paren_balanced(paren_string):
    s = Stack()
    is_balanced = True
    index = 0

    while index < len(paren_string) and is_balanced:
        paren = paren_string[index]
        if paren in "([{":
            s.push(paren)
        else:
            if s.is_empty():
                is_balanced = False
                break
            else:
                top = s.pop()
                if not is_match(top, paren):
                    is_balanced = False
                    break
        index += 1

    if s.is_empty() and is_balanced:
        return True
    else:
        return False

توضیحات

در خطوط ۴-۲ ما یک stack را ساخته ایم با نام s و دو متغیر index و is_balanxed که در ابتدا به صورت ۰ و True در نظر گرفته ایم.حلقه while در خط ۶ تا زمانی که index کمتر از طول paren-string باشد و is_balanxed هم برابر true باشد، اجرا میشود. اگر هر شرطی که آن را False کند اتفاق افتد، برنامه از حلقه خارج خواهد شد. در حلقه ما روی تک تک اعضای paren_string  بر اساس index حرکت میکنیم و هر المان را در متغیر paren برای کار با آن ذخیره میکنیم.در خط ۸ بررسی میکنیم که متغیر paren آیا از انواع براکت‌های باز  هست یا خیر. اگر بود آن را به stack اضافه میکنیم. اگر هیچ کدام از انواع براکت های باز نبود، بررسی میکنیم که آیا  stack خالی است و مقدار is_balanced را به False تغییر میدهیم. این موضوع کار موارد خاص را که در بخش قبلی گفته شد، پیاده‌سازی می‌کند.اگر stack خالی نبود ما المان بالای پشته را بررسی میکنیم که آیا مقدار parent  که یک براکت بسته است با مقدار بالای stack از یک نوع هستند یا نه. اگر از یک نوع نبودند باز هم is_balanced را False میکنیم.ما مقدار index را برای حرکت‌ها و تکرار های بعدی یکی اضافه میکنیم. حلقه while برنامه را تا زمانی که مقدار index برابر یا مساوی طول paren_string نباشد یا مقدار is_balanced برابر True باشد،تکرار میکند.بعد از اینکه از حلقه خارج شدیم، در خط ۲۱ ما بررسی میکنیم که  stack خالی  و  is_balanced برابر True باشد در اینصورت مقدار True را به عنوان خروجی میدهیم. در غیراینصورت مقدار خروجی False خواهد بود.کدی که در بالا دیدید، یک پیاده‌سازی ساده از این الگوریتم که دیدید بود.اکنون تابع is_match را پیاده‌سازی میکنیم:

def is_match(p1, p2):
    if p1 == "(" and p2 == ")":
        return True
    elif p1 == "{" and p2 == "}":
        return True
    elif p1 == "[" and p2 == "]":
        return True
    else:
        return False

توضیحات

تابع is_match دو کاراکتر را میگیرد یکی p1 و یکی هم p2، و ارزیابی میکند که آیا آن ها از یک نوع براکت هستند یا نه. برای اینکه p1 و p2 از یک نوع باشند، باید p1 یک براکت باز باشد و p1 یک براکت بسته از همان نوع p1. اگر هم این شرایط برای p1 و p2 محیا نبود، خروجی تابع False است.ساده بود. درسته؟در کد زیر شما کل پیاده‌سازی، برای حل این مسئله را میبینید که بررسی میکند آیا در string ورودی، براکت‌ها تعادل دارند یا نه. آن را برای یادگیری بیشتر بررسی کنید!

from stack import Stack

def is_match(p1, p2):
    if p1 == "(" and p2 == ")":
        return True
    elif p1 == "{" and p2 == "}":
        return True
    elif p1 == "[" and p2 == "]":
        return True
    else:
        return False


def is_paren_balanced(paren_string):
    s = Stack()
    is_balanced = True
    index = 0

    while index < len(paren_string) and is_balanced:
        paren = paren_string[index]
        if paren in "([{":
            s.push(paren)
        else:
            if s.is_empty():
                is_balanced = False
                break
            else:
                top = s.pop()
                if not is_match(top, paren):
                    is_balanced = False
                    break
        index += 1

    if s.is_empty() and is_balanced:
        return True
    else:
        return False

print("String : (((({})))) Balanced or not?")
print(is_paren_balanced("(((({}))))"))

print("String : [][]]] Balanced or not?")
print(is_paren_balanced("[][]]]"))

print("String : [][] Balanced or not?")
print(is_paren_balanced("[][]"))

"""
Stack Data Structure.
"""
class Stack():
    def __init__(self):
        self.items = []

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

    def pop(self):
        return self.items.pop()
    
    def is_empty(self):
        return self.items == []
    
    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        
    def get_stack(self):
        return self.items

در درس بعدی، مسئله دیگری را بررسی میکنیم یعنی برعکس کردن یک string و حل این مسئله به کمک stack ها.