بخش ۴: رشته (string)

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

پرسش: برنامه ای بنویسید که دو رشته که نشان دهنده نسخه های یک نرم افزارند را در یافت نماید. اگر اولین رشته نسخه جدید تری باشد مقدار 1، چنانچه دومی جدیدتر باشد مقدار 1-، و در صورت مساوی بودن 0 را برگرداند.

پاسخ: کار را با چند مثال شروع می کنیم (فهم مساله). اگریک نسخه نرم افزاری “1.02” و نسخه دیگر آن “1.02.1” باشد آنگاه بخش آخر رشته دوم (یعنی “1.”) نشان می دهد که ورژن “1.02.1” مربوط به ویرایش اول از نسخه “1.02” است و جدیدتر است. بنابر اگر “1.02” ورودی اول این برنامه و “1.02.1” ورودی دوم باشد این تابع باید مقدار 1- را برگرداند. اگر رشته اولی “1.2” باشد باز هم نتیجه 1- است زیرا صفر در بخش دوم (یعنی 02) در مقدار عددی ورژن تاثیری ندارد. اگر رشته دومی “1.02.0” باشد در واقع این دو ورژن یکی هستند.با توجه به مثال های بالا واضح است که استفاده از عملگرهای مقایسه ای (یعنی ==, > , <) پاسخ صحیح را برای این سوال نمی دهد، زیرا مقایسه رشته ای حالتهای شامل 0 که در مثالها گفتیم را بدرستی مدیریت نمی کنند (یافتن ایراد راه حل).


بنابر این یک راه حل درست باید مقادیر عددی بخش های متناظر از دو رشته را با هم مقایسه نماید نه خود رشته ها را (ارایه راه حل بهتر).  به عنوان مثال، رشته “1.2” را می توانیم بصورت لیستی از مقادیر صحیح [2, 1] در نظر بگیریم و رشته “1.02.1” را بصورت یک لیست از مقادیر صحیح [1, 2, 1] در نظر داشته باشیم. با مقایسه لیست ها از چپ به راست اولین نقطه ای که دو لیست با هم متفاوت باشند مشخص می کند که کدام یک بزرگتر است. در صورتی که دو لیست تفاوتی نداشته باشند به این معنا است که دو نسخه نرم افزار با هم برابرند.

شروع به پیاده سازی الگوریتم می کنیم و همزمان بانوشتن برنامه باید چیزهایی که در ذهنمان می گذرد را برای مصاحبه کننده توضیح دهیم (فکرمان را داد بزنیم). مثلا <<یک تابع با پارامترهای مناسب تعریف می کنیم. این تابع نیاز به دو پارامتر برای گرفتن ورژنهای ورودی دارد (خط 1). سپس از تابع split استفاده می کنیم که بخشهای هر ورژن را بدهد (خط 2 و 3). البته اینجا می توانستیم قبل این کارها چک کنیم که آیا مقدار پارامتر version1 تهی (None) هست.>> می توانیم از مصاحبه کننده بپرسیم که آیا لازم هست که این شرط را بررسی کنیم. این سوال ما نشان می دهد که ما حالتهای ورودی در یک برنامه واقعی را می شناسیم و مطلعیم که ممکن است ورودی شکل مورد نظر ما را نداشته باشد. بررسی این حالت خیلی ساده است و پیشنهاد می کنیم که آن را اضافه کنیم. در اینجا برای اینکه برنامه کوتاه و قابل فهم باشد این شرط را نیاورده ایم. <<پس از آنکه بخشهای ورژن را در آوردیم باید آنها را به عدد صحیح تبدیل کنیم. برای این کار از تابع map  استفاده می کنیم که در واقع تک تک مقادیر لیست (بخش های نسخه) را به عدد صحیح تبدیل می کند (خط 2). این کار را برای رشته دوم هم انجام می دهیم (خط 3).>>

