2.1-2.3 Στοίβες, Αντίστροφη Πολωνική Γραφή (RPN) και ΑΤΔ Συνόλου

Κάρτες λεξιλογίου για βασικές έννοιες: στοίβα, ενδοθεματική/μεταθεματική/Αντίστροφη Πολωνική Γραφή, αλγόριθμοι μετατροπής και αξιολόγησης, καθώς και βασικές πράξεις και εννοιολογικά στοιχεία του ΑΤΔ Συνόλου.

Ενδοθεματική μορφή (Infix notation)

Μορφή της έκφρασης στην οποία ο τελεστής βρίσκεται ανάμεσα στους τελεστέους και συνήθως χρειάζονται παρενθέσεις για να ορίσουν την προτεραιότητα των πράξεων.

Μεταθεματική μορφή (Postfix notation)

Μορφή στην οποία οι τελεστές έπονται των τελεστέων. Απαλλάζει από παρενθέσεις και χρησιμοποιείται σε αρκετές γλώσσες προγραμματισμού.

Αντίστροφη Πολωνική Γραφή (Reverse Polish Notation, RPN)

Μορφή μεταθεματικής γραφής όπου οι τελεστές έπονται των τελεστών. Χρησιμοποιείται σε μεταγλωττιστές/υπολογιστές και απαιτεί στοίβα για αξιολόγηση.

Δυαδικοί τελεστές (binary operators)

Τελεστές που αφορούν δύο τελεστέους (π.χ. +, -, *, /).

Μοναδιαίοι τελεστές (unary operators)

Τελεστές που αφορούν έναν τελεστή (π.χ. negation).

Τελεστής

Μέρος έκφρασης που δηλώνει πράξη (π.χ. πρόσθεση, αφαίρεση).

Τελεστέος

Μέρος έκφρασης που υφίσταται την ενέργεια του τελεστή (operands, π.χ. αριθμοί, μεταβλητές).

Αλγόριθμος μετατροπής ενδοθεματικής σε RPN

Διαδικασία που μετατρέπει έκφραση από ενδοθεματική σε μεταθεματική (RPN) χρησιμοποιώντας στοίβα για τους τελεστές/τελεστέους.

Αλγόριθμος υπολογισμού RPN

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

Στοίβα (Stack)

Δομή δεδομένων τύπου LIFO (Last In, First Out) όπου τα στοιχεία προστίθενται/αφαιρούνται από την κορυφή.

Top (κορυφή)

Η θέση της κορυφής της στοίβας, όπου γίνεται εισαγωγή/αφαίρεση.

Push

Εισαγωγή ενός νέου στοιχείου στην κορυφή της στοίβας.

Pop

Ανακτηση και αφαίρεση του στοιχείου στην κορυφή της στοίβας.

Άδεια Στοίβα

Κατάσταση στην οποία η στοίβα έχει Top = -1 (ή αντίστοιχη ένδειξη).

Full Stack / Γεμάτη Στοίβα

Κατάσταση όπου η κορυφή βρίσκεται στο ανώτατο επιτρεπόμενο όριο του πίνακα (StackLimit).

ΑΤΔ Σύνολο με Πίνακα

Αντικείμενο/τύπος δεδομένων που ορίζει σύνολο ως μη διατεταγμένη συλλογή μοναδικών στοιχείων και βασικές λειτουργίες (Δημιουργία, Καθολικό, Είσοδος, Διαγραφή, Μέλος, Κενό, Ίσα, Υποσύνολο, Ένωση, Τομή, Διαφορά).

Μέλος (Melos)

Έλεγχος αν ένα στοιχείο ανήκει στο ΑΤΔ συνόλου.

Κενό Σύνολο

Το σύνολο χωρίς στοιχεία.

Καθολικό Σύνολο

Το σύνολο που περιλαμβάνει όλα τα στοιχεία του είδους βάσης υπό μελέτη.

Εισαγωγή στοιχείου (Eisagogi)

Εισαγωγή ενός στοιχείου στο ΑΤΔ συνόλου.

Διαγραφή στοιχείου (Diagrafi)

Αφαίρεση ενός στοιχείου από το ΑΤΔ συνόλου.

Ίσα Σύνολα (IsaSynola)

Έλεγχος αν δύο σύνολα έχουν τα ίδια στοιχεία.

Υποσύνολο (Yposynolo)

Έλεγχος αν ένα σύνολο είναι υποσύνολο ενός άλλου.

Ένωση συνόλων (EnosiSynolou)

Το νέο σύνολο που περιλαμβάνει τα στοιχεία και των δύο συνόλων (τουλάχιστον ένα από τα δύο φθάνει στο true).

Τομή συνόλων (TomiSynolou)

Το νέο σύνολο που περιέχει τα στοιχεία που είναι κοινά στα δύο συνόλα.

Διαφορά συνόλων (DiaforaSynolou)

Το νέο σύνολο με τα στοιχεία που ανήκουν στο πρώτο αλλά όχι στο δεύτερο.

ΑΤΔ Στοίβα με Πίνακα (StackADT)

Αντικείμενο για στοίβα σε C με πίνακα, συμπεριλαμβάνει δήλωση δομών και λειτουργίες CreateStack, EmptyStack, Push, Pop, κ.ά.

API Stack (CreateStack, Push, Pop, EmptyStack)

Συνάρτηση-διασύνδεση που επιτρέπει τη διαχείριση μιας στοίβας (δημιουργία, έλεγχος κενότητας, προσθήκη/αφαίρεση)

Ενδοθεματική vs RPN σχέση

Η ενδοθεματική μορφή απαιτεί παρενθέσεις για προτεραιότητα, ενώ η RPN δεν χρειάζεται παρενθέσεις και χρησιμοποιεί στοίβα για αξιολόγηση.