پرسش: یک رشته از کمانکهای ( شامل پرانتز، آکولاد، و کروشه) باز و بسته داده شده است(یعنی کاراکترهای (){}[]). برنامه ای بنویسید که مشخص کند آیا کمانکهای باز و بسته منطبق می باشند.
پاسخ: کار را با یک مثال شروع می کنیم. در رشته "()[]{}" کمانکهای از هر نوع باهم منطبق می باشند. دررشته "{}[" کروشه تطابق ندارد. همچنین در رشته "[{]}" تطابق وجود ندارد زیرا قبل از بسته شدن کروشه باز ،یعنی کاراکتر"]"، در اندیس دوم رشته آکولاد بسته قرار دارد. خاصیتی از رشته های با کمانک منطبق می بینیم آن است که در آنها حداقل یک جفت کمانک متوالی ( یعنی یک زوج () یا {} یا []) یافت می شود و اگر چنین کمانکی را از آن حذف کنیم، رشته باقیمانده دارای کمانک منطبق خواهد بود.
بنابراین راه حل سادی برای این مساله آن است که هربار یک زوج کمانک را از رشته حذف کنیم. اگر با تکرار این کار به رشته خالی برسیم آنگاه رشته اولیه دارای کمانکهای منطبق بوده است. اگر رشته خالی نباشد و زوج کمانکی در آن یافت نشود آنگاه رشته اولیه دارای کمانکهای منطبق نبوده است. این الگوریتم به ازای هر جفت کمانک متوالی یکبار رشته را جستجو می کند. بنابر این پیچیدگی محاسباتی آن در بدترین حالت (O(n^2 می باشد.
اشکال این روش جستجوی تکراری رشته برای یافتن جفت کمانک های متوالی است. بنابر این به راه حلی فکر می کنیم که از ابتدای رشته تنهای یکبار به سمت انتهای آن حرکت کند و کمانهای بسته شده را بیابد. اینکار باید بگونه ای کمانک های باز منطبق نشده را بخاطر بسپارد و در صورت مشاهده کمانک بسته بررسی کند که تطابق وجود دارد یا خیر. برای بررسی کردن تطابق یک کمانک بسته همیشه باید تنها آخرین کمانک باز استفاده نشده را بیابیم. همچنین با مشاهده یک کمانک باز آن را به انتهای لیست کمانکهای باز اضافه می کنیم. اینگونه اضافه کردن و حذف کردن در لیست کمانک های بازشده رفتار <<First in Last Out>> ساختمان داده پشته را تداعی می کند. بنابر این از مفهوم ساختمان داده پشته برای حل این مساله استفاده می کنیم.
در الگوریتم جدید از سمت چپ رشته شروع می کنیم. بادیدن هر کمانک باز آن را روی پشته می گذاریم. با دیدن هر کمانک بسته عنصر بالای پشته را بررسی می کنیم. اگر روی پشته کمانکی متناسب با کمانک بسته دیده شده باشد (یعنی ")" برای "(" و "}" برای "{" و "]" برای "[" ) به این معناست که یک جفت منطبق دیده ایم. بنابر این کمانک باز بالای پشته را مصرف کرده و آن را حذف می کنیم. درصورتی که کمانک بالای پشته متناسب نباشد یعنی تطابق وجود ندارد.
با توجه به اینکه این الگوریتم تنها یکبار رشته راپیمایش می کنیم و هر کمانک باز یکبار رو پشته قرار می گیرد، پیچیدگی محاسباتی این الگوریتم (O(n می باشد.
برای اینکه از درستی الگوریتم مطین شویم آن را حداقل روی دو ورودی یکی با رشته منطبق مثلا "{[]}()" و دیگری رشته نامنطبق مثلا "[{]}" بصورت دستی امتحان می کنیم. برای رشته منطبق مشاهد کاراکترها و وضعیت پشته اینچنین خواهند بود:
با این دلیل که با اتمام رشته پشته خالی است نتیجه می گیریم که همه کمانکهای رشته منطبق می باشند.برای رشته نامنطبق "[{]}" وضعیت پشته چنین خواهد بود.
با توجه به این دومثال بنظر می رسد که الگوریتم می تواند جواب درست را بدهد. بنابر این شروع به نوشتن برنامه می کنیم.
ابتدا برای تابع نام مناسبی انتخاب می کنیم. سپس یک پشته، که در پایتون با لیست پیاده می شود، تعریف می کنیم (خط 2). سپس یک دیکشنری تعریف می کنیم که زوج کاراکترهای کمانکها را مشخص میکند (خط 3). سپس در یک حلقه تکرار (خطوط 4 تا 10) هربار یک کاراکتر را می خوانیم. درصورتی که کاراکتر یک کمانک باز باشد آن را روی پشته می گذاریم. درغیر اینصورت اگر که پشته خالی نباشد و کاراکتر بالای پشته کمانک باز مرتبط به کمانک بسته کنونی باشد (خط 7) آن را از روی پشته حذف می کنیم (خط 8). در غیر این صورت کمانکهای رشته منطبق نمی باشند (خط 10). با اتمام حلقه درصورتی که پشته خالی باشد نتیجه می گیریم که دارای کمانکهای منطبق می باشد (خط 11).
علاوه بر الگوریتم سریع، برنامه فوق از روشی استفاده می کند که کد را تمیز و مرتب و همچنین قابل توسعه می کند. این تکنیک مربوط به استفاده از دیکشنری در خط 3 برای نگهداری زوج های متناظر کمانکهاست.
استفاده از این روش دو مزیت دارد:
(۱) نیاز به استفاده از تعداد زیادی خط برای نوشتن if else برای تطبیق کمانک ها نمی باشد. بلکه همه آنها در خط 7 انجام می شوند.
(۲) برنامه قابلیت توسعه دارد. به این معنا که اگر در آینده یک کمانک جدید مثلا <> نیز به عنوان کمانک قابل قبول در رشته ارایه شود تنها لازم است که این زوج به خط 3 اضافه شوند و هیچ جای دیگر برنامه نیاز به تغییر ندارد.
