مكدس تطابق الأقواس: آخر فتح وموضع أول إغلاق مخالف

التوازن تعشيق لا تساوي أعداد فقط

نريد فحص سلسلة من رموز الأقواس وحدها، مع ثلاثة أنواع من الفتح والإغلاق. يوضح مرجع CP-Algorithms أن الفحص متعدد الأنواع يحتاج متابعة نوع الفتح المنتظر، لا عدد الفتحات وحده. سنبني تقريرًا أصليًا يحفظ المواضع والأزواج المكتملة وأول مخالفة في التوازن، ثم نراجع لماذا قد تتساوى أعداد الأنواع مع بقاء السلسلة غير صحيحة التعشيق.

العقد يقبل الرموز الستة فقط ولا يفسر أسماء أو أرقامًا أو اقتباسات أو تعليقات داخل السلسلة. نفحص هذا الشرط قبل متابعة التوازن، ونرفض مدخلًا لا يوافقه بدل تجاهل أحرف لم نحدد معناها. لذلك التقرير ليس محللًا كاملًا لشيفرة برنامج، ولا يتعامل مع ظهور قوس داخل نص مقتبس كما لو عرف سياقه اللغوي.

نرقم المواضع من صفر، ونحفظ نوع كل فتح وموضعه إلى أن نجد الإغلاق الملائم. ظهور عدد متساوٍ من الفتح والإغلاق في نهاية النص لا يضمن أن كل خطوة كانت صالحة. إذا أغلقت نوعًا أقدم بينما ما زال نوع أحدث ينتظر فوقه، فقد تداخلت الأزواج بطريقة تخالف التعشيق، حتى لو استطعنا عد كل رمز وإيجاد مقابله بالعدد.

[1]

مثال الأقواس الثلاثة المتداخلة

نأخذ السلسلة ([{}]) من ستة رموز. في الموضع صفر فتح دائري، ثم فتح مربع في واحد، ثم فتح معقوف في اثنين. الإغلاق المعقوف عند ثلاثة يغلق آخر فتح معقوف، ثم يغلق المربع عند أربعة، ثم الدائري عند خمسة. الأزواج بحسب ترتيب اكتمالها هي اثنان مع ثلاثة، ثم واحد مع أربعة، ثم صفر مع خمسة.

لا نقرأ ترتيب اكتمال الأزواج بوصفه ترتيب فهرس الفتح. الزوج الداخلي ينتهي أولًا، بينما الزوج الخارجي بدأ أولًا وينتهي آخرًا. إذا أراد تقرير آخر عرض الأزواج بحسب موضع البداية، يمكنه ترتيب بياناتها بعد الفحص، لكن كودنا يسجلها حين نصل إلى إغلاق ناجح. هذا قرار واضح في شكل المخرج، لا تغيير في علاقات التعشيق نفسها.

الرسم الرئيسي يعرض الرموز والمواضع وتسلسل المكدس قبل الإغلاق وبعده. البيانات من تأليف المثال، ولا ننقل إليه أعدادًا أو عمليات حساب كي نعلن أنه تعبير صالح بلغة برمجة. ما ثبت أن سلسلة الرموز نفسها تطابق عقد الفتح والإغلاق والتعشيق الذي أعلنّاه، مع غياب أي فتح معلق عند نهايتها.

آخر فتح أول ما يجب إغلاقه

تصف NIST المكدس بأنه يحتفظ بأحدث عنصر مضاف في القمة، ويزيله أولًا عند السحب. هذه هي العلاقة التي نحتاجها للأقواس المتداخلة: ما فتح أخيرًا يجب أن يغلق قبل أن نستطيع إغلاق الطبقة التي تحته. لذلك نضيف الفتح إلى نهاية قائمة المكدس، وننظر إلى آخر عنصر عند كل إغلاق في تطبيقنا.

في المثال، لا يكفي أن يكون الفتح الدائري موجودًا في أسفل المكدس كي نقبل إغلاقًا دائريًا مباشرةً عند الموضع ثلاثة. فوقه فتح مربع ومعقوف لم يكتمل إغلاقهما. يحدد العنصر في القمة النوع الذي ننتظره الآن، ولا نبحث في كل المكدس عن أي فتح يوافق الرمز ثم نخرجه من الوسط.

