عنوان کامل: الگوریتم بررسی متعادل بودن پارانتز باز و بسته در یک عبارت با استفاده از پشته
داشتم تجربه مصاحبه یکی از دوستان را میخواندم که یک سوالی پرسیده بودند که خیلی زمان از بررسی موضوع مشابهی برام گذشته بود بنابراین تصمیم گرفتم یک فلش بک به این موضوع داشته باشم و با شما به اشتراک بذارم.
فرض کنید یک رشته بصورت زیر داشته باشیم:
[()]{}{[()()]()}
برنامه ای بنویسید که بررسی کند آیا ترتیب باز و بسته بودن آنها صحیح است یا خیر؟
مثال:
Input: exp = “[()]{}{[()()]()}” Output: Balanced Input: exp = “[(])” Output: Not Balanced
الگوریتم:
1- یک پشته برای کاراکتر ها با نام S تعریف می کنیم
2- عبارت وارد شده را از ابتدا کاراکتر به کاراکتر شروع به پیمایش می کنیم
3- اگر کاراکتر خوانده شده از نوع پارانتز باز (براکت باز یا کروشه باز یا ...) باشد آن را به پشته پوش می کنیم
4- اگر کاراکتر خوانده شده از نوع پارانتز بسته باشد یک آیتم از پشته برمیداریم (پاپ) و بررسی می کنیم که آن با کاراکتر خوانده شده تطابق داشته باشد
یعنی مثلا اگر از نوع پارانتز بود، پارانتز باز با پارانتز بسته مطابقت دارد در غیر اینصورت اشتباه است
5- بعد از اینکه کل عبارت پیمایش شد اگر پارانتز بازی در پشته مانده باشد نتیجه میگیریم که عدم تطابق وجود دارد
در تصویر زیر نمای استک و نحوه پردازش رشته را برای یک مثال مشاهده می کنید:
خب بریم این الگوریتم را با زبان پایتون 3 پیاده کنیم:
Output: Balanced
