Pages: [1]   Go Down
Print
Author Topic: Esercizi di Programmazione  (Read 1059 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
milos224
Forumista
***
Offline Offline

Posts: 830


« on: 19-09-2011, 21:30:41 »

Apro questo topic per vedere un pò insieme le esercitazioni per la prova del 4 ottobre. Comiciamo da questo: non ho capito bene il testo. Quando dice si utilizzi la classe ottenuta per la realizzazione del seguente problema, devo praticamente fare uno stack e inserire di volta in volta le stringhe? E poi ovviamente risolvere il problema?

"La parentesi quadra"
Si realizzi un'implementazione dell'interfaccia Stack<E> (come mostrato a lezione) e si utilizzi la classe ottenuta per la realizzazione del seguente problema legato alle sequenza parentesizzate.
Una sequenza S si dice parentesizzata se
– è formata da una coppia di parentesi, una aperta e l'altra chiusa. Esempio: S = ( )
– è la concatenazione di due sequenze parentesizzate, S1 ed S2. Esempio: S1 S2
– è data da una sequenza parentesizza, S, racchiusa tra parentesi Esempio: ( S )

Si fornisca un programma Java che prenda in input un file di testo contenente una lista di sequenze di parentesi, una per riga, e permetta di controllare se tali sequenze siano delle sequenza parentesizzate.

Input
Il file di input contiene una sequenza di sequenze, una per riga, terminanti con il simbolo “ ;” (punto e virgola). Ciascuna sequenza contiene una lista di simboli di parentesi tra: (, [, {, < >, }, ], )

Output
il file di output contiene una riga per ogni sequenza di input. La riga contiene la stringa 'Ok' se la relativa sequenza è parentesizzata, altrimenti contiene la stringa 'Errore'.
Esempio
Input.txt
  <[(())]>;
  {<}}[](<{});
  <>()<<>>;
  (<<>{}>);
  {{}[];
  ()<<<({})>>>;
  {[]}<>;
  <>({<>};
Output.txt
  Ok
  Errore
  Ok
  Ok
  Errore
  Ok
  Ok
  Errore

Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #1 on: 19-09-2011, 22:10:17 »

Si ricordo questo esercizio, non l' ho saputo fare a suo tempo, non capivo........navigando sul web ho trovato una cosa che...forse...può essere utile:

Code:
public boolean parentesizzata ( char[] a )
{
Stack stack=new Stack();
for(int i=0; i<a.length(); i++)
{ if     ( a[i]==’{’  ||  a[i]==’[’  ||   a[i]==’(’   )
                        stack.push(a[i]);
   if     (  a[i]==’}’  ||  a[i]==’]’)   ||    a[i]==’)’   )
             if   (  stack.isEmpty() )  return false;
                   else { if     ( a[i]==’}’  &&  stack.pop()!=’{’ )     return false;
  if     ( a[i]==’]’  &&  stack.pop()!=’[’ )     return false;
  if     ( a[i]==’)’  &&  stack.pop()!=’(’ )     return false;  };
}
return (stack.isEmpty());
}

Domani se ho tempo mi ci dedico...da quel codice dovresti ricavare un possibile procedimento. Oppure, dimmi se ci sono progressi, in caso contrario...riprovo a fare questo esercizio.
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
milos224
Forumista
***
Offline Offline

Posts: 830


« Reply #2 on: 19-09-2011, 23:31:07 »

Si ricordo questo esercizio, non l' ho saputo fare a suo tempo, non capivo........navigando sul web ho trovato una cosa che...forse...può essere utile:

Code:
public boolean parentesizzata ( char[] a )
{
Stack stack=new Stack();
for(int i=0; i<a.length(); i++)
{ if     ( a[i]==’{’  ||  a[i]==’[’  ||   a[i]==’(’   )
                        stack.push(a[i]);
   if     (  a[i]==’}’  ||  a[i]==’]’)   ||    a[i]==’)’   )
             if   (  stack.isEmpty() )  return false;
                   else { if     ( a[i]==’}’  &&  stack.pop()!=’{’ )     return false;
  if     ( a[i]==’]’  &&  stack.pop()!=’[’ )     return false;
  if     ( a[i]==’)’  &&  stack.pop()!=’(’ )     return false;  };
}
return (stack.isEmpty());
}