هذه السياسة تحفظ ترتيب الطبقات وتسمح باستعادة موضع الفتح عند إغلاقه. لا نستعمل طابورًا يسحب أقدم فتح أولًا، لأنه سيعامل المثال المتداخل كما لو كانت الطبقة الخارجية يجب أن تنتهي قبل الداخلية. الاسم والعملية التي اخترناها يفسران النتيجة؛ مجرد تخزين قائمة فتحات لا يكفي إذا تغير الطرف الذي نقرأه أو نزيله.

[2]

تتبع مكدس المواضع

بعد الموضع صفر يحوي المكدس الفتح الدائري وموضعه صفرًا. وبعد واحد يحوي الدائري ثم المربع، وبعد اثنين يضيف المعقوف إلى القمة. نحتاج النوع والموضع معًا: النوع يحدد الإغلاق المنتظر، والموضع يربط الزوج بشاهد في الإدخال الأصلي. حفظ نوع بلا موضع يسمح بفحص جزئي لكنه لا يعطي حقول التقرير التي طلبناها هنا.

عند الموضع ثلاثة، يوافق الإغلاق المعقوف قمة المكدس، فنزيل الفتح عند اثنين ونحفظ الزوج. تبقى القمة مربعًا عند واحد. عند أربعة نزيله ونحفظ زوجه، ثم عند خمسة نزيل الدائري عند صفر. يصبح المكدس فارغًا بعد قراءة السلسلة كلها، فنعلن النجاح بدل الاكتفاء بنجاح آخر رمز وحده.

ولو توقفنا بعد بعض الرموز، فلن يكفي ما رأيناه لإعلان نجاح النص الكامل. مثلًا بعد الموضع ثلاثة يوجد زوج معقوف صحيح، لكن طبقتين ما زالتا مفتوحتين. نميز ما اكتمل داخل البادئة من حالة السلسلة عند نهايتها، حتى لا يتحول زوج ناجح محلي إلى نتيجة توازن عامة لم نصل إلى شروطها بعد.

عد متساوٍ لكن نوع الإغلاق مخالف

في السلسلة ([)] يوجد فتح دائري وإغلاق دائري وفتح مربع وإغلاق مربع؛ أعداد كل نوع متساوية. لكن عند الموضع اثنين يصل إغلاق دائري بينما القمة فتح مربع عند واحد. النوع المنتظر هو إغلاق مربع، فيعيد التقرير mismatch عند اثنين مع موضع الفتح واحدًا والنوع المتوقع والنوع الفعلي.

لو قارنا الأعداد النهائية فقط، أو عاملنا كل فتح زيادة وكل إغلاق نقصًا دون متابعة النوع، فقد نفوت هذه المخالفة. القاعدة الرقمية الخاصة بنوع واحد لا تصير فحصًا لعدة أنواع بمجرد أن جمعناها في عدد موحد. المثال الفاصل يوضح لماذا يحمل المكدس النوع إلى جانب عدد العناصر المنتظرة.

كما لا يقول الموضع اثنان بالضرورة أين كان قصد الكاتب إدخال تعديل. قد يكون أراد ترتيبًا آخر أو أغفل إغلاقًا قبل ذلك. expected يصف ما يلائم القمة في هذا الموضع، ولا يمثل تصحيحًا كاملًا مضمونًا للشيفرة أو النص. دالتنا تشخص المخالفة في عقد الرموز ولا تطبق إصلاحًا تلقائيًا على طلب لم يحدد سياسة تعديل.

عرض الرسم بالحجم الكامل

إغلاق بلا فتح منتظر

نأخذ السلسلة ())؛ الفتح عند صفر يغلق بنجاح عند واحد، فيصبح المكدس فارغًا ونحفظ الزوج صفرًا مع واحد. عند الموضع اثنين يصل إغلاق دائري جديد بلا فتح منتظر. هنا يعيد التقرير unexpected_close، ويحتفظ بالزوج الذي اكتمل قبل الخطأ، بدل اختراع موضع فتح لم يرد في المصدر.

تختلف هذه الحالة من mismatch؛ في الأولى لا يوجد عنصر في القمة أصلًا، وفي الثانية يوجد فتح لكن نوعه لا يوافق الإغلاق. الفصل بين نوعي التقرير يوضح أي معلومة نملكها: يمكن للمخالفة النوعية أن تعطي expected وopening_index، بينما الإغلاق غير المتوقع لا يملك فتحًا معينًا ننسبه إليه في المكدس الفارغ.

ولا يعني نجاح الزوج الأول أن السلسلة كلها متوازنة. يجب أن تكون كل الإغلاقات مناسبة وأن ينتهي المرور دون فتحات معلقة. نعرض الأزواج السابقة بوصفها نتائج جزئية داخل تقرير فاشل، ونحفظ valid مستقلًا حتى لا يقرأ المستهلك وجود زوج واحد كعلامة نجاح عامة.

النهاية وفتحات لم تغلق

السلسلة ([] تكمل الزوج المربع بين الموضعين واحد واثنين، لكنها تصل إلى نهاية طولها ثلاثة مع بقاء الفتح الدائري عند صفر. يعيد التقرير unclosed وموضع النهاية ثلاثة وقائمة الفتحات الباقية. هذا الموضع حد بعد آخر رمز، وليس رمز إغلاق خاطئًا كان موجودًا في الإدخال.

ونحفظ expected_suffix الذي يغلق القمة ثم ما تحتها في بادئة لم تتضمن مخالفة سابقة. في هذا المثال هو الإغلاق الدائري وحده. وفي مثال فتح مربع ثم دائري، نحتاج إغلاق الدائري ثم المربع. الترتيب العكسي لقائمة الفتحات الباقية يأتي من تعشيق المكدس، لا من فرز الرموز بحسب شكلها أو موضعها تصاعديًا.

هذا الحقل إكمال مناسب للفتحات الحالية ضمن عقد السلسلة، وليس ادعاء أقل عدد تحرير لكل نص خاطئ أو إصلاح لبرنامج كامل. عند مخالفة مبكرة توقفت الدالة قبل نهاية النص أصلًا، فلا ننقل معنى لاحقة النهاية إليها. نقرأ نوع الحالة والموضع والبيانات التي حفظت فيها قبل تفسير ما يمكن استعماله لتكوين مثال متوازن.

الأزواج المكتملة قبل الخطأ جزئية

قد يحفظ التقرير أزواجًا صحيحة ثم يتوقف عند مخالفة لاحقة. في ()) بقي الزوج صفرًا مع واحد رغم أن valid تساوي False. وفي ([] بقي الزوج المربع واحدًا مع اثنين بينما لم يكتمل الخارجي. لا نزيل هذه البيانات من التقرير، لأنها تصف ما نجح محليًا، لكننا لا نسميها قائمة أزواج لكل سلسلة متوازنة.

وفي مثال ()([)] يكتمل الزوج الأول قبل أن يصل المرور إلى إغلاق مخالف في الجزء التالي. يستطيع المراجع رؤية موقع نجاح سابق وموقع المخالفة الأولى دون أن تتعارض المعلومتان. وجود بيانات في pairs ليس شرط النجاح؛ الحقل valid ونوع kind هما اللذان يحددان حالة الفحص ضمن العقد الذي اتبعناه.

لذلك لا نطلب من مستهلك التقرير أن يخمن النتيجة من طول قائمة الأزواج. قد تكون فارغة في سلسلة غير متوازنة، وفارغة أيضًا في سلسلة فارغة صحيحة، وقد تكون غير فارغة مع إخفاق لاحق. نحتفظ بالأسماء والمعاني منفصلة حتى يفسر المستخدم الجزئي والكامل بدقة بدل تحويل عدد صفوف ظاهر إلى حكم لم يعطه الكود.

الفارغ والتجاور والتكرار

السلسلة الفارغة متوازنة في عقدنا، فلا تحتوي فتحًا ينتظر إغلاقًا ولا إغلاقًا غير متوقع. تعيد الدالة valid صحيحة وأزواجًا فارغة. هذا يختلف من مدخل ليس نصًا أو يحوي رمزًا خارج الأبجدية؛ غياب الرموز حالة مقبولة، أما نوع المدخل وأحرفه فيحتاجان مراجعة قبل بدء الفحص.

ونستطيع وضع زوج صحيح بعد زوج صحيح، مثل ()[]{}، دون طبقة خارجية تجمعها كلها. يغلق كل فتح قبل بدء الزوج التالي، ويبقى التعشيق سليمًا. لا نلزم كل سلسلة متوازنة بأن تبدأ بفتح يحيط بجميع الرموز، كما لا نستنتج من وجود ثلاثة أنواع أنها يجب أن تظهر دائمًا من الخارج إلى الداخل بالترتيب نفسه.

وعند تكرار نوع واحد في ((()))، تظل سياسة آخر فتح أول إغلاق مناسبة. تحفظ المواضع تمييز كل ظهور، رغم أن الأنواع متساوية. لا ندمج الفتحات المتكررة في عنصر واحد، لأن ثلاثة إغلاقات تحتاج ثلاثة ظهورات مقابلة. النوع وحده يحدد صلاحية المقارنة، والموضع يعطي هوية الزوج الذي اكتمل.

الكود الأصلي وأبجدية الستة رموز

الدالة التالية تقبل str من رموز الأقواس الستة فقط، وتراجع هذا الشرط على المدخل كله قبل المرور. إذا وجد حرف عادي أو فراغ أو اقتباس ترفع ValueError، وإذا كان المدخل غير نصي ترفع TypeError. لا تتجاهل رموزًا غير مدعومة ثم تعطي نتيجة عن نص كامل لم تحدد كيفية تفسيره.

بعد التحقق، تحفظ الدالة قائمة فتحات مع مواضعها، وتستعمل القمة عند كل إغلاق. عند النجاح تزيل الفتح وتحفظ الزوج، وعند المخالفة ترجع فورًا تقريرها دون متابعة بقية الرموز أو تغيير المصدر. وعند النهاية تراجع الفتحات الباقية وتعلن unclosed أو balanced. المخرج يصف ما فحصناه فعلًا وحدود التوقف.

هذا تنفيذ أصلي لطريقة معروفة مع حقول تقرير صممناها للأمثلة. لا نزعم اختراع المكدس أو خوارزمية جديدة، ولا نستدعي محلل لغة برمجة داخل الكود. الصور والمواضع والنتائج هنا من إعداد المقال، ونراجعها بمرجع حذف أزواج مستقل حتى لا يكون نجاح مثال متداخل واحد هو دليلنا الوحيد.

def bracket_report(text):
    if not isinstance(text, str):
        raise TypeError("bracket text required")
    closing = {"(": ")", "[": "]", "{": "}"}
    if any(symbol not in "()[]{}" for symbol in text):
        raise ValueError("only the six bracket characters are supported")
    stack = []
    pairs = []
    for position, symbol in enumerate(text):
        if symbol in closing:
            stack.append((symbol, position))
            continue
        if not stack:
            return {"valid": False, "kind": "unexpected_close", "index": position,
                    "actual": symbol, "pairs": tuple(pairs)}
        opening, opening_index = stack[-1]
        if closing[opening] != symbol:
            return {"valid": False, "kind": "mismatch", "index": position,
                    "opening_index": opening_index, "expected": closing[opening],
                    "actual": symbol, "pairs": tuple(pairs)}
        stack.pop()
        pairs.append((opening_index, position))
    if stack:
        return {"valid": False, "kind": "unclosed", "index": len(text),
                "remaining_open": tuple(stack),
                "expected_suffix": "".join(closing[symbol] for symbol, _ in reversed(stack)),
                "pairs": tuple(pairs)}
    return {"valid": True, "kind": "balanced", "pairs": tuple(pairs)}

أول مخالفة توازن بعد تحقق الأبجدية

إذا أعطينا المدخل ()) ومعه حرف عادي في آخره، يفشل تحقق الأبجدية قبل أن نبدأ إرجاع تشخيص التوازن. لذلك عبارة أول مخالفة في التقرير تخص المرور على مدخل اجتاز شرط الرموز، لا بحثًا عامًا عن أول مشكلة من كل أنواع المشكلات الممكنة في نص مختلط. ترتيب التحقق جزء من عقد واجهتنا.

