Η εικοστή πέμπτη επαναληπτική άσκηση για το μάθημα της Πληροφορικής
(πρώην ΑΕΠΠ) αφορά την επίλυση του πολύ γνωστού προβλήματος των ισορροπημένων παρενθέσεων με χρήση στοίβας. Οι λειτουργίες της στοίβας απαιτείται να υλοποιηθούν με χρήση διαδικασιών.
25η Επαναληπτική Άσκηση
Τίτλος: Ισορροπημένες Παρενθέσεις
Κατηγορία: Στοίβα, Διαδικασίες
Ένα από τα διασημότερα προβλήματα, που επιλύονται με χρήση στοίβας, είναι το πρόβλημα των ισορροπημένων παρενθέσεων (balanced parentheses). Έστω λοιπόν ότι έχουμε μία συμβολοσειρά η οποία αποτελείται από αριθμούς, αριθμητικούς τελεστές και από παρενθέσεις ( είτε '(' είτε ')' ), αγκύλες ( είτε '[' είτε ']' ) και άγκιστρα ( είτε '{' είτε '}' ). Η συμβολοσειρά θα ονομάζεται ισορροπημένη αν όλα τα είδη παρενθέσεων που ανοίγουν κλείνουν και δεν κλείνουν είδη παρενθέσεων που δεν έχουν προηγουμένως ανοίξει.
Να γραφεί πρόγραμμα το οποίο:
α) Θα διαβάζει από πόσους χαρακτήρες αποτελείται μία συμβολοσειρά και στη συνέχεια θα διαβάζει χαρακτήρα – χαρακτήρα τους χαρακτήρες της συμβολοσειράς,
β) Θα υλοποιεί διαδικασίες για τις δύο βασικές λειτουργίας μίας στοίβας (Ώθηση και Απώθηση) και
γ) Θα ελέγχει, με χρήση στοίβας, αν η συμβολοσειρά που δόθηκε είναι ισορροπημένη. Αν σε κάποια φάση διαπιστωθεί ότι η συμβολοσειρά είναι μη ισορροπημένη η διαδικασία πρέπει να σταματάει.
Παρατήρηση: Η υλοποίηση της στοίβας να γίνει με έναν μονοδιάστατο πίνακα 50 στοιχείων. Θεωρείστε ότι δεν θα συμβεί ποτέ υπερχείλιση της στοίβας.
Λύση 25ης επαναληπτικής άσκησης
ΠΡΟΓΡΑΜΜΑ Ισορροπημένες_Παρενθέσεις
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: Ι, ΚΟΡΥΦΗ, Ν
ΧΑΡΑΚΤΗΡΕΣ: ΧΑΡ, ΣΤΟΙΒΑ[50], ΣΤΟΙΧΕΙΟ
ΛΟΓΙΚΕΣ: ΙΣΟΡΡΟΠΗΜΕΝΗ
ΑΡΧΗ
ΓΡΑΨΕ 'Πόσους χαρακτήρες έχει η συμβολοσειρά; '
ΔΙΑΒΑΣΕ Ν
ΙΣΟΡΡΟΠΗΜΕΝΗ <- ΑΛΗΘΗΣ
ΚΟΡΥΦΗ <- 0
Ι <- 1
ΟΣΟ Ι <= Ν ΚΑΙ ΙΣΟΡΡΟΠΗΜΕΝΗ ΕΠΑΝΑΛΑΒΕ
ΓΡΑΨΕ 'Δώσε τον ', Ι, 'ο χαρακτήρα: '
ΔΙΑΒΑΣΕ ΧΑΡ
ΑΝ ΚΟΡΥΦΗ = 0 ΤΟΤΕ
ΑΝ ΧΑΡ = '(' Η ΧΑΡ = '[' Η ΧΑΡ = '{' ΤΟΤΕ
ΚΑΛΕΣΕ ΩΘΗΣΗ(ΣΤΟΙΒΑ, ΚΟΡΥΦΗ, ΧΑΡ)
ΑΛΛΙΩΣ_ΑΝ ΧΑΡ = ')' Η ΧΑΡ = ']' Η ΧΑΡ = '}' ΤΟΤΕ
ΙΣΟΡΡΟΠΗΜΕΝΗ <- ΨΕΥΔΗΣ
ΤΕΛΟΣ_ΑΝ
ΑΛΛΙΩΣ
ΑΝ ΧΑΡ = '(' Η ΧΑΡ = '[' Η ΧΑΡ = '{' ΤΟΤΕ
ΚΑΛΕΣΕ ΩΘΗΣΗ(ΣΤΟΙΒΑ, ΚΟΡΥΦΗ, ΧΑΡ)
ΑΛΛΙΩΣ_ΑΝ ΧΑΡ = ')' Η ΧΑΡ = ']' Η ΧΑΡ = '}' ΤΟΤΕ
ΚΑΛΕΣΕ ΑΠΩΘΗΣΗ(ΣΤΟΙΒΑ, ΚΟΡΥΦΗ, ΣΤΟΙΧΕΙΟ)
ΑΝ ΣΤΟΙΧΕΙΟ = '(' ΚΑΙ ΧΑΡ <> ')' ΤΟΤΕ
ΙΣΟΡΡΟΠΗΜΕΝΗ <- ΨΕΥΔΗΣ
ΑΛΛΙΩΣ_ΑΝ ΣΤΟΙΧΕΙΟ = '[' ΚΑΙ ΧΑΡ <> ']' ΤΟΤΕ
ΙΣΟΡΡΟΠΗΜΕΝΗ <- ΨΕΥΔΗΣ
ΑΛΛΙΩΣ_ΑΝ ΣΤΟΙΧΕΙΟ = '{' ΚΑΙ ΧΑΡ <> '}' ΤΟΤΕ
ΙΣΟΡΡΟΠΗΜΕΝΗ <- ΨΕΥΔΗΣ
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΑΝ
Ι <- Ι + 1
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΑΝ ΙΣΟΡΡΟΠΗΜΕΝΗ ΚΑΙ ΚΟΡΥΦΗ = 0 ΤΟΤΕ
ΓΡΑΨΕ 'Η συμβολοσειρά είναι ισορροπημένη.'
ΑΛΛΙΩΣ
ΓΡΑΨΕ 'Η συμβολοσειρά δεν είναι ισορροπημένη.'
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ Ισορροπημένες_Παρενθέσεις
ΔΙΑΔΙΚΑΣΙΑ ΩΘΗΣΗ(ΣΤΟΙΒΑ, ΚΟΡΥΦΗ, ΣΤΟΙΧΕΙΟ)
ΜΕΤΑΒΛΗΤΕΣ
ΧΑΡΑΚΤΗΡΕΣ: ΣΤΟΙΒΑ[50], ΣΤΟΙΧΕΙΟ
ΑΚΕΡΑΙΕΣ: ΚΟΡΥΦΗ
ΑΡΧΗ
ΑΝ ΚΟΡΥΦΗ < 50 ΤΟΤΕ
ΚΟΡΥΦΗ <- ΚΟΡΥΦΗ + 1
ΣΤΟΙΒΑ[ΚΟΡΥΦΗ] <- ΣΤΟΙΧΕΙΟ
ΑΛΛΙΩΣ
ΓΡΑΨΕ 'Υπερχείλιση στοίβας.'
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
ΔΙΑΔΙΚΑΣΙΑ ΑΠΩΘΗΣΗ(ΣΤΟΙΒΑ, ΚΟΡΥΦΗ, ΣΤΟΙΧΕΙΟ)
ΜΕΤΑΒΛΗΤΕΣ
ΧΑΡΑΚΤΗΡΕΣ: ΣΤΟΙΒΑ[50], ΣΤΟΙΧΕΙΟ
ΑΚΕΡΑΙΕΣ: ΚΟΡΥΦΗ
ΑΡΧΗ
ΑΝ ΚΟΡΥΦΗ >= 1 ΤΟΤΕ
ΣΤΟΙΧΕΙΟ <- ΣΤΟΙΒΑ[ΚΟΡΥΦΗ]
ΚΟΡΥΦΗ <- ΚΟΡΥΦΗ - 1
ΑΛΛΙΩΣ
ΓΡΑΨΕ 'Υποχείλιση στοίβας.'
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
Όλες τις επαναληπτικές ασκήσεις για το μάθημα της Πληροφορικής (πρώην ΑΕΠΠ) μπορείτε να τις βρείτε στο παρακάτω άρθρο:
Σχόλια
Δημοσίευση σχολίου