یک برنامه نویس خوب باید بتواند یک دیالوگ دورنی در ذهن خود بسازد. حل مسایل برنامه نویسی با روش بهبود مرحله به مرحله کمک می کند این دیالوگ را بسازید، با ذهن خودتان حرف بزنید، و دستش را بگیرید تا به مقصد برسانید.
پرسش: یک رشته از پرانتزهای باز و بسته داده شده است. برنامه ای بنویسید که مشخص کند آیا پرانتزهای باز و بسته با هم منطبق می باشند.
پاسخ: حل مساله را با چند مثال شروع می کنیم تا مطمین شویم آن را بطور کامل درک کرده ایم.در رشته "())" حتی تعداد پرانتزهای باز و بسته یکی نیست، چه برسد به انطباق دوبدوی پرانتزهای باز و بسته. در رشته "())(" تعداد پرانتزهای باز و بسته یکی است اما همچنان پرانتزها برهم منطبق نمی باشند. به عنوان مثال پرانتز اولیه بسته مطابق با هیچ پرانتز باز سمت چپ آن نیست. به عنوان مثال های مثبت، در رشته های "(())()" و "(()((())))" پرانتز های باز و بسته با هم منطبق می باشند.
در مورد این مساله الگوریتم جستجوی کامل مفهوم روشنی ندارد. بنابر این بجای آن تلاش می کنیم که یک الگوریتم ساده ارایه نماییم که مستقیما مبتنی بر خاصیت ذاتی یک رشته پرانتز-منطبق می باشد. خاصیت ذاتی یک پرانتز بندی منطبق آن است که اگر یک زوج منطبق (یعنی '()') آن را حذف کنیم آنگاه رشته باقیمانده نیز پرانتزبندی منطبق دارد. همچنین اگر یک زوج پرانتز باز و بسته (یعنی '()') در یک رشته نامنطبق را حذف کنیم، آنگاه پرانتزهای رشته باقیمانده نامنطبق خواهند بود. مثلا با یک بار حذف یک زوج منطبق پرانتز رشته "())(()" به رشته "())(" می رسیم که همچنان یک رشته نامنطبق است. بنابر این یک الگوریتم مبتنی بر این خاصیت ابتدا تعداد پرانتزهای باز و بسته را می شماریم. اگر تعداد آنها متفاوت باشد نتیجه می گیریم که پرانتزها نامنطبق اند. درصورتی که تعداد پرانتزهای باز و بسته برابر باشند، در گام بعد هر بار یک زیر رشته "()" را از داخل رشته حذف می کنیم و این کار را تا زمانی که (۱) رشته تمام شود (برای رشته منطبق) یا، (۲) دیگر زیر رشته "()" پیدا نشود (در رشته نامنطبق) تکرار می کنیم. این الگوریتم در بدترین حالت دارای پیچیدگی محاسباتی (O(n^2 می باشد زیرا برای یافتن هر زیر رشته "()" باید بطور متوسط از ابتدا تا وسط رشته را بپیماییم. در این لحظه می توانیم الگورتیم را روی مثالهای داده شده تست کنیم تا مطین شویم که درست کار می کند.
با وجود این که الگوریتم درست است اما کند است. علت کندی این الگوریتم آن است که کارهای تکراری انجام می دهد. بخصوص اینکه برای پیداکردن زوج پرانتز باز و بسته جدید هربار از ابتدای رشته دوباره شروع به جستجو میکند. برای رفع این مشکل الگوریتم را تغییر می دهیم بگونه ای که هر بار مجبور به جستجوی مجدد از ابتدای رشته نباشد. برای این کار ازابتدای رشته شروع به حرکت می کنیم تا اولین پرانتز بسته (یعنی "(") را در اندیس Y در رشته پرانتزها بیابیم. سپس به عقب حرکت می کند تا اولین پرانتز باز (یعنی ")") قبل آن را در نقطه X بیابیم. به این دلیل که پرانتزهای در موقعیت X و Y زوج منطبق هستند دیگر کاری با آنها نداریم. در نتیجه یا آنها را از رشته حذف می کنیم یا جای آنها را با کاراکترهای الکی (غیر از پرانتز مثلا *) پر می کنیم تا دفعات بعد با آنها کار نداشته باشیم.
سپس از اندیس Y+1 کار را برای جستجوی پرانتز بسته (یعنی "(") بعدی ادامه می دهد. و این کار را تا منطبق کردن همه پرانتزهای بسته و باز انجام می دهد. به این ترتیب برای یافتن پرانتزهای بسته تنها باید یکبار بصورت کامل رشته را می پیماییم. برای یافتن پرانتزهای باز در بدترین حالت باید تمار کاراکترهای سمت چپ اندیس Y را تا ابتدای رشته بررسی کنیم. بنابر این چنین پیچیدگی محاسباتی این الگوریتم همچنان (O(n^2 خواهد بود.
قسمت کند الگوریتم فوق همان یافتن موقعیت پرانتز باز (یعنی ")") استفاده نشده ای است که سمت چپ یک پرانتز بسته در موقعیت Y است. اما با توجه به صورت مساله، آیا واقعا نیاز به یافتن اندیس موقعیت این پرانتز باز داریم یا اینکه کافیست مطمین شویم که یک پرانتز باز استفاده نشده در سمت چپ Y وجود دارد؟ پاسخ آن است که در این مساله نیاز به برگرداندن لیست زوج پرانتز های منطبق نداریم و بنابر این کافی است که مطمین باشیم که یک پرانتز باز استفاده نشده در سمت چپ Y هست اما لازم نداریم اندیس آن را بدانیم. این نکته راه را برای یافتن الگوریتم بهبود یافته باز می کند.
بنابر این تنها کافی است بدانیم که آیا حداقل یک پرانتز کافی منطبق نشده در سمت چپ یک پرانتز بسته در موقعیت Y وجود دارد؟ به عنوان مثال در رشته "())(()" با رسیدن به اولین پرانتز بسته در اندسی 1، یک پرانتز باز جهت تطبیق با آن در سمت چپش وجود دارد. در مرحله بعد سراغ پرانتز بسته بعدی (یعنی اندیس 2 در رشته) می رویم. در این صورت تعداد صفر پرانتز باز استفاده نشده در سمت چپ آن وجود دارد. بنابر این زوجی منطبقی برای پرانتز بسته در اندیس 2 وجود ندارد و در نتیجه پرانتزهار رشته منطبق نیستند.
بنابر این یک شمارنده کافی است تا تعداد پرانتز های بسته استفاده نشده در سمت چپ نقطه Y را بدانیم. هرگاه یک پرانتز بسته مشاهده می کنیم یک پرانتز باز را استفاده می کنیم و در نتیجه یک واحد از مقدار شمارنده می کاهیم. با مشاهده یک پرانتز باز یک واحد به این شمارنده اضافه می کنیم. اگر در حین حرکت روی رشته با مشاهده پرانتز بسته در اندیس Y، مقدار این شمارنده صفر باشد، آنگاه نتیجه می گیریم که پرانتزهای رشته منطبق نیستند. همچنین اگر حرکت روی رشته تمام شود و در نهایت مقدار شمارنده بیش از صفر باشد نشان دهنده آن است که تعداد پرانتزهای باز بیش از پرانتز بسته می باشد و در نتیجه بازهم پرانتزهای رشته منطبق نیستند. در غیر این دوحالت، پرانتزها منطبقند.
با توجه با اینکه در این الگوریتم تنها یکبار هر کاراکتر رشته بطول n را مشاهده می کنیم، پیچیدگی محاسباتی آن (O(n می باشد.
در یک مصاحبه واقعی با اجرای الگوریتم روی رشته های مثال بررسی می کنیم که آیا الگوریتم می تواند به درستی پاسخ بدهد. سپس شروع به پیاده سازی الگوریتم می کنیم.
همزمان با نوشتن برنامه خطوط برنامه را توضیح می دهیم. ابتدا نام مناسبی برای تابع و ورودی آن انتخاب می کنیم (خط 1). سپس یک شمارنده برای تعداد پرانتزهای باز و یک شمارنده برای حلقه و موقعیت پیشروی در رشته در نظر می گیریم (خط 2). سپس روی کاراکترهای رشته با استفاده از یک حلقه تکرار حرکت می کنیم. تا زمانی که به انتهای رشته نرسیده ایم و تعداد پرانتزهای منطبق نشده بزرگتر مساوی (یعنی بزرگتر یا مساوی) صفر است به حرکت در حلقه ادامه می دهیم (خط 3). در ادامه متناسب با کاراکتر i ام رشته شمارنده count را یک واحد افزایش یا کاهش می دهیم. درواقع اگر این کاراکتر پرانتز باز باشد یک واحد به تعداد شمارنده پرانتزهای باز اضافه می کنیم. درصورتی که پرانتز بسته ای ببینیم در واقع باید یکی از پرانتزهای باز را استفاده کنیم و درنتیجه یکی از شمارنده پرانتزهای باز کم می کنیم (خط 4). این خط را با استفاده از ساختار شرطی یک خطی نوشته ایم اما می توانستیم آن را با ساختار شرطی معمولی هم بنویسیم. در مورد این مساله ساختار شرطی یک خطی برنامه را خواناتر کرده است.
سپس با افزایش شمارنده حلقه آماده پردازش عنصر بعد رشته می شویم (خط 5). حلقه وقتی تمام می شود که یا به انتهای حلقه رسیده باشیم و یا اینکه شمارنده تعداد پرانتزهای باز کمتر از صفر شده باشد. این حالت در صورتی رخ می دهد که تعداد پرانتزهای باز در نقطه ای از اجرای حلقه صفر باشد ولی کاراکتر بعدی پرانتز بسته باشد. در این صورت شمارنده count برابر 1- خواهد شد. به هر حال اگر بعد از اتمام اجرای حلقه مقدار متغیر count صفر باشد آنگاه تطابق بین پرانتزهای وجود داشته است. اگر مقدار count بزرگتر از صفر باشد یعنی تعداد پرانتزبازهای رشته بیش از پرانتزهای بسته بوده است. اگر مقدار count کمتر از صفر باشد به این معنا است که در نقطه ای از رشته تعداد پرانتزهای باز سمت چپ پرانتز بسته ناکافی بوده است. به هر حال اگر مقدار صفر نباشد آنگاه مقدار False را برمی گردانیم. درصورتی که مقدار count صفر باشد True را برمی گردانیم. این یعنی not count پاسخ درست را می دهد (خط 6).
در یک مصاحبه برنامه نویسی، برنامه را دوباره مرور می کنیم تا از درستی آن مطمین شویم. همچنین چندین داده ورودی را روی آن تست می کنیم.
