Geçenlerde bir mülakat sırasında tarafıma yöneltilen bir soru vardı. Soruyu tam olarak cümle cümle hatırlayamıyorum fakat soru yaklaşık şöyleydi : Verilen integer kadar ve aynı zamanda doğru düzende olan parantez kombinasyonunu bulan kod.
Örneğin verilen integer 3 olsun, şöyle bir çıktı isteniyor : ()()(),()(()),(())(),(()()),((())).
Doğru düzende olması şu anlama geliyor :
Açılmış parantez kadar kapatılmış parantez de olmalı. Ayrıca bunların düzeni doğru sırada olmalı. Yani örneğin parantez açılmadan kapat parantez olmamalı vs. Kodu Java ile gerçekleştirdiğimizde yaklaşık olarak aşağıdaki gibi geliştirilebilir.
(Tabii ki birden fazla çözüm yolu bulunabilir. Ben sadece aklıma yatan bir yolu örnek olması açısından veriyorum.)
import java.util.Scanner;
public class Parantez {
public static boolean isValid(String str){
boolean ret=false;
int total=0;
for(int i=0;i%lt;str.length();i++){
if(str.charAt(i)=='1'){
total++;
}else{
total--;
}
if(total%lt;0) {
ret=false;
break;
}
}
if(total==0)ret=true;
return ret;
}
public static String intToStr(int a){
String ret="";
if(a%lt;2) return ""+a;
ret=intToStr((int)a/2)+""+a%2;
return ret;
}
public static String lPad(String str,int a){
String ret="";
ret=str;
while(ret.length()%lt;a*2){
ret="0"+ret;
}
return ret;
}
public static void main(String[] args){
int cnt=0;
Scanner sc=new Scanner(System.in);
cnt=sc.nextInt();
sc.close();
for(int i=0;i%lt;Math.pow(2,cnt*2);i++){
String str=lPad(intToStr(i),cnt);
if(isValid(str))
System.out.println(
str.replaceAll("1", "(").replaceAll("0", ")")
);
}
}
}
Buradaki mantık şu şekilde :
Öncelikle tüm parantez kombinasyonunu çıkartıyoruz. Bunun için aç parantez'e "1" kapa parantez'e ise "0" veriyoruz. Dolayısıyla buradan bir döngü yardımıyla tüm parantez kombinasyonunu üretebiliyoruz.
Daha sonra kontrol aşamasında ise şöyle bir mantık yürütüyoruz :
kapa parantezlere "-1" aç parantezlere ise "1" olacak şekilde soldan başlayarak ifadenin toplamını almaya başlıyoruz. Şayet toplam negatife düşerse açılmadan kapatılmaya çalışılan bir parantez var anlamında. Toplam sonucunda ise "0" bulunmaz ise açılmış sayısa parantez kapatılmamış anlamındadır.
Herkese başarılar...