كيفية تحديد الحد الأقصى لعمق أقواس التعشيش: القواعد والأمثلة

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

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

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

1. ما هو عمق التعشيش بين قوسين?
2. تحديد عمق تداخل الأقواس
3. ما هو المبدأ الأساسي للتعريف?
4. خوارزمية لتحديد أقصى عمق لأقواس التعشيش
5. ما هي الخطوات التي أحتاج إلى إكمال?
6. ما هي الصيغ والقواعد التي ينبغي تطبيقها?
7. أمثلة على تحديد أقصى عمق لأقواس التعشيش
8. مثال 1: استخدام الصيغة
9. مثال 2: استخدام الخوارزمية
10. سؤال وجواب
11. كيفية تحديد أقصى عمق تداخل الأقواس?

ما هو عمق التعشيش بين قوسين?

عمق تداخل الأقواس هو عدد أقواس الفتح والإغلاق المتداخلة في تعبير أو نص. يحدد الأقواس الموجودة داخل الأقواس الأخرى ومدى عمق تداخلها.

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

يمكن أن يكون لعمق تداخل الأقواس قيم مختلفة. على سبيل المثال ، في التعبير "(3 + 2) * ((4 — 1) * 5)" عمق التعشيش للأقواس هو 2 ، حيث يوجد زوج واحد من الأقواس داخل زوج آخر من الأقواس.

يمكن أن يكون تحديد عمق تداخل الأقواس في النص مفيدا في حل المهام المختلفة ، مثل التحقق من توازن الأقواس أو تحويل التعبيرات أو تحليل التعليمات البرمجية.

تحديد عمق تداخل الأقواس

عمق تداخل الأقواس هو عدد مستويات تداخل الأقواس في التعبير. لتحديد عمق التعشيش ، يجب اتباع قواعد معينة:

1. يجب أن يحتوي قوس الفتح دائما على قوس إغلاق مطابق.
2. لا يمكن أن تتداخل الأقواس-يجب إغلاق كل قوس إغلاق بواسطة قوس الفتح المقابل.
3. يتم تحديد عمق تداخل الأقواس من خلال الحد الأقصى لعدد الأقواس المفتوحة في وقت واحد.

فيما يلي أمثلة لفهم واضح لتحديد عمق تداخل الأقواس:

في المثال الأول ، يكون عمق تداخل الأقواس 3 ، نظرا لأن أكبر عدد من الأقواس المفتوحة في وقت واحد هو 3.

في المثال الثاني ، يكون عمق تداخل الأقواس 2 ، نظرا لأن أكبر عدد من الأقواس المفتوحة في وقت واحد هو 2.

في المثال الثالث ، يكون عمق تداخل الأقواس 4 ، نظرا لأن أكبر عدد من الأقواس المفتوحة في وقت واحد هو 4.

في المثال الرابع ، يكون عمق تداخل الأقواس 1 ، حيث يتم إقران أقواس الفتح والإغلاق مع بعضها البعض.

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

في المثال السادس ، يكون عمق تداخل الأقواس 0 ، حيث لا توجد أقواس إغلاق للأقواس المفتوحة.

ما هو المبدأ الأساسي للتعريف?

يعتمد تحديد الحد الأقصى لعمق تداخل الأقواس على المبادئ التالية:

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

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

خوارزمية لتحديد أقصى عمق لأقواس التعشيش

يمكن حل تحديد أقصى عمق تداخل للأقواس في صف باستخدام مكدس.

1. قم بإنشاء مكدس فارغ حيث سيتم وضع الأقواس الافتتاحية.
2. كرر من خلال كل حرف في السلسلة.
3. إذا كان الحرف عبارة عن قوس فتح ، فأضفه إلى المكدس.
4. إذا كان الحرف هو قوس إغلاق:
• إذا كان المكدس فارغا ، فهذا يعني أن قوس الإغلاق لا يحتوي على قوس فتح ، وبالتالي يتم وضعه بشكل غير صحيح.
• إذا لم يكن المكدس فارغا ، فقم بإزالة العنصر الأخير من المكدس.
5. بعد المرور بجميع الأحرف ، تحقق مما إذا كانت المكدس فارغة:
• إذا كان المكدس فارغا ، فهذا يعني أنه تم إغلاق جميع الأقواس الافتتاحية بشكل صحيح ، والحد الأقصى لعمق التعشيش للأقواس هو 0.
• إذا لم يكن المكدس فارغا ، فهذا يعني أن هناك أقواس فتح لم يتم إغلاقها ، وأن الحد الأقصى لعمق التعشيش للأقواس يساوي حجم المكدس.

