التأكد أن كل قوس مفتوح يقابله قوس مغلق

عندك مجموعة اقواس بتفتح وتقفل

عاوز اتاكد ان كل قوس اتفتح اتقفل مقابل ليه وإن القوس اتفتح في الأول

كده مثلا

((  )) ده صح

))((  ده غلط

ايه أحسن حل?

===========================

الحل اللي فكرت فيه

أول حاجة تتأكد ان عدد الأقواس زوجي

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

 بعد النص للاخر مقفولة
يعني

  عدد الأقواس زوجي

 والأقواس مفتوحة في البداية  من جهة اليسار  ومقفولة في الجهة المقابلة جهة اليمين 

public static boolean checkValid(String seq){

        for (int i = 0; i<seq.length()/2; i++) {

           if(seq.charAt(i) != '(' && seq.charAt(seq.length()-1-i) != ')'){

               return false;

           }

        }

        return true;

    }

 ( ( )(  ) )   طيب لو ده مثلا افترضنا إنه صحيح

 المفروض انه صح لكن الدالة السابقة هتطلعه غلط  عشان الحرف الثالث مقفول والرابع مفتوح

يبقى الحل

1- عدد الأقواس زوجي

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

2- القوس الأول مقفول

3- القوس الأخير مقفول

لكن ده         ()  )(  ( )

غلط وهيطلع بالحل ده صح

  

الحل

1- عدد الأقواس زوجي

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

2- القوس الأول مقفول

3- القوس الأخير مقفول
4- تلف على ال Sting
وتعمل عدادين
كل لما تلاقي قوس مفتوح تزود واحد في العداد الأول
تلاقي قوس مقفول تزود واحد في العداد الثاني
بشرط ان العداد الثاني ميزيدش عن العداد الأول في كل مرة يعني ميكنش قوس اتقفل قفل ما يكون اتفتح

حل تاني أسهل باستخدام

  data structure

وهي ال

 stack 

انك لو لقيت قوس مفتوح تدخله
push
لو اتقفل تشيل اول قوس كان مفتوح منها يعني تعمل
 بشرط ان ال  pop
stack
متكونش فضيت
في الاخر لو ال
stack
فضيت يبقى الأقواس مضبوطة

    public static boolean checkValid2(String seq) {

        Stack st = new Stack();

        for (int i = 0; i < seq.length(); i++) {

            if (seq.charAt(i) == '(') {

                st.push(seq.charAt(i));

            } else {

                if (!st.isEmpty()) {

                    st.pop();

                } else {

                    return false;

                }

            }

        }

        if (st.size() > 0) {

            return false;

        }

        return true;

    }