[Python] esercizio parentesi

Linguaggi di programmazione: php, perl, python, C, bash e tutti gli altri.
Scrivi risposta
gila75
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 2739
Iscrizione: mercoledì 16 gennaio 2013, 17:28
Desktop: ubuntu-2d
Distribuzione: Ubuntu 12.04.2 LTS i686
Località: Airuno(Lecco)

[Python] esercizio parentesi

Messaggio da gila75 »

Ciao a tutti, mi sto un po' esercitando, e rispolvero vecchi esercizi del C
Un grande classico: l'allineamento parentesi:
{[()]} = ok
((())]= non ok.
Ho scritto un programma che è in grado di capire se l'allineamento è corretto, in più l'ho dotato di una piccola variazione, stampa
se l'allineamento è corretto ma la priorità no:
((([])))= allineamento ok, priorità no.
i passi sono questi:
1) input (se la stringa è dispari, per forza l'allineamento non è corretto)
2) se contiene caratteri non validi--->riscrivi

al posto di passare i caratteri ( [ { ) ] } alla lista adibita a stack, passo t,q,g alle parentesi aperte, mente T,Q,G a quelle chiuse
Questo mi evita un po' di if, se passo partentesi tonda chiusa: )---->T
io devo cercare nella posizione precedente il corrispettivo di lower(T)
Avrei potuto anche usare un dizionario

Codice: Seleziona tutto

x={'t':'(','q':'[','g':'{','T':')','Q':']','G':'{'}
a dire il vero bisogna invertire chiavi\valori...noto solo ora