بعد الاجتياز نتوقف عند أول إغلاق غير مناسب، ولا نعد جميع المخالفات أو نبحث عن أفضل تعديلات لها. مثلًا ([)] يعيد موضع المخالفة اثنين، ولا يحاول فتح فرضية إصلاح ثم متابعة الرمز الأخير تحتها. الاستمرار بعد خطأ يحتاج سياسة جديدة لكيفية التعامل مع الحالة، وقد ينتج تقارير مختلفة لم ننفذها هنا.

ونحفظ عدم الإزالة عند mismatch؛ القمة التي أعطتنا expected وopening_index لم نغلقها بنجاح. لا نسجل زوجًا مخالفًا ثم نصفه بأنه من pairs المكتملة. التوقف يحافظ على معنى ما سبق جمعه، ويجعل كل زوج في القائمة نتيجة مقارنة صحيحة تمت قبل أول إخفاق في التوازن.

السلسلة ليست شيفرة برنامج كاملة

قد يظهر قوس داخل نص مقتبس في برنامج أو تعليق أو بيانات، وقد تختلف قواعد تفسيره بحسب اللغة. دالتنا لا تعرف تلك السياقات، بل ترفض أصلًا علامات الاقتباس والأحرف الأخرى في عقدها. لا نعطي فحص الرموز وحدها عنوانًا يدعي إثبات صحة كل تعبير أو ملف مصدر أو بناء لغوي آخر.