هنا مثال على تنفيذ هذه الخوارزمية في جافا سكريبت:

وظيفة جيتماكسبراكيتديبث (ستر) {

دعونا كومة = [];

السماح ماكس العمق = 0;

ل (اسمحوا لي = 0; أنا < شارع.الطول ؛ أنا {) {

دعونا شار = شارع [أنا];

إذا (شار ===" (") {

كومة.دفع (شار);

} آخر إذا (شار ===")") {

إذا (كومة.length === 0) {

return -1;

}

stack.pop();

}

maxDepth = Math.max(maxDepth, stack.length);

}

if (stack.length !== 0) {

return -1;

}

return maxDepth;

}

let str = "(((1+2)*3)+4)";

console.log(getMaxBracketDepth(str)); // Output: 3

Этот алгоритм перебирает каждый символ в исходной строке и отслеживает открывающиеся и закрывающиеся скобки. كما أنه يدعم التحكم في عمق تداخل القوس ويعيد أقصى عمق.

ما هي الخطوات التي أحتاج إلى إكمال?

لتحديد الحد الأقصى لعمق تداخل الأقواس في تعبير ، اتبع الخطوات التالية:

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

باستخدام الخوارزمية أعلاه ، يمكنك تحديد أقصى عمق تداخل للأقواس في التعبير.

ما هي الصيغ والقواعد التي ينبغي تطبيقها?

يمكن استخدام الصيغ والقواعد التالية لتحديد أقصى عمق لتداخل الأقواس:

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

هنا مثال لشرح القواعد:

في المثال الأول ، الحد الأقصى لعمق التعشيش هو 2 ، لأن مستوى التعشيش لكل قوس هو 1. في المثال الثاني ، يكون الحد الأقصى لعمق التعشيش هو 3 ، لأن مستوى التعشيش للأقواس الخارجية هو 1 ، وبالنسبة للأقواس الداخلية يكون 2. في المثالين الثالث والرابع ، يكون الحد الأقصى لعمق التعشيش هو 4 ، لأن مستوى التعشيش للأقواس الخارجية هو 1 ، وبالنسبة للأقواس الداخلية المقترنة هو 2.

يتيح لك استخدام هذه الصيغ والقواعد تحديد والتحقق من أقصى عمق تداخل للأقواس في التعبير.

أمثلة على تحديد أقصى عمق لأقواس التعشيش

لنلق نظرة على بعض الأمثلة لتوضيح الخوارزمية لتحديد أقصى عمق لأقواس التعشيش.

1. مثال 1:

   سلسلة:

   أقصى عمق تداخل الأقواس: 2

   التحليل:

   الرمز	الإجراء	العمق الحالي	أقصى عمق
   (	زيادة العمق بمقدار 1	1	1
   (	زيادة العمق بمقدار 1	2	2
   )	تقليل العمق بمقدار 1	1	2
   )	تقليل العمق بمقدار 1	0	2

2. المثال 2:

   سلسلة:

   الحد الأقصى لعمق التعشيش للأقواس: 3

   التحليل:

   الرمز	الإجراء	العمق الحالي	أقصى عمق
   (	زيادة العمق بمقدار 1	1	1
   )	تقليل العمق بمقدار 1	0	1
   (	زيادة العمق بمقدار 1	1	1
   (	زيادة العمق بمقدار 1	2	2
   )	تقليل العمق بمقدار 1	1	2
   )	تقليل العمق بمقدار 1	0	2
   )	تقليل العمق بمقدار 1	0	2