ma mi sembra eccessivo, magari è più elegante, ma forse anche più oneroso...non so.
Per la priorità invece mi baso sul codice ascii:
io metto nello stack 't' ,'q', 'g'
in ordine alfabetico abbiamo g,q,t di conseguenza se sottraiamo dal codice asci abbiamo un numero negativo in presenza
di priorità errata: ([-----> t,q------> 116-113=-3
Ecco il codice, sicuramente sarà un orrore da principiante....pazienza, accetto volentieri consigli:

Codice: Seleziona tutto

def verifica_st(st):
	tabella=['(',')','[',']','{','}']
	for i in st:
		if i not in tabella:
			print("caratteri NON consentiti, riscrivi")
			return 0
		elif len(st)%2!=0:
			print ("parentesi dispari, allineamento NON corretto")
			return 0		
	else:
		return 1
#---------------------------------------------------
def parentesi(st_list):
	stack=[]
	flag=0
	for i in range (len(st_list)):
		if st_list[i]=='[' :stack.append('q') 
		if flag==0:
			if len (stack)>=1 and (ord (stack[len(stack)-1]))-(ord (stack[len(stack)-2]))<0:
				print("errore priorità")
				flag=1
			
		if st_list[i]=='(' :stack.append('t') 
		if flag==0:
			if len (stack)>=1 and (ord (stack[len(stack)-1]))-(ord (stack[len(stack)-2]))<0:
				print("errore priorità")
				flag=1
			
		if st_list[i]=='{' :stack.append('g') 
		if flag==0:
			if len (stack)>=1 and (ord (stack[len(stack)-1]))-(ord (stack[len(stack)-2]))<0:
				print("errore priorità")
				flag=1
#---------------------------------------------------------
		if st_list[i]==']' :
			stack.append('Q')
			if stack[len(stack)-2].lower()=='q':
				stack.pop();stack.pop()
			
		if st_list[i]==')' :
			stack.append('T')
			if stack[len(stack)-2].lower()=='t':
				stack.pop();stack.pop()

		if st_list[i]=='}' :
			stack.append('G')
			if stack[len(stack)-2].lower()=='g':
				stack.pop();stack.pop()
	flag=0
	return len(stack)
#---------------------------------------------------
while True:
	st=input("inserisci espressione ")
	print("espressione da valutare: ",st)
	res=verifica_st(st)
	if res==1:
		st_list=list(st)
		x=parentesi(st_list)
		if x==0:
			print ('allineamento:OK')
		else:
			print ('allineamento: NON OK',x)
		
	




Avatar utente
nuzzopippo
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 1624
Iscrizione: giovedì 12 ottobre 2006, 11:34

Re: [Python] esercizio parentesi

Messaggio da nuzzopippo »

gila75 [url=https://forum.ubuntu-it.org/viewtopic.php?p=5161173#p5161173][img]https://forum.ubuntu-it.org/images/icons/icona-cita.gif[/img][/url] ha scritto:Ciao a tutti, mi sto un po' esercitando, e rispolvero vecchi esercizi del C
Un grande classico: l'allineamento parentesi:
{[()]} = ok
((())]= non ok.
Ho scritto un programma che è in grado di capire se l'allineamento è corretto, in più l'ho dotato di una piccola variazione, stampa
se l'allineamento è corretto ma la priorità no:
((([])))= allineamento ok, priorità no.
i passi sono questi: ...
Ciao @gila, quesito interessante, mai affrontatoin precedenza, prima di leggere oltre, ho interrotto, giusto per farlo "da me" ed esercitarmi a mia volta oltre a distogliermi un po' da ciò che sto guardando adesso (Django) ,,,
ho stabilito (non ricordo bene le regole) errato anche l'annidamento di parentesi equivalenti ed utilizzato la ricorsione, ti propongo quanto ho fatto io, il Tuo codice lo guardo più appresso
vedi_par.py :

Codice: Seleziona tutto

#-*- coding: utf-8 -*-

p_tipi = {'{': ['}', 0],
          '[': [']', 1],
          '(': [')', 2],
          }

def esame_parentesi(immiss):
    '''
    Esamina una stringa per individuare la sequenza di parente contenuta.
    
    Parametri : la stringa da esaminare, supposta contenente solo "{}[]()"
    Restituisce : boolean1, boolean2, value ove
                  boolean1 = articolazione parentesi corretta
                  boolean2 = priorita parentesi corretta
                  value = valore della coppia esaminata
    '''
    limm = list(immiss)
    my_value = None
    cp = True
    if limm[0] in p_tipi.keys():
        my_value = p_tipi[limm[0]][1]
        try:
            indx = limm.index(p_tipi[limm[0]][0])
        except ValueError:
            return False, False, my_value
        # si ipotizza possano esservi più blocchi di parentesi
        sub_imm1 = limm[1:indx]
        sub_imm2 = limm[indx+1:]
        sa1 = True
        sp1 = True
        sv1 = 2
        sa2 = True
        sp2 = True
        sv2 = 2
        if sub_imm1:
            sa1, sp1, sv1 = esame_parentesi(''.join(sub_imm1))
        if sub_imm2:
            sa2, sp2, sv2 = esame_parentesi(''.join(sub_imm2))
        if not sp1 or not sp2:
            cp = False
        else:
            if sv1 < my_value or sv2 < my_value:
                cp = False
        if not sa1 or not sa2:
            return False, cp, my_value
        else:
            return True, cp, my_value
    else:
        return False, cp, 2


if __name__ == '__main__':
    imm = input('Inserire la seguenza di parentesi : ')
    for elem in imm:
        if not elem in '{}[]()':
            print('Immissione insoddisfacente.')
            exit()
    a, p, v = esame_parentesi(imm)
    print('sequenza', imm, end=' : ')
    if a:
        print('articolazione corretta', end=', ')
    else:
        print('non correttamente articolata', end=', ')
    if p:
        print('progressione corretta')
    else:
        print('scorretta nella progressione')
e questi sono esempi di output :

Codice: Seleziona tutto

python3 vedi_par.py
Inserire la seguenza di parentesi : ()()
sequenza ()() : articolazione corretta, progressione corretta
NzP:~$ python3 vedi_par.py
Inserire la seguenza di parentesi : {[()()][()]}
sequenza {[()()][()]} : articolazione corretta, progressione corretta
NzP:~$ python3 vedi_par.py
Inserire la seguenza di parentesi : [{()}]
sequenza [{()}] : articolazione corretta, scorretta nella progressione
NzP:~$ python3 vedi_par.py
Inserire la seguenza di parentesi : [(())]
sequenza [(())] : non correttamente articolata, scorretta nella progressione
NzP:~$ 
Circa metà del codice è per la parte "test"
Fatti non foste a viver come bruti ...
gila75
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 2739
Iscrizione: mercoledì 16 gennaio 2013, 17:28
Desktop: ubuntu-2d
Distribuzione: Ubuntu 12.04.2 LTS i686
Località: Airuno(Lecco)

Re: [Python] esercizio parentesi

Messaggio da gila75 »

Si, mi farebbe piacere se gli dai un occhio e mi dici il tuo parere. Calcola che ho mezzi limitati, perche' dovrei studiare ancora molte cose.
Sicuramente e' un problema che si presta in modo naturale alla ricorsione.
Purtroppo io la digerisco poco, non mi viene intuitivo.
Piu' tardi accendo il pc, salvo il codice e provo a studiarla
gila75
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 2739
Iscrizione: mercoledì 16 gennaio 2013, 17:28
Desktop: ubuntu-2d
Distribuzione: Ubuntu 12.04.2 LTS i686
Località: Airuno(Lecco)

Re: [Python] esercizio parentesi

Messaggio da gila75 »

@Nuzzo, se hai voglia, spieghi un po' a blocchi il tuo script?
Ci sono cose che credo di non avere ancora incontrato. Se ti va, senza scendere nei dettagli , solo la logica.
Ho riscontrato però un'anomalia:

Codice: Seleziona tutto

Inserire la seguenza di parentesi : [[{}]]
sequenza [[{}]] : non correttamente articolata, scorretta nella progressione
dovrebbe essere giusta la sequenza ma errata la priorità no?
A me da con il mio script:

Codice: Seleziona tutto

inserisci espressione [[{}]]
espressione da valutare:  [[{}]]
errore priorità
allineamento:OK
Sembra un modo elegante di risolvere il tuo script. Cerco di applicarmi, ma forse è prematuro
Avatar utente
nuzzopippo
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 1624
Iscrizione: giovedì 12 ottobre 2006, 11:34

Re: [Python] esercizio parentesi

Messaggio da nuzzopippo »

gila75 [url=https://forum.ubuntu-it.org/viewtopic.php?p=5161257#p5161257][img]https://forum.ubuntu-it.org/images/icons/icona-cita.gif[/img][/url] ha scritto:@Nuzzo, se hai voglia, spieghi un po' a blocchi il tuo script?
Ci sono cose che credo di non avere ancora incontrato. Se ti va, senza scendere nei dettagli , solo la logica.
Ho riscontrato però un'anomalia:,,,
Ciao @gila, in merito alla segnalazione di anomalia, cito me stesso :
ho stabilito (non ricordo bene le regole) errato anche l'annidamento di parentesi equivalenti
Ciò per antichi (veramente) ricordi delle regole per operazioni matematiche apprese una vita fa.

Nella logica da me applicata, l'annidamento di parentesi dello stesso tipo equivale ad un errore di articolazione, la "decisione" scaturisce dalla modalità di divisione delle sub-liste annidate, diventano incoerenti.

Ti posto appresso il codice precedente commentato, nei punti salienti, vedi se Ti è chiaro il processo logico adottato, per eventuali dubbi specifici indicali e parliamone

Codice: Seleziona tutto

#-*- coding: utf-8 -*-

# dizionari delle parentesi, associa ad una chiave "parentesi aperta"
# la definizione della rispettiva chiusura ed un valore pari al livello
# di annidamento
p_tipi = {'{': ['}', 0],
          '[': [']', 1],
          '(': [')', 2],
          }

def esame_parentesi(immiss):
    '''
    Esamina una stringa per individuare la sequenza di parente contenuta.
    
    Parametri : la stringa da esaminare, supposta contenente solo "{}[]()"
    Restituisce : boolean1, boolean2, value ove
                  boolean1 = articolazione parentesi corretta
                  boolean2 = priorita parentesi corretta
                  value = valore della coppia esaminata
    '''
    limm = list(immiss)     # trasorma in lista la stringa inserita
    my_value = None         # valore di annidamento della parentesi in esame
    cp = True               # variabile per la corretta progressione
    # verifica se il primo carattere è una parentesi di apertura
    # se non lo è l'inserimento non è valido.
    if limm[0] in p_tipi.keys():
        my_value = p_tipi[limm[0]][1]   # legge il livello di annidamento
        # cerca la prima evenienza della corrispondente chiusura
        # e ne legge la posizione nella lista
        try:
            indx = limm.index(p_tipi[limm[0]][0])
        except ValueError:
            # non ha trovato la chiusura, inserimento incongruente
            return False, False, my_value
        # si ipotizza possano esservi più blocchi di parentesi :
        # in base all'indice di chiusura crea due sub-liste con
        # esclusi gli elementi già letti
        sub_imm1 = limm[1:indx]
        sub_imm2 = limm[indx+1:]
        # entrambe le sub-liste potrebbero essere vuote, prepara
        # opportunamente le variabili di controllo necessarie
        sa1 = True     # articolazione della prima sub-lista
        sp1 = True     # progressione della prima sub-lista
        sv1 = 2        # annidamento della prima sub-lista
        sa2 = True     # articolazione della seconda sub-lista
        sp2 = True     # progressione della seconda sub-lista
        sv2 = 2        # annidamento della seconda sub-lista
        # se le sub-liste non sono vuote questa funzione richiama se
        # stessa sulle sottostringhe rivenienti, assegnando i valori
        # restituiti alle variabili di controllo predisposte
        if sub_imm1:
            sa1, sp1, sv1 = esame_parentesi(''.join(sub_imm1))
        if sub_imm2:
            sa2, sp2, sv2 = esame_parentesi(''.join(sub_imm2))
        # se almeno uno dei sub-elementi ha progressione errata la
        # progressione è errata
        if not sp1 or not sp2:
            cp = False
        else:
            # se la progressione dei sub-elementi è corretta valuta il
            # caso che l'elemento precedente non abbia un annidamento
            # inferiore al corrente (progressione errata)
            if sv1 < my_value or sv2 < my_value:
                cp = False
        # se almeno uno dei sub-elementi ha articolazione errata la
        # articolazione è errata, altrimenti è giusta
        if not sa1 or not sa2:
            return False, cp, my_value
        else:
            return True, cp, my_value
    else:
        # l'elemento iniziale non è una parentesi di apertura, la articolazione
        # è errata
        return False, cp, 2


if __name__ == '__main__':
    imm = input('Inserire la seguenza di parentesi : ')
    for elem in imm:
        if not elem in '{}[]()':
            print('Immissione insoddisfacente.')
            exit()
    a, p, v = esame_parentesi(imm)
    print('sequenza', imm, end=' : ')
    if a:
        print('articolazione corretta', end=', ')
    else:
        print('non correttamente articolata', end=', ')
    if p:
        print('progressione corretta')
    else:
        print('scorretta nella progressione')
Per altro, l'errore per parente equivalenti da me previsto è opinabile, ieri mi son dedicato a ricerche in merito ed in questa pagina di wikipedia, sezione dedicata alle parentesi quadre, ho trovato:
La matematica adopera le parentesi quadre nelle espressioni, come succede per le tonde e le graffe; esse includono un calcolo che deve essere svolto prima di un altro, se in questo si trovano delle parentesi tonde, come, ad esempio, nell'espressione [27 : (6 - 3)] × 5. Quest'uso è giustificato solo da questioni di comodità: l'espressione (27 : (6 - 3)) × 5 è completamente equivalente.
La qual cosa rende completamente inadatta la logica da me applicata, dovrò comunque rivederla completamente.

Questa mattina ho cominciato a vedere il Tuo codice ... forse, hai inserito un prototipo derivato dal C?, questi blocchi di istruzione mi danno errore :

Codice: Seleziona tutto

#---------------------------------------------------------
      if st_list[i]==']' :
         stack.append('Q')
         if stack[len(stack)-2].lower()=='q':
            stack.pop();stack.pop()
         
      if st_list[i]==')' :
         stack.append('T')
         if stack[len(stack)-2].lower()=='t':
            stack.pop();stack.pop()

      if st_list[i]=='}' :
         stack.append('G')
         if stack[len(stack)-2].lower()=='g':
            stack.pop();stack.pop()
   flag=0
   return len(stack)
#---------------------------------------------------
nelle istruzioni "stack.pop();stack.pop()", che danno errore "IndexError: pop from empty list" ,,, lo ho ancora visto poco e devo riguardarlo attentamente caso mai è saltata una qualche indentazione, in ogni caso lo devo anche capire "per bene".
:ciao:

[Edit] Si, guardate le indentazioni, ne erano saltate due, il Tuo codice funziona correttamente, ora posso guardarlo meglio :)

[Ri-Edit] veramente buono, ci vuole un po' a capire il codice ma l'idea di sottrarre i codici unicode per i confronto della priorità non perde un colpo, così come la mancata eliminazione da stack.
Fatti non foste a viver come bruti ...
gila75
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 2739
Iscrizione: mercoledì 16 gennaio 2013, 17:28
Desktop: ubuntu-2d
Distribuzione: Ubuntu 12.04.2 LTS i686
Località: Airuno(Lecco)

Re: [Python] esercizio parentesi

Messaggio da gila75 »

Ciao @Nuzzo, si ho capito dopo la tua logica, va bhè, quello è il meno, lo si può tranquillamente lasciare così...
Questa mattina ho cominciato a vedere il Tuo codice ... forse, hai inserito un prototipo derivato dal C?
No, ma diciamo che assomiglia molto (purtroppo) ad un programma in C... credo.
Non adottando la ricorsione, è l'unico metodo che per ora mi viene in mente.
La cosa che proprio non mi piace è che devo lavorare con gli indici, ma in questo caso, sono obbligato.
Non ho adottato la ricorsione per questi motivi:

1) Non l'ho mai "masticata" molto bene nemmeno in C. In Python, le funzioni non le ho ancora studiate, quello che vedi, sono solo
delle anteprime che ho sbirciato sul libro e in rete. Quindi, anche se la logica della ricorsione è comune a tutti i linguaggi,
non mi sono azzardato.
2) Sulla ricorsione, c'è da sempre una guerra di "religione", un po' come tra la bontà dei vari linguaggi...ognuno dice la sua.
molti sostengono (e io anche se non sono nessuno, appartengo a questa fazione) che è contro intuitiva.
Cosa più importante, è molto gravosa dal punto di vista computazionale, si rischia di riempire lo stack.
Non so bene in Python, ma una volta avevo trovato un esempio in C (forse Fibonacci, non ricordo), con 2 versioni:
tradizionale e ricorsiva, ebbene, quella ricorsiva all'aumentare dell'input ad un certo punto andava in crash.
Anche prima di fallire comunque era più lenta. Se ci si pensa, una funzione che richiama se stessa, carica i valori, "impigna" nello stack ecc...
è molto gravosa.
E' anche vero che alcuni problemi se non adotti la ricorsione vai letteralmente al manicomio. Non so mi viene in mente (programmi passati in C)
l'ispezione di una cartella, che ne può contenere altre, che a loro volta ne contengono altre a 'mo' di scatola cinese.
Ricorsivamente in poche righe te la cavi, a stack esplicito, rischi d'impazzire.
Adesso provo a guardare il tuo codice, nel limite della mia ignoranza... :D
Ps: strano che abbia perso l'identazione, ho fatto copia-incolla. Se fosse identato male, non sarebbe partito nemmeno a me...bho....
Avatar utente
nuzzopippo
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 1624
Iscrizione: giovedì 12 ottobre 2006, 11:34

Re: [Python] esercizio parentesi

Messaggio da nuzzopippo »

gila75 [url=https://forum.ubuntu-it.org/viewtopic.php?p=5161310#p5161310][img]https://forum.ubuntu-it.org/images/icons/icona-cita.gif[/img][/url] ha scritto:Ciao @Nuzzo, si ho capito dopo la tua logica, va bhè, quello è il meno, lo si può tranquillamente lasciare così...
,,,
Ps: strano che abbia perso l'identazione, ho fatto copia-incolla. Se fosse identato male, non sarebbe partito nemmeno a me...bho....
No, non lo lascerò così ... vedrò di fare qualcosa di diverso dal Tuo codice (ora mi condiziona, motivo per cui non l'ho letto prima) ma che sia funzionante ... e, poi, la conseguenza logica dell'esercizio non è forse un "valutatore" di espressioni algebriche? ;)

Riguardo ai gap di indentazione capitano spesso nel copia-incolla con l'editor, in altri linguaggi spesso non sono evidenti, ma con python ...
:ciao:
Fatti non foste a viver come bruti ...
Avatar utente
Claudio_F
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 1463
Iscrizione: lunedì 28 maggio 2012, 18:49
Desktop: Mate/Gnome
Distribuzione: Ubu22.04

Re: [Python] esercizio parentesi

Messaggio da Claudio_F »

gila75 ha scritto:Ecco il codice, sicuramente sarà un orrore da principiante....pazienza, accetto volentieri consigli:
Non entro nel merito dell'algoritmo per... "inconsistenza delle specifiche" :p (possibilità di avere più parentesi dello stesso tipo consecutive ecc).

Riguardo il puro codice alcune note: non serve lavorare con liste di caratteri (a meno di non volerli modificare), le stringhe sono già sequenze che accettano il test di appartenenza:

Codice: Seleziona tutto

if ch in "()[]{}"
Nella funzione 'verifica_st' non serve controllare ad ogni giro la disparità, e i messaggi sarebbe più logico farli stampare da chi ha chiesto la verifica dopo aver ottenuto il risultato. Il risultato può anche essere "parlante", ad esempio restituendo delle stringhe in chiaro invece che dei numeri:

Codice: Seleziona tutto

def verifica_st(st):
   if len(st) & 1:
      return "dispari"
   if all(ch in "()[]{}" for ch in st):
      return "verifok"
   return "charko"
Nella funzione 'parentesi' iterare tramite l'indice 'i' è effettivamente non pythonico. Le sequenze accettano anche l'indice negativo che parte dalla fine (-1 è l'ultimo elemento, non serve fare calcoli con len). Flag binari di nome anonimo meglio sostituirli con dei booleani con nome esplicito:

Codice: Seleziona tutto

for ch in st_list:
   if ch == '[': stack.append('q') 
   if !error:
      if len(stack)>1  and  ((ord(stack[-1])) - (ord(stack[-2]))  <  0):
         print("errore priorità")
         error = True
Ps: strano che abbia perso l'identazione, ho fatto copia-incolla. Se fosse identato male, non sarebbe partito nemmeno a me...bho....
Hai mischiato spazi e tabulazioni, questo causa errori di visualizzazione...
Non so bene in Python, ma una volta avevo trovato un esempio in C (forse Fibonacci, non ricordo), con 2 versioni:
tradizionale e ricorsiva, ebbene, quella ricorsiva all'aumentare dell'input ad un certo punto andava in crash.
Anche prima di fallire comunque era più lenta. Se ci si pensa, una funzione che richiama se stessa, carica i valori, "impigna" nello stack ecc...
La ricorsione in Pyhton è doppiamente pesante, tra l'altro è impostato per default un limite di circa 900 livelli (non ricordo dove si può modificare). MA... qui viene in aiuto la memoizzazione, che elimina la pesantezza della ricorsione completa riducendo di centinaia di volte i tempi di risposta di quelle funzioni che devono ricalcolare spesso gli stessi valori partendo dagli stessi parametri :)


EDIT: trovato, modulo 'sys' funzioni 'getrecursionlimit' e 'setrecursionlimit'... hanno alzato il limite a 1000 :lol:
gila75
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 2739
Iscrizione: mercoledì 16 gennaio 2013, 17:28
Desktop: ubuntu-2d
Distribuzione: Ubuntu 12.04.2 LTS i686
Località: Airuno(Lecco)

Re: [Python] esercizio parentesi

Messaggio da gila75 »

Sempre ottimi consigli @Claudio, grazie ;)
Non entro nel merito dell'algoritmo per... "inconsistenza delle specifiche" :p (possibilità di avere più parentesi dello stesso tipo consecutive ecc).
Qui non ho capito: in che senso ? Ovvio che (()) ha poco senso ? cosa intendi ?
Nella funzione 'verifica_st' non serve controllare ad ogni giro la disparità,
e ma... a ogni input devo controllare no? Noto che tu l'hai (giustamente) spostato sopra: se dispari, non controllare nemmeno giusto?
Riguardo il puro codice alcune note: non serve lavorare con liste di caratteri (a meno di non volerli modificare), le stringhe sono già sequenze che accettano il test di appartenenza:
Vero, mi sono reso conto questo pomeriggio... mentre pensavo ad altro (inesperienza e mancanza di pratica)
Nella funzione 'parentesi' iterare tramite l'indice 'i' è effettivamente non pythonico. Le sequenze accettano anche l'indice negativo che parte dalla fine (-1 è l'ultimo elemento, non serve fare calcoli con len). Flag binari di nome anonimo meglio sostituirli con dei booleani con nome esplicito:
anche qui, cose studiate, ma come sopra ,la poca pratica mi fa scordare le cose.
...MA... qui viene in aiuto la memoizzazione, che elimina la pesantezza della ricorsione ...
Intravedo una cosa molto interessante che verrà moooolto dopo. Se non erro ho "leggiucchiato" da qualche parte la tecnica dei "suggerimenti"
o qualcosa del genere, che tiene traccia...non so. Tecniche avanzate che per ora non mi riguardano.
Domanda: vai pure deciso, non mi offendo.
Secondo te la tecnica di passare lettere t,g,q è buona o è una caxxata ? Mi sembra possa risparmiare qualche confronto, magari
posso usare un dizionario, non so.
Aggiorno il codice con i suggerimenti e quando pronto lo posto.
Intanto grazie :)
Avatar utente
Claudio_F
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 1463
Iscrizione: lunedì 28 maggio 2012, 18:49
Desktop: Mate/Gnome
Distribuzione: Ubu22.04

Re: [Python] esercizio parentesi

Messaggio da Claudio_F »

gila75 ha scritto:Qui non ho capito: in che senso ? Ovvio che (()) ha poco senso ? cosa intendi ?
Non esiste alcun senso oltre quello che noi vogliamo dare a qualcosa.
Ecco, non ho ben capito il senso che *tu* vuoi dare. :lol:
Se dici che:
- possono esserci al massimo tre livelli di parentesi (tanti quanti i tipi possibili di parentesi)
AND
- che una graffa deve esempre essere la più esterna e una tonda la più interna
allora questa sequenza secondo te (per il senso in cui la intendi) è corretta? Cioè deve passare l'esame?

() { () [ () ] } [] [ () () ] {} { [] [] [ () () ] () }
spostato sopra: se dispari, non controllare nemmeno giusto?
Giusto, basta un solo controllo.
Tecniche avanzate che per ora non mi riguardano.
Ma no, è semplicissima: una funzione usa un dizionario per memorizzare e associare i parametri alla risposta calcolata. Quando viene chiamata di nuovo cerca prima nel dizionario se trova la risposta precalcolata. Mano a mano che viene usata il dizionario cresce e la funzione calcola sempre di meno (se sono compiti lunghi i vantaggio diventa enorme).
Secondo te la tecnica di passare lettere t,g,q è buona o è una caxxata ? Mi sembra possa risparmiare qualche confronto
Non ho approfondito, attendiamo il codice nuovo ;)
gila75
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 2739
Iscrizione: mercoledì 16 gennaio 2013, 17:28
Desktop: ubuntu-2d
Distribuzione: Ubuntu 12.04.2 LTS i686
Località: Airuno(Lecco)

Re: [Python] esercizio parentesi

Messaggio da gila75 »

() { () [ () ] } [] [ () () ] {} { [] [] [ () () ] () }
Porco cane Claudio :D :devilmad: mi metti in difficoltà...in teoria essendoci spazi mi viene respinta, non calcolavo questa ipotesi.
a me interessavo più che altro l'allineamento, in fondo è solo un esercizio di programmazione, non un'applicazione matematica.
Poi come "di più" ho aggiunto le priorità
Non ho approfondito, attendiamo il codice nuovo ;)
Si ,alcune modifiche le ho in mente. Appena ho tempo riscrivo
gila75
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 2739
Iscrizione: mercoledì 16 gennaio 2013, 17:28
Desktop: ubuntu-2d
Distribuzione: Ubuntu 12.04.2 LTS i686
Località: Airuno(Lecco)