Domani se ho tempo mi ci dedico...da quel codice dovresti ricavare un possibile procedimento. Oppure, dimmi se ci sono progressi, in caso contrario...riprovo a fare questo esercizio.
Io ho fatto così. Creato la classe Stack con capacità 10000 (le stringhe in input sono più di 8000) e man mano che le prendo in input le memorizzo nello stack. Mentre controllo (tramite il top che mi da l'ultima stirnga inserita) se sono parentesizzate o meno: se la lunghezza senza il ";" finale che si trova a fine stringa è dispari, sicuramente devo dare "Errore". Altrimenti controllo che ci siano lo stesso numero dello stesso tipo di parentesi. Tutto funziona.
Volevo però migliorarlo: ovvero prima memorizzare tutto nello stack e perciò chiudere il file in input dato che non mi serve più. E poi man mano prendere la stringa top dello stack e verificare. Però in questo modo l'output sarà al contrario: ovvero il primo risultato si riferirà all'ultima stringa di input che è stata inserita per ultime e si trova al top dello stack. Dovrei in questo caso inserire le stringhe a partire dal basso e non penso si possa fare..

Comunque forse ho scritto troppe cavolate visto l'orario per cui a domani!

Code:
import java.io.*;

class Stack{
   
    private int cap=10000;
    private String Input[]= new String[cap];
    int size=0;
   
    public int size(){
        return size;
    }
   
    public void push(String s){
        Input[size]=s;
        size++;
    }
   
    public String Top(){
        return Input[size-1];
    }
   
    public String Pop(){
        String Pop;
        Pop=Input[size-1];
        Input[size-1]=null;
        size--;
        size--;
        return Pop;
    }
   
    public boolean isEmpty(){
        if(size==0)
            return true;
        else
            return false;
    }
}

public class LaParentesiQuadra{
   
    public static void main(String[] args) throws IOException{
       
        Stack Parentesi=new Stack();
        BufferedReader bfr = new BufferedReader(new FileReader("/Users/Salvuccio/Desktop/Ciao.txt"));
        BufferedWriter bfw = new BufferedWriter(new FileWriter("/Users/Salvuccio/Desktop/OutputStack.txt"));
       
        String buf;
        for(int i=0; (buf=bfr.readLine())!=null ; i++){
            Parentesi.push(buf);
           
            if ((Parentesi.Top().length()-1) % 2 == 0){   //Controllo se la lunghezza della stringa(senza il ";" finale) al top dello stack sia pari
                int tondeaperte=0,tondechiuse=0,quadreaperte=0,quadrechiuse=0,graffeaperte=0,graffechiuse=0;
                for(int j=0; j<Parentesi.Top().length()-1; j++)
                    if (Parentesi.Top().charAt(j)=='('){
                        tondeaperte++;}
                    else if (Parentesi.Top().charAt(j)==')'){
                        tondechiuse++;}
                    else if (Parentesi.Top().charAt(j)=='['){
                        quadreaperte++;}
                    else if (Parentesi.Top().charAt(j)==']'){
                        quadrechiuse++;}
                    else if (Parentesi.Top().charAt(j)=='{'){
                        graffeaperte++;}
                    else if (Parentesi.Top().charAt(j)=='}'){
                        graffechiuse++;}
               
                if (tondeaperte==tondechiuse && quadreaperte==quadrechiuse && graffeaperte==graffechiuse){
                    bfw.write("OK\n");
                }
            }
           
            else{              //se è dispari sicuro non è parentesizzata
                 bfw.write("Errore\n");
            }
        }
       
        bfr.close();
        bfw.close();
    }
}             
               
« Last Edit: 20-09-2011, 00:50:01 by milos224 » Logged
zElOtO
Forumista
***
Offline Offline

Gender: Male
Posts: 845



WWW
« Reply #3 on: 20-09-2011, 13:35:39 »

Potete vedere la soluzione dell'esercizio qui

 pc
Logged

I computer sono incredibilmente veloci, accurati e stupidi. Gli uomini sono incredibilmente lenti, inaccurati e intelligenti. Insieme sono una potenza che supera l'immaginazione. (A. Einstein)

Damiano Cancemi
www.damianocancemi.com
www.nerdbren.com
www.nerdbren.com/blog
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #4 on: 20-09-2011, 14:01:36 »

Potete vedere la soluzione dell'esercizio qui

 pc

The link does not funge.  

http://damianoc90.altervista.org/index.php?option=com_content&view=article&id=88:la-parentesi-quadra&catid=35:programmazione-2&Itemid=53

P.S carino come hai rifatto il sito Cheesy
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
fabryxio
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 343

Chi l'ha duro....... l'ha duro!


WWW
« Reply #5 on: 20-09-2011, 15:51:53 »

Io odio Joomla :S
« Last Edit: 20-09-2011, 15:54:24 by fabryxio » Logged

LtWorf
Forumista Esperto
****
Offline Offline

Posts: 1.079

Ogni cosa da me scritta è da intendersi come opinione personale e non come dato di fatto. Anche le eventuali dimostrazioni matematiche da me scritte saranno opinioni personali e quindi dovranno venire dimostrate da una terza parte di fiducia


WWW
« Reply #6 on: 20-09-2011, 22:22:57 »

Ma non credi che quei
if (x.charAt(a) == ....

potessero essere convertiti con uno switch?

Inoltre, la soluzione è errata, ad esempio la sequenza: "<(>)" viene riconosciuta come buona, mentre da definizione non dovrebbe esserlo.
Logged

There are some OO programming languages. I will create the first -_-' language.

LtWorf
LtWorf
Forumista Esperto
****
Offline Offline

Posts: 1.079

Ogni cosa da me scritta è da intendersi come opinione personale e non come dato di fatto. Anche le eventuali dimostrazioni matematiche da me scritte saranno opinioni personali e quindi dovranno venire dimostrate da una terza parte di fiducia


WWW
« Reply #7 on: 20-09-2011, 22:48:48 »

Io l'ho risolto così (è python ma l'idea alla base si dovrebbe capire spero)

la variabile d è un dizionario, associo ad ogni chiudi parentesi il suo corrispettivo apri parentesi.
Quando trovo un apri parentesi lo metto sullo stack
Quando trovo un chiudo parentesi faccio un pop dallo stack e controllo che l'elemento che mi viene restituito sia l'apri parentesi corrispettivo del chiudi parentesi che ho trovato.
Se trovo un chiudi parentesi e lo stack è vuoto restituisco false

Alla fine se tutti i chiudi parentesi corrispondevano, controllo che lo stack sia vuoto e in quel caso restituisco vero

Code:
def do_it( string ):
  d={'>':'<',')':'(',']':'[','}':'{'}
 
  s=[]
  res=True
 
  for i in string:
    if i in ('<','(','{','['):
      s.append(i)
    elif i in d:
      if len(s)==0 or d[i]!=s.pop():
        res= False
        break
    else: #Non è una parentesi
      res=False
      break
   
  res= res and len(s)==0
  return res
Logged

There are some OO programming languages. I will create the first -_-' language.

LtWorf
zElOtO
Forumista
***
Offline Offline

Gender: Male
Posts: 845



WWW
« Reply #8 on: 26-09-2011, 02:22:45 »

Potete vedere la soluzione dell'esercizio qui

 pc

The link does not funge.  

http://damianoc90.altervista.org/index.php?option=com_content&view=article&id=88:la-parentesi-quadra&catid=35:programmazione-2&Itemid=53

Il link funziona! Grazie per il sito comunque!  ok


P.S carino come hai rifatto il sito Cheesy
Logged

I computer sono incredibilmente veloci, accurati e stupidi. Gli uomini sono incredibilmente lenti, inaccurati e intelligenti. Insieme sono una potenza che supera l'immaginazione. (A. Einstein)

Damiano Cancemi
www.damianocancemi.com
www.nerdbren.com
www.nerdbren.com/blog
Pages: [1]   Go Up
Print
Jump to: