AlgoVerse

تطابق پرانتزها

با یک پشته بررسی می‌کند که پرانتزها، کروشه‌ها و آکولادها درست باز و بسته شده‌اند: هر بسته باید با آخرین باز هم‌نوع باشد.

شمردن بازها و بسته‌ها کافی نیست (([)] تعداد برابر دارد ولی درست نیست). هر بسته باید با آخرین پرانتزی که باز شده و هنوز بسته نشده جور باشد؛ «آخرین باز، اولین بسته» همان رفتار پشته است.

ادامه‌ی توضیح ↓
ورودی:
s="{a*[b+(c-d)]…"خروجی PDF

{a*[b+(c-d)]}؛ سه نوع پرانتز تودرتو، همه جور.

  1. def balanced(s):
  2. pairs = {")": "(", "]": "[", "}": "{"}
  3. stack = []
  4. for i in range(len(s)):
  5. ch = s[i]
  6. if ch in "([{":
  7. stack.append(ch)
  8. elif ch in pairs:
  9. if not stack:
  10. return False
  11. top = stack.pop()
  12. if top != pairs[ch]:
  13. return False
  14. pair = top + ch
  15. if stack:
  16. return False
  17. return True

ناوردا: پشته دقیقاً پرانتزهایی است که باز شده‌اند و هنوز بسته نشده‌اند، به ترتیب باز شدن.

شروع اجرا

0123456789101112
{a*[b+(c-d)]}
stack—

متغیرهای محلی

s'{a*[b+(c-d)]}'

نارنجی = در همین گام عوض شد

Call stack

  1. balanced()خط 1
گام ۱ از ۷۰
خط سیاه = open, closed · خط نارنجی = گام کلیدیopen: 0/3 · closed: 0/3 · balanced: 0/1
    توضیح

    ایده

    شمردن بازها و بسته‌ها کافی نیست (([)] تعداد برابر دارد ولی درست نیست). هر بسته باید با آخرین پرانتزی که باز شده و هنوز بسته نشده جور باشد؛ «آخرین باز، اولین بسته» همان رفتار پشته است.

    الگوریتم

    • پرانتز باز را روی پشته بگذار.
    • پرانتز بسته: پشته نباید خالی باشد و بالای آن باید همان نوع باز باشد؛ آن را بردار.
    • در پایان پشته باید خالی باشد.

    کاربرد

    کامپایلرها، ویرایشگرهای متن (پیدا کردن جفت پرانتز) و بررسی درستی HTML/XML.

    در trace به چه چیزی نگاه کنی

    • اشاره‌گر i روی رشته و کارت stack که پرانتزهای باز را نشان می‌دهد.