Re: [Python] esercizio parentesi

Messaggio da gila75 »

Ecco, una prima bozza, mi piace molto di più così.
Mancano alcuni controlli e ritocchi (consigliati nel post precedente), ma mi sembra molto più in stile python:

Codice: Seleziona tutto

def verifica_st(st):
	if len(st)%2!=0:
			print ("parentesi dispari, allineamento NON corretto")
			return 0
	tabella='()[]{}'	
	for i in st:
		if i not in tabella:
			print("caratteri NON consentiti, riscrivi")
			return 0
	else:
		return 1
#-----------------------------------------------------
def parentesi(st):
	pop_par  ='([{'
	stack=[]
	tab_p={'(':'t', '[':'q', '{':'g', ')':'T', ']':'Q', '}':'G' }
	for i in st:
		if i in pop_par:
			stack.append(tab_p[i])
			if len(stack)>1:
				if ord(stack [-1])-ord (stack [-2])<0:
					print("priorità non ok")
		else:
			stack.append(tab_p[i])
			if len(stack)>1:
				if stack [-1].lower()==stack[-2]:
					stack.pop();stack.pop()
			else:
				return len(stack)
	return len(stack)
#------------------------------------------------------						
while True:
	st=input("inserisci espressione ")
	print("espressione da valutare: ",st)
	res=verifica_st(st)
	if res==1:
		x=parentesi(st)
		if x==0:
			print ('allineamento:OK')
		else:
			print ('allineamento: NON OK, uscita stack:',x)
		
	




