التحقق فيما إذا كانت الأقواس صحيحة أم لا.

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

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

أي مثلاً ما يلي يعبر عن أقواس صحيحة:

() () ( () )
( () ( () () ) )
() () () ( ( ( ) ) )

بينما ما يلي لا يشكل أقواس صحيحة:

) () () (
( ( ) ) )
( ( ) ) (

هناك طريقة بسيطة تعتمد على المكدس للتحقق من ذلك، و هي أن تقوم بالمرور على كل قوس و تقوم بما يلي كل مرة:

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

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