(),[],{} parantezlerinden oluşan bir karakter dizimiz var eğer dizilim şekli hata vermiyorsa doğru aksi durumda yanlış döndüren fonksiyonu nasıl oluşturabiliriz?
Örnek: [(){}] doğru
[(]) yanlış
"()()" doğru mu kabul edilecek? Ya ""? Karakter dizisinin uzunluğu hep ikinin katı mı olacak?
evet bu doğru kabul ediliyor.
Açtığımız şey kapanacak mecbur 2 nin katı olmalı
Fonksiyona verilebilecek parametrelerin böyle bir sınırlaması var mı diye sormuştum. Mesela şu anda yazdığım kod tek sayı uzunluğundaki girişlerde hata veriyor.
Bunu cevaplamadınız:
parametre sayısında kısıtlama yok girilene göre kontrol edicez
karakter dizini belirtmek için kullanılıyor içerde tırnak yok “” ise biz içeriyi kontrol ediyoruz
Anlamadım? Boş bir str verildiğinde fonksiyonun döndürmesi gereken bir şey var mı demek istemiştim.
Merhaba,
ben stack kullanarak şöyle bir şey düşündüm.
def control(s)
key = {"(" : ")",
"[" : "]",
"{" : "}",
")" : '',
"]" : '',
"}" : ''}
stack = []
stack_size = 0
for i in s:
if(stack_size > 0 and key[stack[-1::]] == i):
stack.pop()
stack_size -= 1
else
stack.append(i)
stack_size += 1
return stack_size == 0
Edit:
Hatalı yazdığım kodun bildirimi yapan kişi tarafından düzenlenen hali
def control(s):
pairs = {"(" : ")",
"[" : "]",
"{" : "}"}
stack = []
for i in s:
if stack and pairs.get(stack[-1]) == i:
stack.pop()
else:
stack.append(i)
return not stack
3 Beğeni
benim jeton geç düştüde mesajı yazmış bulundum 
Belirtilmemiş doğru kabul edelim
is_pair = lambda l, r: {"{": "}", "[": "]", "(": ")"}[l] == r
check = lambda s: (check(s[2:]) if is_pair(s[0], s[1]) else is_pair(s[0], s[-1]) and check(s[1:-1])) if s else True
solution = lambda s: len(s)%2 == 0 and check(s)
assert solution("") == True
assert solution("[(){}]") == True
assert solution("()()") == True
assert solution("[(])") == False
assert solution("(") == False
Kod hatalı.
2 Beğeni
([{}])
ifadesinde False döndürdü fonksiyonunuz
True döndürüyor. Kodu en baştan kopyalayıp deneyin, bir şeyi değiştirdiniz büyük ihtimalle.
1 Beğeni
assert solution("[({()}([])[(){}])]") == True
Ipucu 1: Daha basit test case
assert solution("((())())") == True
Ipucu 2: BNF
Su anda
bal ::= "" | "()" <bal> | "(" <bal> ")"
gibi bir grameri kabul ediyor.
2 Beğeni
Zamaninda yazmıştım java ile.
1 Beğeni
bende daha önceki paylaşımlardan ilham alarak bunu yazdım
def validBraces(string:str):
while '()'in string or'[]' in string or'{}'in string:
string=string.replace('()','')
string = string.replace('[]', '')
string=string.replace('{}','')
if string=='':
return True
else:
return FalseŞöyle bir BNF çıkardım ama koda dökemedim:
<solution> ::= "(" <solution> ")" | "[" <solution> "]" | "{" <solution> "}" | "" | <solution> <solution>
any(map(check(s[n:]) and check(s[:n]), range(len(s)))) gibi bir sey ama benim aklimdaki daha cok suydu:
bal ::= "" | "()" <bal> | "(" <bal> ")" | <bal> "()"
^^^^^^^^^^
Sizin bu EBNF tanımınıza göre bir lexer ve bir parser yazmaya çalıştım. Şu ana kadar kendi test ettiklerim ile doğru çalışıyor. Siz ve diğer arkadaşlar da test ederse ve fikrini belirtirse çok memnun olurum. Belki işi uzatmış olabilirim ama lexer ve parser kurallarına göre yazınca böyle oluyor malesef.
1 Beğeni
Review? Okey:
Parser’da “{” gibi literaller kullaniliyorsa lexer token’larinin hatta lexer’in kendisinin manasi nedir anlamadim.
Ismi “p” olan ve deger olarak 0 veya 1 alabilen bir degisken var. Ne ise yaradigini anlamadim fakat akisi baya etkiliyor gibi duruyor.
tokens ve token isminde degiskenler var, ne yaptiklari ayni sekilde belirsiz. Hele token dedigimiz sey gecici degisken ismine sahipken butun sinif tarafindan kullanilan, hatta bir fonksiyondan digerine state paslamak icin kullanilan bir degisken. Neyi temsil ettigini anlamadim.
Kisacasi kod hakkinda bir sey soyleyemeyecegim zira okuyamadim. Testlerin yazilmis olmasi cok guzel ama, calistigini gorebiliyoruz. BNF’ten (random) string ureten ureteclerle ekstra case’ler eklenebilir.
3 Beğeni
Tamam o zaman daha detaylı açıklayayım. İlk olarak bir lexer’in gerekliliği hakkında şunu diyebilirim. Amacım sadece bir string girdiyi, en küçük bileşenlere ayırarak etiketlendirilmiş bir token listesi haline getiren bir sınıf yazmaktı. Olmasa da olurdu, ama lexer’ı merak eden bazı arkadaşlara iyi kötü bir lexer’ın neye benzediğini de göstermek istedim. Lexer olmadan şöyle yazılabilir:
# coding: utf-8
class Parser:
def __init__(self):
self.string = ""
self.token = None
def get_token(self):
if(len(self.string)):
self.token = self.string[0]
self.string = self.string[1:]
else:
self.token = ""
def expect(self,value):
if self.token != value:
raise Exception("Syntax Error")
self.get_token()
def curly(self):
self.expect("{")
self.stmt(1)
self.expect("}")
def bracket(self):
self.expect("(")
self.stmt(1)
self.expect(")")
def square(self):
self.expect("[")
self.stmt(1)
self.expect("]")
def stmt(self,p):
if self.token == "":
return
if self.token == "{":
self.curly()
self.stmt(p)
elif self.token == "(":
self.bracket()
self.stmt(p)
elif self.token == "[":
self.square()
self.stmt(p)
else:
if p == 1:
return
else:
raise Exception("Syntax error")
return
def __call__(self,string):
return self.work(string)
def work(self,string):
self.string = string
while True:
try:
self.get_token()
if(self.token == ""):
break
self.stmt(0)
except Exception as e:
print(e)
return False
return True
parser = Parser()
assert parser("[({()}([])[(){}])]") == True
P değişkeni ifadenin henüz bitmemiş olduğunu belirtmek için kullanılıyor. Yani bracket() metodu içerisindeyken stmt(1) çağrısı yapıldığında kapama parantezlerinden birisiyle karşılaşıldığı zaman bunun bir hata olarak değil de, bitmemiş bir ifadeye ait kapama parantezi olduğunu garantilemek için kullanılıyor. Bu durumu ayırt etmek için p değişkeni kullandım. İsmine karar veremedim, p olarak kaldı.
tokens ve token değişkenleri için, tokens değişkeni, lexer tarafından ayrıştırılmış ve parser’a işlemesi için verilmiş tokenlerin listesidir. Parser’a token listesi verildiğinde bunu self.tokens isimli değişkene aktarıyor. Ve get_token() ile listenin başından bir token alıp self.token isimli değişkene aktarıyor. self.token, parser’ın o anda üzerinde işlem yapmakta olduğu token’i ifade eder. Tüm fonksiyonlara paslamak yerine nesne niteliği olarak tanımlamayı daha kolay buldum.
BNF’den üretme konusunu bilmiyorum. İpucu verirseniz araştırabilirim.