حالا باید دو لیست را با هم مقایسه کنیم. برای این کار می توانیم یک حلقه تکرار بنویسیم که سراغ تک تک عناصر لیست می رود تا جایی که (۱) یکی از مقادیر متناظر مقایسه شده از دیگری بزرگتر باشد که در این صورت نتیجه را می دانیم، یا (۲) یا به انتهای لیست کوچکتر برسیم. حالت دوم به این معناست که همه مقادیر دو لیست تا اینجای کار با هم مساوی می باشند. شاید بنظر برسی که پس از خروج از حلقه باید اندازه لیست ها را با هم مقایسه کنیم تا لیست بزرگتر را به عنوان نسخه بزرگتر اعلام کنیم اما در مورد این مساله خاص باید این را در نظر بگیریم که لیست طولانی تر الزاما بزرگتر نیست. به این دلیل که ممکن است باقی مانده عناصر لیست بزرگتر همگی صفر باشند. مثلا لیست های مرتبط با رشته های “1.2” و “1.2.0” عبارتند از [2, 1] و [0, 2, 1]. با وجود اینکه تا عنصر اندیس 1 این دو لیست با هم برابرند و لیست دوم طولانی تر است، به این دلیل که مقادیر از اندیس 1 به بعد در لیست دوم صفر است، تفاوتی را در نسخه نرم افزار ایجاد نمی کند. بنابر این این دو لیست با هم برابرند.

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

برای اینکه از بررسی شرطهای اضافی خلاص شویم، از یک تکنیک خوب استفاده می کنیم. در این تکنیک دو لیست را ابتدا هم اندازه می کنیم و سپس آنها را مقایسه می کنیم. بنابراین در خط 5 ابتدا تفاوت طول در لیست را محاسبه می کنیم. سپس با استفاده از امکانات زبان پایتون به راحتی تعداد صفر مناسب به انتها رشته ها اضافه می کنیم (خطوط 6 و 7). در انتها دو لیست را مستقیما با عملگرهای مقایسه ای مقایسه می کنیم (خطوط 9 و 11) و نیازی به نوشتن حلقه تکرار برای مقایسه نخواهیم داشت. نهایتا در خط نتیجه را برمی گردانیم.

def compareVersion(version1, version2):
	v1 = map(int, version1.split("."))
	v2 = map(int, version2.split("."))

	d  = len(v1)-len(v2)
	v1 += [0] * (-d)
	v2 += [0] * (d)

	if v1 == v2:
		return 0
	return 1 if v1 > v2 else -1