sto testando eventuali bug, che sono sempre dietro l'angolo

EDIT @Claudio:
(){()[()]}[][()()]{}{[][][()()]()}
Rimossa da spazi mi dice che l'allineamento è ok, e anche la priorià.In questo caso però la priorità non è ok.
Diciamo che la priorità è un di più, e questi casi limiti non li avevo calcolati:

Codice: Seleziona tutto

inserisci espressione []{[()]}
espressione da valutare:  []{[()]}
allineamento:OK
inserisci espressione 
le prime quadre non hanno motivo di esistere, dovrebbero essere tonde.
Io l'avevo intesa così:

Codice: Seleziona tutto

inserisci espressione [][{()}]
espressione da valutare:  [][{()}]
priorità non ok
allineamento:OK
inserisci espressione 


Poco male, spunto per un nuovo esercizio. Ma m'interessa molto di più se il codice aggiornato è migliore
Avatar utente
nuzzopippo
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 1624
Iscrizione: giovedì 12 ottobre 2006, 11:34

Re: [Python] esercizio parentesi

Messaggio da nuzzopippo »

Siete andati avanti, ragazzi ...
beh ... quel link che ho postato prima (senso o non senso) lo riteneva ammissibile
Claudio_F ha scritto: Non esiste alcun senso oltre quello che noi vogliamo dare a qualcosa.
...
allora questa sequenza secondo te (per il senso in cui la intendi) è corretta? Cioè deve passare l'esame?

