بخش ۵: پشته (stack)

پرسش: یک رشته از کمانکهای ( شامل پرانتز، آکولاد، و کروشه) باز و بسته داده شده است(یعنی کاراکترهای (){}[]). برنامه ای بنویسید که مشخص کند آیا کمانکهای باز و بسته منطبق می باشند.

پاسخ: کار را با یک مثال شروع می کنیم. در رشته “()[]{}” کمانکهای از هر نوع باهم منطبق می باشند. دررشته “{}[” کروشه تطابق ندارد. همچنین در رشته “[{]}” تطابق وجود ندارد زیرا قبل از بسته شدن کروشه باز ،یعنی کاراکتر”]”، در اندیس دوم رشته آکولاد بسته قرار دارد. خاصیتی از رشته های با کمانک منطبق می بینیم آن است که در آنها حداقل یک جفت کمانک متوالی ( یعنی یک زوج () یا {} یا []) یافت می شود و اگر چنین کمانکی را از آن حذف کنیم، رشته باقیمانده دارای کمانک منطبق خواهد بود. بنابراین راه حل سادی برای این مساله آن است که هربار یک زوج کمانک را از رشته حذف کنیم. اگر با تکرار این کار به رشته خالی برسیم آنگاه رشته اولیه دارای کمانکهای منطبق بوده است. اگر رشته خالی نباشد و زوج کمانکی در آن یافت نشود آنگاه رشته اولیه دارای کمانکهای منطبق نبوده است. این الگوریتم به ازای هر جفت کمانک متوالی یکبار رشته را جستجو می کند. بنابر این پیچیدگی محاسباتی آن در بدترین حالت (O(n^2 می باشد.


اشکال این روش جستجوی تکراری رشته برای یافتن جفت کمانک های متوالی است. بنابر این به راه حلی فکر می کنیم که از ابتدای رشته تنهای یکبار به سمت انتهای آن حرکت کند و کمانهای بسته شده را بیابد. اینکار باید بگونه ای کمانک های باز منطبق نشده را بخاطر بسپارد و در صورت مشاهده کمانک بسته بررسی کند که تطابق وجود دارد یا خیر. برای بررسی کردن تطابق یک کمانک بسته همیشه باید تنها آخرین کمانک باز استفاده نشده را بیابیم. همچنین با مشاهده یک کمانک باز آن را به انتهای لیست کمانکهای باز اضافه می کنیم. اینگونه اضافه کردن و حذف کردن در لیست کمانک های بازشده رفتار <<First in Last Out>> ساختمان داده پشته را تداعی می کند. بنابر این از مفهوم ساختمان داده پشته برای حل این مساله استفاده می کنیم.

در الگوریتم جدید از سمت چپ رشته شروع می کنیم. بادیدن هر کمانک باز آن را روی پشته می گذاریم. با دیدن هر کمانک بسته عنصر بالای پشته را بررسی می کنیم. اگر روی پشته کمانکی متناسب با کمانک بسته دیده شده باشد (یعنی “)” برای “(” و “}” برای “{” و “]” برای “[” ) به این معناست که یک جفت منطبق دیده ایم. بنابر این کمانک باز بالای پشته را مصرف کرده و آن را حذف می کنیم. درصورتی که کمانک بالای پشته متناسب نباشد یعنی تطابق وجود ندارد. با توجه به اینکه این الگوریتم تنها یکبار رشته راپیمایش می کنیم و هر کمانک باز یکبار رو پشته قرار می گیرد، پیچیدگی محاسباتی این الگوریتم (O(n می باشد.برای اینکه از درستی الگوریتم مطین شویم آن را حداقل روی دو ورودی یکی با رشته منطبق مثلا “{[]}()” و دیگری رشته نامنطبق مثلا “[{]}” بصورت دستی امتحان می کنیم. برای رشته منطبق مشاهد کاراکترها و وضعیت پشته اینچنین خواهند بود:

مثالی از اجرای دسته الگوریتم روی رشته ای با کامنکهای منطبق

با این دلیل که با اتمام رشته پشته خالی است نتیجه می گیریم که همه کمانکهای رشته منطبق می باشند.برای رشته نامنطبق “[{]}” وضعیت پشته چنین خواهد بود.

مثالی از اجرای دسته الگوریتم روی رشته ای با کامنکهای نامنطبق

با توجه به این دومثال بنظر می رسد که الگوریتم می تواند جواب درست را بدهد. بنابر این شروع به نوشتن برنامه می کنیم. ابتدا برای تابع نام مناسبی انتخاب می کنیم. سپس یک پشته، که در پایتون با لیست پیاده می شود، تعریف می کنیم (خط 2).  سپس یک دیکشنری تعریف می کنیم که زوج کاراکترهای کمانکها را مشخص میکند (خط 3). سپس در یک حلقه تکرار (خطوط 4 تا 10) هربار یک کاراکتر را می خوانیم. درصورتی که کاراکتر یک کمانک باز باشد آن را روی پشته می گذاریم. درغیر اینصورت اگر که پشته خالی نباشد و کاراکتر بالای پشته کمانک باز مرتبط به کمانک بسته کنونی باشد (خط 7) آن را از روی پشته حذف می کنیم (خط 8). در غیر این صورت کمانکهای رشته منطبق نمی باشند (خط 10). با اتمام حلقه درصورتی که پشته خالی باشد نتیجه می گیریم که دارای کمانکهای منطبق می باشد (خط 11).

def bracesMatch(s):
	stack = []
	pairs = {'(':')', '{': '}', '[': ']'}
	for w in s:
		if w in pairs:
			stack.append(w)
		elif len(stack)!=0 and pairs[stack[-1]] == w:
			stack.pop()
		else:
			return False
	return len(stack)==0

پرسش: یک لیست از مقادیر داریم. برنامه ای بنویسید که برای هر مقدار در این لیست اولین مقدار بعد از آن که  بزرگتر از آن می باشد را مشخص کند و حاصل را بصورت یک لیست برگرداند. اگر چنین مقدار برای عنصری وجود نداشته باشد مقدار 1- پاسخ خواهد بود.پاسخ: کار را با یک مثال شروع می کنیم. فرض کنیم که لیست زیر داده شده است.


اولین مقدار بعد از 4 درون لیست که بزرگتر از آن می باشد 14 است. اولین عنصر بعد از 3 که بزرگتر از آن می باشد 14 می باشد هیچ عنصری بعد از 14 بزرگتر از آن نمی باشد. بنابر این باید مقدار 1- در آن موقعیت قرارگیرد. لیست زیر پاسخ نهایی می باشد.


برای یافتن پاسخ بهینه از روش جستجوی کامل شروع می کنیم. در این الگوریتم برای هر عنصر لیست از عنصر بعد تا جایی که مقادیر کمتر از آن باشند به سمت انتهای لیست حرکت می کنیم. در بدترین حالت باید تا انتهای لیست را بپیماییم. بنابر این پیچیدگی محاسباتی چنین الگوریتمی O(n2)می باشد. اشکال این روش این است که پیدا کردن جواب برای یک عنصر اطلاع قابل استفاده ای برای یافتن پاسخ برای عنصر بعدی نمی دهد یا از آن استفاده نمی کند. به عنوان مثال با وجود اینکه برای یافتن پاسخ مقدار 4 از روی عناصر بعدی تا 14 رد می شویم، بازهم نمی توانیم بدون پیمایش همه مقادیر تا 14 جواب را برای 3 بیابیم. بنابر این بررسی می کنیم که آیا شروع از انتهای لیست امکان استفاده از اطلاعات عناصر پیمایش شده را فراهم می کند. به عنوان مثال فرض کنیم که از انتهای لیست تا عنصر با مقدار 14 را پیموده و پاسخ را برای آنها یافته ایم. با توجه به اینکه همه مقادیر بعد از 14 (یعنی  13، 7، و 12) از آن کوچکترند مطمین خواهیم بود که برای یافتن اولین عنصر بزرگتر از عناصر سمت چپ 14 نیازی به استفاده از آنها نمی باشد. زیرا یا 14 از آنها بزرگتر است (که در این صورت 14 جواب می باشد) یا 14 کوچکتر از آنهاست که در این صورت باقی عناصر نیز کوچکتر از آن می باشند. بنابراین با پیمایش از راست به چپ لیست تنها کافیست عناصر بالارونده بعدی را در یک لیست جدا نگه داریم. برای ساختن چنین لیستی می توانیم از ساختمان داده پشته استفاده کنیم.

بنابر این از سمت راست لیست و با یک پشته خالی شروع می کنیم و به سمت چپ لیست حرکت می کنیم. با دیدن هر عنصر جدید آن را با عنصر بالای پشته مقایسه می کنیم. اگر عنصر بالای پشته بزرگتر از آن است جواب را یافته ایم. درغیر این صورت آنقدر از بالا پشته برمی داریم که به عنصری بزرگتر از عنصر جدید برسیم یا اینکه پشته خالی شود. اگر پشته خالی شد مقدار 1- پاسخ است. در غیر این صورت مقدار بالای پشته پاسخ می باشد. با توجه به اینکه مقدار جدید کوچکتر از بالای پشته است آن را به بالای پشته اضافه می کنیم و محتوای پشته همچنان بالارونده باقی خواهد ماند. این الگوریتم پیشنهادی را روی مثال فوق اجرا می کنیم تا مطمین شویم که درست کار میکند. در مثال زیر به علت کمبود فضا تنها تا عنصر با مقدار 1 را پیموده ایم. یادآور می شویم که روند اجرا از راست به چپ نمایش داده شده است.


بنابر این الگوریتم  روی مثال داده شده درست کار می کند. سپس کد آن را می زنیم.درحین نوشتن برنامه کاری که هرخط می کند را توضیح می دهیم. ابتدا نامی مناسب و پارامتر ورودی تابع را تعریف می کنیم (خط 1). سپس یک پشته خالی تعریف می کنیم (خط 2). بعد یک لیست به طول لیست ورودی تعریف می کنیم که نتیجه را برای هر عنصر نگه می دارد. به هر عنصر مقدار اولیه 1- می دهیم (خط 3). سپس در یک حلقه تکرار از انتهای به سمت ابتدای لیست حرکت می کنیم (خط 5). چنانچه پشته خالی باشد آنگاه مقدار نتیجه 1- (یعنی پیشفرض عناصر لیست نتیجه) می باشد. بنابر این نیاز به تغییری در لیست نتیجه نیست اما این عنصررا  باید روی پشته بگذاریم (خطوط 7 و 8). چنانچه پشته خالی نباشد تا زمانی که عنصری بزرگتر از عنصر i ام لیست در بالای پشته نبینیم از بالای پشته برداریم (خط 9). عنصر بالای پشته، درصورت وجود، مقدار بزرگترین عنصر بعد از عنصر iام را مشخص می کند (خط 12). سپس عنصر iام را روی پشته قرار می دهیم تا در محاسبه نتیجه برای عنصر بعدی (سمت چپ آن) استفاده نماییم (خط 13). در انتها لیست نتیجه را برمی گردانیم (خط 14).

def nextGreater(nums):
	stack = []
	res = [-1] * len(nums)

	for i in range(len(nums)-1, -1, -1):
		if not stack:
			stack.append(nums[i])
		else:
			while s and stack[-1]<=nums[i]:
				stack.pop()

			res[i] = stack[-1] if stack else -1
			stack.append(nums[i])
	return res





GiottoPress by Enrique Chavez