تحلیل سرعت برنامه: یک اشتباه رایج آن است که تصور کنیم این برنامه دارای پیچیدگی محاسباتی (O(1 است به این خاطر که هیچ حلقه یا فراخوانی بازگشتی ای وجود ندارد. اما باید هزینه توابع موجود و از پیش تعریف شده در زبان برنامه نویسی را نیز جزو هزینه برنامه خود محاسبه کنیم. برنامه بالا از split، map و مقایسه لیست ها استفاده می کند که دارای پیچیدگی محاسباتی (O(nاست که در آن n مجموع طول دو رشته است.  بنابر این پیچیدگی محاسباتی این الگوریتم (O(n می باشد.

پرسش: برنامه ای بنویسید که ترتیب کلمات درون یک رشته را بالعکس می کند.پاسخ: کار را با چند مثال شروع می کنیم. اگر رشته ورودی “Hello world” باشد آنگاه برنامه باید مقدار “world Hello” را برگرداند. با کمی فکر کردن متوجه می شویم که اگر یک لیست از کلمات متوالی درون رشته بسازیم و لیست را برعکس کنیم آنگاه ترتیب مطلوب کلمات در لیست بدست می آید. با وصل کردن کلمات درون لیست می توانیم رشته مورد نظر را بسازیم. قطعه کد زیر این کار را انجام می دهد.

def reverseWords(s):
	" ".join(reversed(s.split()))


اما مصاحبه کننده از ما می خواهد که رشته ورودی “Hello      World” را روی تست کنیم. با دنبال کردن برنامه با داده ورودی، خروجی”World Hello” تولید می شود که پاسخ مطلوب نیست زیرا چندین کاراکتر فاصله بین دو کلمه از بین رفته اند. این اتفاق به دلیل نحوه کار تابع split رخ می دهد که رشته را از نقطه فاصله می شکند ولی فاصله ها را در حاصل دخیل نمی کند. اگر بخواهیم این الگوریتم را تصحیح کنیم باید از روشی برای جداکردن کلمات استفاده نماییم که برخلاف split، فاصله ها را نیز در لیست خروجی در اختیار بگذارد. خوشبختانه راه حلی برای این کار وجود دارد و آن استفاده از تابع split درون کتابخانه عبارات باقاعده (regular expression) برای جداکردن رشته در نقاط فاصله است. این روش به ازای هر فاصله های یک رشته خالی در لیست حاصل ایجاد می کند. ممکن است در زمان پاسخگویی نحوه استفاده از عبارات باقاعده را ندانیم اما مطرح کردن این گزینه ،حتی اگر نتوانیم آن را پیاده کنیم، برای مصاحبه کننده نشان دهنده آن است که شما ذهنی باز دارید و گزینه های مختلف برای حل مساله را در نظر می گیرید. این یکی از مهمترین خصوصیات یک برنامه نویس خوب است.اگر هم که حضور ذهن برای نوشتن عبارات باقاعده داشته باشیم می توانیم جواب درست زیر را پیاده کنیم.

import re
def reverseWords(s):
	" ".join(reversed(re.split('\s', s)))


اما اگر ایده استفاده از عبارت با قاعده به ذهنمان نرسید یا مصاحبه کننده از ما بخواهد که از این امکان استفاده نکنیم، باید یک ایده دیگر بزنیم و مساله را به روش دیگری حل کنیم. با دقت در ورودی و خروجی مثال متوجه می شویم که خروجی در واقع معادل با رشته ایست که نسبت به رشته اول برعکس شده و هر کلمه نیز پس از آن برعکس شده است. مثلا با عکس کردن رشته “Hello      World” به رشته “dlroW      olleH” می رسیم. سپس با برعکس کردن هریک از کلمات در جای خود به رشته نهایی “World Hello” دست خواهیم یافت. بنابر این الگوریتم درست کار می کند. با اندکی تامل بیشتر متوجه می شویم که برعکس کردن رشته عملی است که در هر دو مرحله الگوریتم انجام می شود.

بنابر این در حل برنامه تابعی بنویسیم که بتواند یک رشته را برعکس کند. برای اینکه بتوانیم عمل برعکس کردن را روی کلمه ها هم انجام دهیم باید تابع را بصورتی بنویسیم که بتواند هر زیر رشته دلخواه بین اندیس های داده شده از یک رشته را در محل برعکس کند.با این ذهنیت شروع به نوشتن برنامه می کنیم. همانطور که برنامه را می نویسیم خطوط برنامه را برای مصاحبه کننده توضیح می دهیم. ابتدا نام مناسبی برای تابع در نظر می گیریم. این تابع یک رشته را به عنوان ورودی می گیرد. در ادامه ابتدا رشته را به لیستی از کاراکتر ها تبدیل می کنیم (خط 2). این کار را به این دلیل انجام می دهیم که در زبان پایتون رشته یک ساختمان داده تغییر ناپذیر (immutable) می باشد. در ادامه یک تابع کمکی می نویسیم که اندیس چپ و راست یک زیر لیست را می گیرد و همه عناصر لیست در آن بازه را برعکس می کند (خطوط 4 تا 7). از این تابع هم برای برعکس کردن کل رشته (خط 9) و هم برعکس کردن کلمات (خطوط 10 تا 15) استفاده می کنیم. در انتها کاراکترهای لیست را به هم متصل می کنیم تا رشته را بسازیم.

def reverseWords(s):
	c = list(s)
	def inverse_helper(left, right):
		while (left<right):
			c[left], c[right] = c[right], c[left]
			left, right = left+1, right-1
			
	inverse_helper(0, len(s)-1)
	p = 0
	for i in range(len(s)):
		if c[i] == ' ':
			inverse_helper(p, i-1)
			p = i+1
	inverse_helper(p, len(s)-1)
	return "".join(c)


تحلیل سرعت برنامه: این برنامه عملا یکبار رشته را می پیماید تا آن را برعکس می کند و سپس کلمات درون رشته را با یکبار پیمایش آنها برعکس می کند. بنابر این پیچیدگی محاسباتی این الگوریتم(O(n می باشد.

پرسش: یک رشته از پرانتزهای باز و بسته داده شده است. برنامه ای بنویسید که مشخص کند آیا پرانتزهای باز و بسته با هم منطبق می باشند.

پاسخ: حل مساله را با چند مثال شروع می کنیم تا مطمین شویم آن را بطور کامل درک کرده ایم.در رشته “())” حتی تعداد پرانتزهای باز و بسته یکی نیست، چه برسد به انطباق دوبدوی پرانتزهای باز و بسته. در رشته “())(” تعداد پرانتزهای باز و بسته یکی است اما همچنان پرانتزها برهم منطبق نمی باشند. به عنوان مثال پرانتز اولیه بسته مطابق با هیچ پرانتز باز سمت چپ آن نیست.  به عنوان مثال های مثبت، در رشته های “(())()” و “(()((())))” پرانتز های باز و بسته با هم منطبق می باشند.

در مورد این مساله الگوریتم جستجوی کامل مفهوم روشنی ندارد. بنابر این بجای آن تلاش می کنیم که یک الگوریتم ساده ارایه نماییم که مستقیما مبتنی بر خاصیت ذاتی یک رشته پرانتز-منطبق می باشد. خاصیت ذاتی یک پرانتز بندی منطبق آن است که اگر یک زوج منطبق (یعنی ‘()’) آن را حذف کنیم آنگاه رشته باقیمانده نیز پرانتزبندی منطبق دارد. همچنین اگر داخلی ترین زوج پرانتز باز و بسته (یعنی ‘()’) در یک رشته نامنطبق را حذف کنیم، آنگاه پرانتزهای رشته باقیمانده نامنطبق خواهند بود. مثلا با یک بار حذف یک زوج منطبق پرانتز رشته “())(()” به رشته “())(” می رسیم که همچنان یک رشته نامنطبق است. بنابر این یک الگوریتم مبتنی بر این خاصیت ابتدا تعداد پرانتزهای باز و بسته را می شمارد. اگر تعداد آنها متفاوت باشد رشته نتیجه می گیرد که پرانتزها نامنطبق اند. در گام بعد، درصورتی که تعداد پرانتزهای باز و بسته برابر باشند هر بار یک زیر رشته “()” را از داخل رشته حذف می کنیم و این کار را تا زمانی که (۱) رشته تمام شود (برای رشته منطبق) یا، (۲) دیگر زیر رشته “()” پیدا نشود (در رشته نامنطبق) تکرار می کنیم. این الگوریتم در بدترین حالت دارای پیچیدگی محاسباتی (O(n^2 می باشد زیرا برای یافتن هر زیر رشته “()” باید بطور متوسط از ابتدا تا وسط رشته را بپیماییم. در این لحظه می توانیم الگورتیم را روی مثالهای داده شده تست کنیم تا مطین شویم که درست کار می کند.

با وجود این که الگوریتم درست است اما کند است. علت کندی این الگوریتم آن است که کارهای تکراری انجام می دهد. بخصوص اینکه برای پیداکردن زوج پرانتز باز و بسته جدید هربار از ابتدای رشته دوباره شروع به جستجو میکند. برای رفع این مشکل الگوریتم را تغییر می دهیم بگونه ای که هر بار مجبور به جستجوی مجدد از ابتدای رشته نباشد. برای این کار ازابتدای رشته شروع به حرکت می کنیم تا اولین پرانتز بسته (یعنی “(“) را در اندیس Y در رشته پرانتزها بیابیم. سپس به عقب حرکت می کند تا اولین پرانتز باز (یعنی “)”) قبل آن را در نقطه X بیابیم. به این دلیل که پرانتزهای در موقعیت X و Y زوج منطبق هستند دیگر کاری با آنها نداریم. در نتیجه یا آنها را از رشته حذف می کنیم یا جای آنها را با کاراکترهای الکی (غیر از پرانتز مثلا *) پر می کنیم تا دفعات بعد با آنها کار نداشته باشیم.

سپس از اندیس Y+1 کار را برای جستجوی پرانتز بسته (یعنی “(“) بعدی ادامه می دهد. و این کار را تا منطبق کردن همه پرانتزهای بسته و باز انجام می دهد. به این ترتیب برای یافتن پرانتزهای بسته تنها باید یکبار بصورت کامل رشته را می پیماییم. برای یافتن پرانتزهای باز در بدترین حالت باید تمار کاراکترهای سمت چپ اندیس Y را تا ابتدای رشته بررسی کنیم. بنابر این چنین پیچیدگی محاسباتی این الگوریتم همچنان ((O(n^2 خواهد بود.

قسمت کند الگوریتم فوق همان یافتن موقعیت پرانتز باز (یعنی “)”) استفاده نشده ای است که سمت چپ یک پرانتز بسته در موقعیت Y است. اما با توجه به صورت مساله، آیا واقعا نیاز به یافتن اندیس موقعیت این پارانتز باز داریم یا اینکه کافیست مطمین شویم که یک پرانتز باز استفاده نشده در سمت چپ Y وجود دارد؟ پاسخ آن است که در این مساله نیاز به برگرداندن لیست زوج پرانتز های منطبق نداریم و بنابر این کافی است که مطمین باشیم که یک پرانتز باز استفاده نشده در سمت چپ Y هست اما به لازم نداریم محل آن را بدانیم. این نکته راه را برای یافتن الگوریتم بهبود یافته راحت می کند.

بنابر این تنها کافی است بدانیم که آیا حداقل یک پرانتز کافی منطبق نشده در سمت چپ یک پرانتز بسته در موقعیت Y وجود دارد. به عنوان مثال در رشته “())(()” با رسیدن به اولین پرانتز بسته یک پرانتز باز جهت تطبیق با آن در سمت چپش وجود دارد. در مرحله بعد سراغ پرانتز بسته بعدی (یعنی اندیس 3 در رشته) می رویم. در این صورت تعداد صفر پرانتز باز استفاده نشده در سمت چپ آن وجود دارد. بنابر این زوجی منطبقی برای پرانتز بسته در اندیس 3 وجود ندارد و در نتیجه رشته دارای پرانتز منطبق نیست.

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

با توجه با اینکه در این الگوریتم تنها یکبار هر کاراکتر رشته بطول n را مشاهده می کنیم، پیچیدگی محاسباتی آن (O(n می باشد.

در یک مصاحبه واقعی با اجرای الگوریتم روی رشته های مثال بررسی می کنیم که آیا الگوریتم می تواند به درستی پاسخ بدهد. بنابراین شروع الگوریتم را پیاده می کنیم.

سپس شروع به پیاده سازی الگوریتم می کنیم و همزمان خطوط برنامه را توضیح می دهیم. ابتدا نام مناسبی برای تابع و ورودی آن انتخاب می کنیم. سپس یک شمارنده برای تعداد پرانتزهای باز و یک شمارنده برای حلقه و موقعیت پیشروی در رشته در نظر می گیریم. سپس روی کاراکترهای رشته با استفاده یک حلقه تکرار حرکت می کنیم. تا زمانی که به انتهای رشته نرسیده ایم و  تعداد پرانتزهای منطبق نشده بزرگتر مساوی (یعنی بزرگتر یا مساوی) صفر است به حرکت در حلقه ادامه می دهیم (خط 3). در ادامه متناسب با کاراکتر i ام رشته شمارنده count را یک واحد افزایش یا کاهش می دهیم. درواقع اگر این کاراکتر پرانتز باز باشد یک واحد به تعداد شمارنده پرانتزهای باز اضافه می کنیم. درصورتی که پرانتز بسته ای ببینیم در واقع باید یکی از پرانتزهای باز را استفاده کنیم و درنتیجه یکی از شمارنده پرانتزهای باز کم می کنیم (خط 4). این خط را با استفاده از ساختار شرطی یک خطی نوشته ایم اما می توانستیم آن را با ساختار شرطی معمولی هم بنویسیم. در مورد این مساله این کار برنامه را خواناتر کرده است.

سپس با افزایش شمارنده حلقه اماده پردازش عنصر بعد رشته می شویم (خط 5).  حلقه وقتی تمام می شود که یا به انتهای حلقه رسیده باشیم و یا اینکه شمارنده تعداد پرانتزهای باز کمتر از صفر شده باشد. این حالت در صورتی رخ می دهد که تعداد پرانتزهای باز در نقطه ای از اجرای حلقه صفر باشد ولی کاراکتر بعدی پرانتز بسته باشد. در این صورت شمارنده count برابر 1- خواهد شد. به هر حال اگر بعد از اتمام اجرای حلقه مقدار متغیر count صفر باشد آنگاه تطابق بین پرانتزهای وجود داشته است. اگر مقدار count بزرگتر از صفر باشد یعنی تعداد پرانتزبازهای رشته بیش از پرانتزهای بسته بوده است. اگر مقدار count کمتر از صفر باشد به این معنا است که در نقطه ای از رشته تعداد پرانتزهای باز سمت چپ پرانتز بسته ناکافی بوده است. به هر حال اگر مقدار صفر نباشد آنگاه مقدار False را برمی گردانیم. درصورتی که مقدار count صفر باشد True را برمی گردانیم. این یعنی not count پاسخ درست را می دهد (خط 6).

def parenthesesMatch(str):
	count, i = 0, 0
	while i < len(str) and 0<=count:
		count += 1 if str[i] == '(' else -1
		i += 1
	return not count





GiottoPress by Enrique Chavez