إذا احتاج تطبيق تحليل برنامج، فعليه تحديد كيف يستخرج رموز الأقواس التي تدخل الفحص، مع الحفاظ على علاقة مواضعها بالمدخل الأصلي. حذف أجزاء أو تغيير نص قبل تقديمه قد يغير رقم الموضع الذي نعرضه. لا نأخذ فهرسًا في سلسلة مستخرجة ونسميه موقعًا في ملف أصلي دون بيانات تربط الاثنين.

كما أن توازن الأقواس لا يثبت وحده صحة العمليات أو أنواع القيم أو أسماء المتغيرات. يمكن لسلسلة أقواس سليمة أن تحيط بمحتوى لا تعرف دالتنا شيئًا عنه. ما أعلناه محدود ومفيد: ترتيب أنواع الفتح والإغلاق ومواضعها في سلسلة معلنة. نحافظ على هذا المعنى بدل توسيع كلمة صالح إلى خصائص لم تدخل في الكود.

مرجع حذف الأزواج المتجاورة

للتحقق المستقل، يأخذ مرجعنا السلسلة ويزيل أي زوج متجاور ملائم من الأنواع الثلاثة، ثم يكرر العملية حتى لا يتغير النص. إذا اختفت الرموز كلها، يقبلها في رسم القواعد الذي نختبره. هذا المرجع لا يستعمل المكدس أو تقارير مواضع دالتنا، فيختلف عن إعادة الطريقة نفسها باسم آخر.

في مثال ([{}]) يزيل الزوج المعقوف الداخلي، فتصير ([])، ثم يزيل المربع، ثم الدائري، وينتهي إلى الفراغ. وفي ([)] لا يجد زوجًا متجاورًا ملائمًا يزيله، فتبقى السلسلة غير مقبولة. الأمثلة توضح كيف يمكن لطريقتين مختلفتين أن تتفقا على الحكم مع احتفاظ إحداهما بمواضع وتشخيص أغنى من الأخرى.

نفذنا المقارنة على جميع سلاسل الأبجدية الستية بأطوال من صفر إلى ستة. لا يحول ذلك الفحص إلى برهان لكل طول أو لكل لغة، لكنه دليل على الحالات المعلنة. ونراجع بصورة إضافية أن الأزواج في النتائج الناجحة تغطي كل موضع مرة واحدة، وأن كل فتح يسبق إغلاقه، وأن أنواعها تلائم بعضها.

فحوص المواضع وبطاقة النتيجة

بطاقة المثال المتداخل تحفظ النص ([{}]) وأزواجه اثنين مع ثلاثة وواحد مع أربعة وصفر مع خمسة، مع valid صحيحة وkind balanced. وبطاقة المخالف تحفظ ([)] والموضع اثنين والفتح واحدًا والنوع المتوقع والفعلية. نكتب نظام الفهرسة من صفر، ونميز موضع النهاية الذي قد يساوي طول النص عن موضع رمز فعلي داخله.

ونراجع السلسلة الفارغة والمدخلات المرفوضة والإغلاق المفاجئ والفتحات الباقية، ثم نجرب إكمال expected_suffix في الحالات التي انتهت دون مخالفة مبكرة. كلفة المرور مرتبطة بالرموز التي راجعناها، والمكدس والأزواج قد ينموان مع طول المدخل. لا نقدم قياس سرعة أو ضمان مساحة ثابتة لكل سلسلة لمجرد أن العملية الأساسية بسيطة.

قبل اعتماد تقرير، راجع الأبجدية ونوع النتيجة ومعنى الموضع وحدود التوقف. افصل بين الأزواج التي اكتملت وبين الحكم على السلسلة كلها، واحفظ المصدر الذي تخصه الفهارس. ستعرف بذلك ما أنجزه الفحص: تعشيق معلن مع تشخيص قابل للمراجعة، دون ادعاء تحليل برنامج كامل أو إصلاح مقصود لم نحدد سياسته.