Δομές Δεδομένων

[theos]

Μάλλον δεν έχεις καταλάβει καλά τι κάνει η στοίβα. Η στοίβα, λοιπόν, κάνει pop το τελευταίο στοιχείο που έγινε pushed. Συνεπώς, δεν κάνει pop όποιο στοιχείο γουστάρει. Πάμε πιο αναλυτικά:

Η έκφραση είναι σωστή: (())()
Ελπίζω να το βλέπεις τώρα...

Πάμε ένα άλλο παράδειγμα: [(())()[(())]] Βάλε χρωματάκια και εδώ να δεις ότι είναι σωστή η έκφραση. Βάζω τι θα έχει η στοίβα σε κάθε βήμα. Όταν ξεκινάει ο αλγόριθμος η στοίβα είναι άδεια:

{Y}
{Y,X}
{Y,X,X} (Όπως βλέπεις γίνεται pop αναγκαστικά το στοιχείο που βρίσκεται δεξιά δεξιά αφού η στοίβα είναι LIFO
{Y,X}
{Y}
{Y,X}
{Y}
{Υ,Υ} (αν μετά από αυτό το βήμα είχαμε δεξιά παρένθεση θα γινόταν pop το Υ και θα σταματούσε ο αλγόριθμος αφού δεξιά παρένθεση απαιτεί pop X)
{Y,Y,X}
{Y,Y,X,X} (αν πάλι μετά από αυτό το βήμα είχαμε δεξιά αγκύλη θα γινόταν pop το Χ και θα σταματούσε ο αλγόριθμος αφού δεξιά αγκύλη απαιτεί pop Υ)
{Υ,Υ,Χ}
{Υ,Υ}
{Υ}
{}
Η έκφρασή μας τελειώνει εδώ. Ο αλγόριθμος ελέγχει αν η στοίβα είναι άδεια τώρα. Βλέπει ότι όντως είναι άδεια και επιστρέφει ότι η έκφραση είναι σωστή

Ελπίζω να το κατάλαβες τώρα

[f_angel]

Γνωρίζετε αν μπορώ να πάρω το βιβλίο του μαθήματος με ταυτότητα (δηλ χωρίς πάσο)?

[el_greco]

Μπορείς, αρκεί να είσαι στη λίστα... εγώ που δεν έχω πάσο το πήρα κανονικά με την ταυτότητα.

[brian]

paidia mporei kapoios pou to parakolouthouse tora na mas pei an ekane sto teleftaio mathima mia megali askisi me ena keimeno pou metraei kati lekseis kai zitaei diafora?

[DrCox]

nai paidia auto to thema an ginetai kapoios na to eksigisei...

[theos]

Ποιό θέμα? Εκφώνηση πείτε

[DrCox]

thema 5 kanoniki 2007..kati me kadous den einai kai doxeia..?kapws etsi den lynetai..?episis stin askisi me tis agkyles kai tis parentheseis...arkei na tou to grapsoume me logia opws mas edeikses esy,i mipws thelei kai ton kwdika ths java..?

[theos]

Στο θέμα με τις παρενθέσεις και τις αγκύλες όπως και σε κάθε θέμα στις δομές που ζητείται αλγόριθμος, πρέπει να γραφεί ένας αλγόριθμος. Αυτό που γράφω εγώ παραπάνω με λόγια δεν είναι αλγόριθμος, αλλά μια επεξήγηση του τι θα πρέπει να κάνει ο αλγόριθμος που καλείστε να γράψετε.

Παρόλα αυτά ένας αλγόριθμος μπορεί να είναι λόγια αλλά θα πρέπει να έχει συγκεκριμένα βήματα. Δηλαδή στην ουσία θα είναι σαν μια δική σου γλώσσα προγραμματισμού που θα κάνει τα ίδια πράγματα που κάνει η java μόνο που θα τα κάνει με διαφορετικές εντολές. Για παράδειγμα:

Αρχή αλγορίθμου
Δημιούργησε στοίβα s
i=1
Επανάλαβε μέχρι το ι να γίνει το τελευταίο στοιχείο της έκφρασης
Διάβασε το i-οστό στοιχείο της έκφρασης
Αν διάβασες "(" κάνε push X
Αν διάβασες ")" και isempty==false κάνε pop
Αν το στοιχείο που έγινε pop ήταν ")" γράψε λάθος έκφραση και τέλος αλγορίθμου
Αν διάβασες ")" και isempty==true γράψε λάθος και τέλος αλγορίθμου
ι=ι+1
Τέλος επανάληψης

isempty==true γράψε σωστή έκφραση
isempty==false γράψε λάθος έκφραση
Τέλος αλγορίθμου

Το παραπάνω είναι αλγόριθμος... Παρόλα αυτά σε τέτοια μαθήματα συνηθίζεται να γράφεις τους αλγόριθμους σε μορφή κάποιου κώδικα. Κανονικά το παραπάνω θα έπρεπε να βαθμολογηθεί ως σωστό, όμως όποιοι ξέρετε το Συμβώνη θα ξέρετε και ότι είναι λίγο παράξενος και βαθμολογεί και λίγο περίεργα... Οπότε καλό είναι να το γράψετε σε μορφή ενός απλοϊκού κώδικα για να είστε σίγουροι...

Για το τελευταίο θέμα... εκφώνηση

[DrCox]

theos i ekfwnisi des tin apo ta themata pou exei stin arxiki selida..kanoniki tou 2007 thema 5.'' ena programma analysis keimenou diabazei ena keimeno kai ypologizei ton arithmo twn leksewn pou exei to keimeno,twn arithmo twn diakritwn leksewn kai tis (k) pio syxna emfanizomenes lekseis se fthinousa seira me basi ton arithmo emfanisis tous.px mia typiki eksodos mporei na einai :
to arxeio periexei 2586 lekseies.yparxoun 931 diaforetikes lekseis
37 o
37 algorithmoi
32 kai
31 domes
h timi tou k einai mia parametros tou programmatos.an yparxoun ligoteres apo k diakrites leklseis
tote ektypwnontai oles. yparxoun polles luseis me (diaforetiki asymptwtiki apodosi) sto programma tis analysis keimenou. skopos seinai na paraxthei mia lysi i opoia einai grigori sti m esi periptwsi.na ypologisete tin asymptwtiki polyplokotita tis lysis sas ws synartisi twn
c o arithmos twn xaraktirwn tou arxeiou
m o arithos twn leksewn sto arxeio
n o arithmos twn diakritwn leksewn sto arxeio
k o arithmos twn leksewn pou ektypwnontai stin eksodo..



auta....

[brian]

sto thema me tis parentheseis, an exo parentheseis kai agiles ftiaxno 2 stoives?mia gia tis parentheseis kai mai gia tis agiles?
episis otan mas zitaei na ilopoiisoume soro, ti soro ilopoioume minimum i maximum?

[theos]

Λοιπόν, μιας και έδινα λογική σήμερα δεν είχα χρόνο ασχοληθώ χθες. Απαντάω τώρα:

Θέμα 5 κανονικής 2007:

Χρησιμοποιώ έναν OrderedSymbolTable. Μου έχουν δώσει μία συνάρτηση getNext() η οποία μου δίνει την επόμενη λέξη (αυτό το διευκρίνησε ο Συμβώνης μέσα στην εξέταση γιατί δεν το λέει στην εκφώνηση). Κάθε φορά που θα καλώ αυτήν την συνάρτηση θα έχω έναν μετρητή που να αυξάνεται κατά 1 έτσι ώστε να μετρήσω πόσες λέξεις είναι συνολικά με την εξής εντολή

x= getNext();
While χ=!(null)
{m=m+1;

Κάθε καινούργια λέξη που θα λαμβάνω με την συνάρτηση getNext() θα πρέπει να ελέγχω αν υπάρχει ήδη μέσα στον πίνακα συμβόλων με την εξής εντολή (έστω ότι έχω δηλώσει τον πίνακα συμβόλων ως table:
newEntry.setValue=x;
y=table.retrieveNext(new Entry) ****

Ο σκοπός αυτών των τριών γρμμών είναι ο εξής: Μέσα στον πίνακα χώνω αντικείμενα που έχουν ένα key και ένα value. Το χ που είχα είναι απλώς μία λέξη και όχι ένα αντικείμενο. Οπότε δημιουργώ ένα αντικείμενο με value το χ και αφού δεν βάζω κλειδί, το κλειδί θα είναι null. Αν λοιπόν αυτό το αντικείμενο υπάρχει εγώ δεν θέλω να το ξαναβάλω μέσα... Θέλω απλώς να μετρήσω τις φορές που υπάρχει αυτή η λέξη. Τη δουλειά του μετρήματος θα την κάνει το κλειδί των αντικειμένων και μιας και είναι και ταξινομημένος πίνακας το αντικείμενο με το μεγαλύτερο κλειδί θα είναι πρώτο πρώτο. Επανέρχομαι στις γραμμές. Για να ελέγξω, λοιπόν ότι το αντικείμενο δεν υπάρχει ήδη μέσα καλώ την retrieveNext. Αν αυτή μου επιστρέψει κάποιο αντικέιμενο και δεν μου επιστρέψει null, τότε σημαίνει ότι υπήρχε μέσα το συγκεκριμένο αντικείμενο. Και άρα απλώς πάω κάνω get key σε αυτό το αντικείμενο και μετά set key αυξημένο κατά ένα. Αλλιώς, άμα μου επιστρέψει null, προσθέτω το καινούργιο αντικείμενο βάζοντας του κλειδί 1 (δηλαδή ότι είναι η 1η φορά που συναντάω την τάδε=value λέξη)Με αυτόν τον τρόπο, τελικά θα έχω n αντικείμενα μέσα στον ταξινομημένο πίνακα συμβόλων , τις n διακριτές λέξεις δηλαδή. Το κλειδί σε κάθε μία από τις διακριτές λέξεις θα είναι ο αριθμός που εμφανίστηκε αυτή η λέξη...

Έπειτα, αρχίζω και εκτυπώνω από το το maximum κλειδί του πίνακα μέχρι το κ ή μέχρι να αδειάσει ο πίνακας αν έχει λιγότερες διακριτές λέξεις από κ

Αυτό είναι όλο... Ξέρω ότι δεν είναι εύκολο, ίσως να μην τα λέω και καλά...

****Εκεί που έχω βάλει τα αστεράκια, υπάρχει ένα λαθάκι αλλά δεν νομίζω να κόψει σε κανέναν από αυτό. Κανονικά θα έπρεπε να κάνει την retrieveNext όσες φορές είναι το μέγιστο κλειδί ώστε να μην βρει διαφορά στα αντικείμενα. Πχ το αντικείμενο με value "o" και key "1" είναι διαφορετικό από το αντικείμενο με ίδιο value και κλειδί "4". Οπότε η λέξη "o" πρέπει να ελέγξω αν υπάρχει για όλα τα πιθανά κλειδιά...

Για ότι δεν κατάλαβες, ρώτα DrCox

@Brian όταν σας ζητάει σωρό θα σας διευκρινήσει εκείνη την ώρα αν θέλει max ή min
Στο θέμα με τις παρενθέσεις ακι τις αγκύλες χρησιμοποιείς μία στοίβα πάλι, απλώς κάνεις push X στην αριστερή παρένθεση και push Y στην αριστερή αγκύλη. Στην δεξιά παρένθεση αναμένεις pop X και στην δεξιά αγκύλη αναμένεις pop Y αλλιώς είναι λάθος η έκφραση...

[DrCox]

theos euxaristoume polu..alli mia erwtisi...sto swro otan tha mas dieukrinizei ekeini tin wra...an thelei megistou ta kleidia tha ta petame sto telos tou pinaka otan 'diagrafontai' en w stin elaxistou stin arxi ...'? i kai stis 2 to idio?

[DrCox]

as mou eksigisei kapoios gt fetos allakse ta themata!!!!gt?
gt na mi balei katholou thewria...?kapoia stigmi tha ta anebasw an mporesei kaneis na ta epeksigisei...(nai theos gia sena milaw ... )

[f_angel]

Το θέμα με τις παρενθέσεις και τις αγκύλες, υπάρχει κάπου στο βιβλίο??

[pao132003]

Δεν υπάρχει στο βιβλίο (γενικά τα θέματα δεν υπάρχουν στο βιβλίο). Λύνεται με στοίβα και η λύση του υπάρχει στη σελίδα 3 του topic από τον theos.