3. المثال 3:

   سلسلة:

   الحد الأقصى لعمق التعشيش للأقواس: 3

   التحليل:

   الرمز	الإجراء	العمق الحالي	أقصى عمق
   (	زيادة العمق بمقدار 1	1	1
   (	زيادة العمق بمقدار 1	2	2
   )	تقليل العمق بمقدار 1	1	2
   )	تقليل العمق بمقدار 1	0	2
   (	زيادة العمق بمقدار 1	1	2
   (	زيادة العمق بمقدار 1	2	3
   )	تقليل العمق بمقدار 1	1	3
   )	تقليل العمق بمقدار 1	0	3
   (	زيادة العمق بمقدار 1	1	3
   (	زيادة العمق بمقدار 1	2	3
   )	تقليل العمق بمقدار 1	1	3
   )	تقليل العمق بمقدار 1	0	3

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

مثال 1: استخدام الصيغة

لنفترض أن لدينا سلسلة من الأقواس ، ونريد تحديد أقصى عمق لتداخل الأقواس. لحل هذه المشكلة ، يمكنك استخدام الصيغة:

الحد الأقصى لعمق أقواس التعشيش = عدد أقواس الفتح-عدد أقواس الإغلاق

لنلق نظرة على مثال على سلسلة بسيطة تتكون فقط من أقواس:

الخط: (())(((())))

في هذا المثال ، الحد الأقصى لعمق التعشيش للأقواس هو 3. وهذا يعني أن أكبر عدد من الأقواس المغلقة في بعضها البعض ، هو 3.

مثال 2: استخدام الخوارزمية

لنفترض أن لدينا سلسلة يمكن أن تحتوي على أنواع مختلفة من الأقواس — مستديرة () ومربعة [] ومجعد {}. نحتاج إلى تحديد أقصى عمق تداخل للأقواس في هذا الخط.

لحل هذه المشكلة ، يمكننا استخدام خوارزمية قائمة على المكدس.

1. إنشاء كومة فارغة ، والتي سنضيف إليها أقواس فتح.
2. نذهب من خلال كل حرف في السلسلة.
3. إذا كان الحرف الحالي عبارة عن قوس فتح (،[،{،أضفه إلى المكدس.
4. إذا كان الحرف الحالي هو قوس إغلاق)،]،} ، تحقق مما إذا كان هناك قوس فتح مطابق في المكدس:
• إذا لم يكن المكدس فارغا وكان العنصر العلوي من المكدس يتوافق مع قوس الفتح ، فقم بإزالة قوس الفتح هذا من المكدس.
• إذا كان المكدس فارغا أو كان العنصر العلوي من المكدس لا يتطابق مع قوس الفتح ، فهذا يعني أن قوس الإغلاق الحالي لا يتطابق مع أي أقواس فتح ، ونتوقف عن التحليل أكثر.
5. بعد الانتهاء من اجتياز جميع الأحرف ، نتحقق مما إذا كانت المكدس فارغة:
• إذا كان المكدس فارغا ، فهذا يعني أن جميع أقواس الفتح والإغلاق متسقة ، وأن أقصى عمق تداخل للأقواس يساوي حجم المكدس.
• إذا لم يكن المكدس فارغا ، فهذا يعني أن هناك بعض الأقواس الافتتاحية التي لا توجد أقواس إغلاق مقابلة لها ، والحد الأقصى لعمق التعشيش للأقواس غير صحيح.

على سبيل المثال ، ضع في اعتبارك السلسلة "(({}[{}])))". دعونا تشغيل الخوارزمية:

1. المكدس: فارغ.
2. الرمز ' ( ' : نضيفه إلى المكدس.
3. الرمز ' ( ' : نضيفه إلى المكدس.
4. الرمز ' { ' : نضيفه إلى المكدس.
5. الرمز ' [ ' : نضيفه إلى المكدس.
6. الرمز ' { ' : نضيفه إلى المكدس.
7. الرمز'}': إزالة ' {'من المكدس.
8. حرف']': إزالة ' ['من المكدس.
9. رمز')': إزالة ' ('من المكدس.
10. رمز')': إزالة ' ('من المكدس.
11. رمز')': إزالة ' ('من المكدس.

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

سؤال وجواب

كيفية تحديد أقصى عمق تداخل الأقواس?

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