İç İçe Parantezler

(),[],{} 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 :slight_smile:
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.