[Python] esercizio parentesi

Linguaggi di programmazione: php, perl, python, C, bash, ecc.

[Python] esercizio parentesi

Messaggioda gila75 » giovedì 7 novembre 2019, 10:59

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
gila75
Imperturbabile Insigne
Imperturbabile Insigne
 
Messaggi: 2607
Iscrizione: gennaio 2013
Località: Airuno(Lecco)
Desktop: ubuntu-2d
Distribuzione: Ubuntu 12.04.2 LTS i686

Re: [Python] esercizio parentesi

Messaggioda nuzzopippo » giovedì 7 novembre 2019, 16:23

gila75 Immagine 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"
Avatar utente
nuzzopippo
Entusiasta Emergente
Entusiasta Emergente
 
Messaggi: 1311
Iscrizione: ottobre 2006

Re: [Python] esercizio parentesi

Messaggioda gila75 » giovedì 7 novembre 2019, 17:19

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
Avatar utente
gila75
Imperturbabile Insigne
Imperturbabile Insigne
 
Messaggi: 2607
Iscrizione: gennaio 2013
Località: Airuno(Lecco)
Desktop: ubuntu-2d
Distribuzione: Ubuntu 12.04.2 LTS i686

Re: [Python] esercizio parentesi

Messaggioda gila75 » giovedì 7 novembre 2019, 20:20

@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
gila75
Imperturbabile Insigne
Imperturbabile Insigne
 
Messaggi: 2607
Iscrizione: gennaio 2013
Località: Airuno(Lecco)
Desktop: ubuntu-2d
Distribuzione: Ubuntu 12.04.2 LTS i686

Re: [Python] esercizio parentesi

Messaggioda nuzzopippo » venerdì 8 novembre 2019, 8:59

gila75 Immagine 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.
Avatar utente
nuzzopippo
Entusiasta Emergente
Entusiasta Emergente
 
Messaggi: 1311
Iscrizione: ottobre 2006

Re: [Python] esercizio parentesi

Messaggioda gila75 » venerdì 8 novembre 2019, 10:02

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
gila75
Imperturbabile Insigne
Imperturbabile Insigne
 
Messaggi: 2607
Iscrizione: gennaio 2013
Località: Airuno(Lecco)
Desktop: ubuntu-2d
Distribuzione: Ubuntu 12.04.2 LTS i686

Re: [Python] esercizio parentesi

Messaggioda nuzzopippo » venerdì 8 novembre 2019, 10:18

gila75 Immagine 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:
Avatar utente
nuzzopippo
Entusiasta Emergente
Entusiasta Emergente
 
Messaggi: 1311
Iscrizione: ottobre 2006

Re: [Python] esercizio parentesi

Messaggioda Claudio_F » venerdì 8 novembre 2019, 13:38

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:
Avatar utente
Claudio_F
Entusiasta Emergente
Entusiasta Emergente
 
Messaggi: 1416
Iscrizione: maggio 2012
Desktop: Unity/Mate/Gnome
Distribuzione: Ubu16.04/Mint17

Re: [Python] esercizio parentesi

Messaggioda gila75 » venerdì 8 novembre 2019, 17:31

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
gila75
Imperturbabile Insigne
Imperturbabile Insigne
 
Messaggi: 2607
Iscrizione: gennaio 2013
Località: Airuno(Lecco)
Desktop: ubuntu-2d
Distribuzione: Ubuntu 12.04.2 LTS i686

Re: [Python] esercizio parentesi

Messaggioda Claudio_F » venerdì 8 novembre 2019, 18:22

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 ;)
Avatar utente
Claudio_F
Entusiasta Emergente
Entusiasta Emergente
 
Messaggi: 1416
Iscrizione: maggio 2012
Desktop: Unity/Mate/Gnome
Distribuzione: Ubu16.04/Mint17

Re: [Python] esercizio parentesi

Messaggioda gila75 » venerdì 8 novembre 2019, 20:20

() { () [ () ] } [] [ () () ] {} { [] [] [ () () ] () }


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
Avatar utente
gila75
Imperturbabile Insigne
Imperturbabile Insigne
 
Messaggi: 2607
Iscrizione: gennaio 2013
Località: Airuno(Lecco)
Desktop: ubuntu-2d
Distribuzione: Ubuntu 12.04.2 LTS i686

Re: [Python] esercizio parentesi

Messaggioda gila75 » venerdì 8 novembre 2019, 21:26

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
gila75
Imperturbabile Insigne
Imperturbabile Insigne
 
Messaggi: 2607
Iscrizione: gennaio 2013
Località: Airuno(Lecco)
Desktop: ubuntu-2d
Distribuzione: Ubuntu 12.04.2 LTS i686

Re: [Python] esercizio parentesi

Messaggioda nuzzopippo » sabato 9 novembre 2019, 19:32

Siete andati avanti, ragazzi ...
gila75 Immagine ha scritto:Qui non ho capito: in che senso ? Ovvio che (()) ha poco senso ? cosa intendi ?


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 :
>>>
Avatar utente
nuzzopippo
Entusiasta Emergente
Entusiasta Emergente
 
Messaggi: 1311
Iscrizione: ottobre 2006

Re: [Python] esercizio parentesi

Messaggioda gila75 » sabato 9 novembre 2019, 19:47

Mannaggia @Nuzzo, purtroppo sulle classi sto a zero.
Io ho modificato il mio codice, vedi ( se vuoi) se ti piace
Avatar utente
gila75
Imperturbabile Insigne
Imperturbabile Insigne
 
Messaggi: 2607
Iscrizione: gennaio 2013
Località: Airuno(Lecco)
Desktop: ubuntu-2d
Distribuzione: Ubuntu 12.04.2 LTS i686

Re: [Python] esercizio parentesi

Messaggioda nuzzopippo » sabato 9 novembre 2019, 19:55

gila75 Immagine 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-
Avatar utente
nuzzopippo
Entusiasta Emergente
Entusiasta Emergente
 
Messaggi: 1311
Iscrizione: ottobre 2006

Re: [Python] esercizio parentesi

Messaggioda gila75 » sabato 9 novembre 2019, 20:03

Ok, ci provo...
Avatar utente
gila75
Imperturbabile Insigne
Imperturbabile Insigne
 
Messaggi: 2607
Iscrizione: gennaio 2013
Località: Airuno(Lecco)
Desktop: ubuntu-2d
Distribuzione: Ubuntu 12.04.2 LTS i686

Re: [Python] esercizio parentesi

Messaggioda nuzzopippo » domenica 10 novembre 2019, 9:46

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.
Avatar utente
nuzzopippo
Entusiasta Emergente
Entusiasta Emergente
 
Messaggi: 1311
Iscrizione: ottobre 2006

Re: [Python] esercizio parentesi

Messaggioda gila75 » domenica 10 novembre 2019, 11:01

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.
Avatar utente
gila75
Imperturbabile Insigne
Imperturbabile Insigne
 
Messaggi: 2607
Iscrizione: gennaio 2013
Località: Airuno(Lecco)
Desktop: ubuntu-2d
Distribuzione: Ubuntu 12.04.2 LTS i686


Torna a Programmazione

Chi c’è in linea

Visualizzano questa sezione: 0 utenti registrati e 5 ospiti