() { () [ () ] } [] [ () () ] {} { [] [] [ () () ] () }
beh ... un discorso "parentesi", sussiste se focalizzato, ritengo le operazioni algebriche una buona linea di criterio, letto quello che avete detto sulla ricorsione, si può fare tranquillamente senza ... propongo un metodo estratto da una classe per un oggetto "Espressione" che avevo avviato ieri ed ho dovuto interrompere :

Codice: Seleziona tutto

p_tipi = {'{': '}',
          '[': ']',
          '(': ')',
          }

def __evaluate_blocks(val):
    ''' Verifica la congruenza delle parentesi presenti.'''
    par = list(val.replace(' ', ''))
    if len(par) % 2: return False
    continua = True
    key = '('
    while continua:
        ch = p_tipi[key]
        if ch in par:
            i_ch = par.index(ch)
            if i_ch == 0:
                return False
            if par[i_ch - 1] != key:
                return False
            else:
                del par[i_ch]
                del par[i_ch -1]
        else:
            if key == '(':
                key = '['
            elif key == '[':
                key = '{'
            else:
                continua = False
        if len(par) < 2:
            continua = False
    if len(par) > 0:
        return False
    return True

if __name__ == '__main__':
    imm = ' '
    while imm:
        imm = input('Inserire espressione : ')
        if imm:
            ris = __evaluate_blocks(imm)
            if ris:
                print(imm, '- Valida')
            else:
                print(imm, ' - NON valida')
Il metodo valuta "la coerenza" di eventuali blocchi di operazioni (eventuali parentesi presenti), e permette anche anche gli annidamenti di parentesi simili (di qualunque tipo) ma NON permette violazioni dei livelli "{[()]}", se presenti.

Un esempio di output (quello ipotizzato da @Claudio_F compreso)

Codice: Seleziona tutto

>>> %Run vedi_par_2.py
Inserire espressione : {[()()](())}
{[()()](())} - Valida
Inserire espressione : [{()()}]
[{()()}]  - NON valida
Inserire espressione : ((
((  - NON valida
Inserire espressione : () { () [ () ] } [] [ () () ] {} { [] [] [ () () ] () }
() { () [ () ] } [] [ () () ] {} { [] [] [ () () ] () } - Valida
Inserire espressione : 
>>> 
Fatti non foste a viver come bruti ...
gila75
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 2739
Iscrizione: mercoledì 16 gennaio 2013, 17:28
Desktop: ubuntu-2d
Distribuzione: Ubuntu 12.04.2 LTS i686
Località: Airuno(Lecco)

Re: [Python] esercizio parentesi

Messaggio da gila75 »

Mannaggia @Nuzzo, purtroppo sulle classi sto a zero.
Io ho modificato il mio codice, vedi ( se vuoi) se ti piace
Avatar utente
nuzzopippo
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 1624
Iscrizione: giovedì 12 ottobre 2006, 11:34

Re: [Python] esercizio parentesi

Messaggio da nuzzopippo »

gila75 [url=https://forum.ubuntu-it.org/viewtopic.php?p=5161657#p5161657][img]https://forum.ubuntu-it.org/images/icons/icona-cita.gif[/img][/url] ha scritto:Mannaggia @Nuzzo, purtroppo sulle classi sto a zero.
Io ho modificato il mio codice, vedi ( se vuoi) se ti piace
Il codice è stato adattato per essere una funzione "indipendente" e ... parte dalle parentesi di chiusura :P
Il Tuo lo guarderò prossimamente per bene, Tu guarda il mio, mi è uscito "di getto" e mi è sembrato "carino" come algoritmo-
Fatti non foste a viver come bruti ...
gila75
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 2739
Iscrizione: mercoledì 16 gennaio 2013, 17:28
Desktop: ubuntu-2d
Distribuzione: Ubuntu 12.04.2 LTS i686
Località: Airuno(Lecco)

Re: [Python] esercizio parentesi

Messaggio da gila75 »

Ok, ci provo...
Avatar utente
nuzzopippo
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 1624
Iscrizione: giovedì 12 ottobre 2006, 11:34

Re: [Python] esercizio parentesi

Messaggio da nuzzopippo »

Ciao, appena guardato, buono ma "entra in crisi" con gli spazi, tipo nella proposta di @Claudio_F ... correzione facile, basta fare così :

Codice: Seleziona tutto

while True:
    st=input("inserisci espressione ")
    print("espressione da valutare: ",st)
    st =st.replace(' ', '')                                       <--- inserisci questa
    res=verifica_st(st)
   
Per il resto, personalmente, non ho niente da dire, mi sembra una buona impostazione, coerente ai risultati che vuoi conseguire (nel mio ultimo esempio ho "deviato", punto ad altro, ma basterebbe qualche "print")

Una osservazione : l'input su loop infinito a me non piace molto, basterebbe controllare che l'utente non abbia inserito niente, guarda nel main del mio precedente esempio per vedere applicata la cosa.

[Edit] ... riguardo la priorità "non buona" dell'esempio di Claudio, non sarei tanto d'accordo ... richiamando l'equivalenza tra le parentesi indicata nel brano di wikipedia da me citato, la "comodità" non sarebbe da ritenersi regola ... inoltre in condizioni di annidamento superiori a tre livelli come si metterebbe? ... ha ben ragione a dire che "le specifiche" devono essere "consistenti" nella loro definizione.
Fatti non foste a viver come bruti ...
gila75
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 2739
Iscrizione: mercoledì 16 gennaio 2013, 17:28
Desktop: ubuntu-2d
Distribuzione: Ubuntu 12.04.2 LTS i686
Località: Airuno(Lecco)

Re: [Python] esercizio parentesi

Messaggio da gila75 »

Una osservazione : l'input su loop infinito a me non piace molto, basterebbe controllare che l'utente non abbia inserito niente, guarda nel main del mio precedente esempio per vedere applicata la cosa.
Si, è solo un trucchetto per avere input multipli senza rilanciare ogni volta, per eventuali bug, solo per velocizzare.
[Edit] ... riguardo la priorità "non buona" dell'esempio di Claudio, non sarei tanto d'accordo ... richiamando l'equivalenza tra le parentesi indicata nel brano di wikipedia da me citato, la "comodità" non sarebbe da ritenersi regola ... inoltre in condizioni di annidamento superiori a tre livelli come si metterebbe? ... ha ben ragione a dire che "le specifiche" devono essere "consistenti" nella loro definizione
Si, tralasciamo per un attimo le priorità. Quando e se avremo voglia, possiamo fare un nuovo esercizio, con regole ben precise no?
Posto il mio codice definitivo, scremato appunto, dalle priorità.
Sono abbastanza soddisfatto perchè sono riuscito (a mio avviso a contenere gli if, che non mi piacciono mai troppo)
Ecco:

Codice: Seleziona tutto

def verifica_st(st):
	if len(st)%2!=0:
			print ("parentesi dispari, allineamento NON corretto")
			return False
	tabella='()[]{}'	
	for i in st:
		if i not in tabella:
			print("caratteri NON consentiti, riscrivi")
			return False
	else:
		return True
#-----------------------------------------------------
def parentesi(st):
	pop_par  ='([{'
	stack=[]
	tab_p={'(':'t', '[':'q', '{':'g', ')':'T', ']':'Q', '}':'G' }
	for i in st:
		if i in pop_par:
			stack.append(tab_p[i])
		else:
			stack.append(tab_p[i])
			if len(stack)>1:
				if stack [-1].lower()==stack[-2]:
					stack.pop();stack.pop()
			else:
				return len(stack)
	return len(stack)
#------------------------------------------------------						
while True:
	st=input("inserisci espressione ")
	print("espressione da valutare: ",st)
	res=verifica_st(st)
	if res==True:
		x=parentesi(st)
		if x==False:
			print ('allineamento:OK')
		else:
			print ('allineamento: NON OK, uscita stack:',x)
		
	




Sto guardando il tuo codice Nuzzo, con calma.... :D , e intanto ti ringrazio per gli spunti e la partecipazione.
Sentiamo il buon @Claudio se ha ulteriori consigli.
Scrivi risposta

Ritorna a “Programmazione”

Chi c’è in linea

Visualizzano questa sezione: 0 utenti iscritti e 11 ospiti