Στοίβες – C# Learning

Τι είναι η Στοίβα;

Φαντάσου μια στοίβα από πιάτα. Όταν θέλεις να βάλεις ένα νέο πιάτο, το βάζεις πάνω από τα υπόλοιπα. Όταν θέλεις να πάρεις ένα πιάτο, παίρνεις το πάνω πιάτο, δηλαδή το τελευταίο που έβαλες. Αυτή η ιδέα λέγεται στοίβα (stack), και δουλεύει με την αρχή Last In, First Out (LIFO), που σημαίνει ο τελευταίος που μπήκε, βγαίνει πρώτος.

Στη C#, μπορούμε να δημιουργήσουμε στοίβες χρησιμοποιώντας την κλάση Stack<T>, όπου το T είναι ο τύπος των στοιχείων που θα έχει η στοίβα, όπως int, string, κλπ.

Παράδειγμα με Πιάτα:

Έχεις μια στοίβα με πιάτα. Αρχικά, η στοίβα είναι άδεια.
Push: Προσθέτεις το πρώτο πιάτο.
Push: Προσθέτεις το δεύτερο πιάτο πάνω από το πρώτο.
Pop: Παίρνεις το δεύτερο πιάτο, που είναι στην κορυφή.
Pop: Παίρνεις το πρώτο πιάτο, που είναι τώρα στην κορυφή.

Αυτή είναι η βασική ιδέα μιας στοίβας. Ας το δούμε τώρα σε κώδικα C#.

Πώς Δημιουργούμε μια Στοίβα στην C#;

Για να δημιουργήσουμε μια στοίβα στην C#, χρησιμοποιούμε την κλάση Stack<T>. Ας δούμε πώς μπορούμε να φτιάξουμε μια στοίβα από ακέραιους αριθμούς (int):

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // Δημιουργία μιας στοίβας για ακέραιους αριθμούς
        Stack<int> stack = new Stack<int>();

        // Προσθήκη στοιχείων στην στοίβα (Push)
        stack.Push(10);
        stack.Push(20);
        stack.Push(30);

        // Εκτύπωση των στοιχείων της στοίβας
        Console.WriteLine("Στοιχεία στη στοίβα:");
        foreach (int number in stack)
        {
            Console.WriteLine(number);
        }

        // Αφαίρεση του στοιχείου από την κορυφή της στοίβας (Pop)
        int topElement = stack.Pop();
        Console.WriteLine("\nΤο στοιχείο που αφαιρέθηκε είναι: " + topElement);

        // Εκτύπωση των στοιχείων μετά το Pop
        Console.WriteLine("Στοιχεία στη στοίβα μετά το Pop:");
        foreach (int number in stack)
        {
            Console.WriteLine(number);
        }
    }
}

Αναλυτική Εξήγηση του Κώδικα:

Δημιουργία Στοίβας:
- Χρησιμοποιούμε τη Stack<int> για να φτιάξουμε μια στοίβα που θα αποθηκεύει ακέραιους αριθμούς (int).
Προσθήκη Στοιχείων με Push:
- Προσθέτουμε τους αριθμούς 10, 20 και 30 στην στοίβα με τη μέθοδο Push().
- Ο αριθμός 30 είναι στην κορυφή, γιατί μπήκε τελευταίος.
Αφαίρεση Στοιχείου με Pop:
- Όταν καλέσουμε τη μέθοδο Pop(), αφαιρεί το στοιχείο που βρίσκεται στην κορυφή, δηλαδή το 30.
- Μετά το Pop, ο αριθμός 20 είναι στην κορυφή της στοίβας.

Άλλες Χρήσιμες Μέθοδοι για τη Στοίβα

Η στοίβα στην C# έχει και άλλες χρήσιμες μεθόδους εκτός από το Push και το Pop. Ας δούμε μερικές:

1. Peek: Βλέπουμε το στοιχείο που είναι στην κορυφή χωρίς να το αφαιρέσουμε.

int topElement = stack.Peek();
Console.WriteLine(“Το στοιχείο στην κορυφή είναι: ” + topElement);

Peek(): Μας επιστρέφει το στοιχείο που βρίσκεται στην κορυφή, αλλά δεν το αφαιρεί.

2. Count: Μας λέει πόσα στοιχεία υπάρχουν στη στοίβα.

int count = stack.Count;
Console.WriteLine(“Η στοίβα έχει ” + count + ” στοιχεία.”);

Count: Επιστρέφει τον αριθμό των στοιχείων που υπάρχουν στη στοίβα.

3. Clear: Διαγράφει όλα τα στοιχεία από τη στοίβα.

stack.Clear(); Console.WriteLine(“Η στοίβα είναι άδεια: ” + (stack.Count == 0));

Clear(): Αδειάζει τη στοίβα, διαγράφοντας όλα τα στοιχεία.

Πού Χρησιμοποιούμε τις Στοίβες;

Οι στοίβες χρησιμοποιούνται σε πολλές εφαρμογές στην πληροφορική, όπως:

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

Παράδειγμα: Αναίρεση Τελευταίας Ενέργειας

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

using System;
using System.Collections.Generic;

class Program
{
static void Main()
{
Stack actions = new Stack();

    // Προσθήκη ενεργειών
    actions.Push("Άνοιγμα αρχείου");
    actions.Push("Επεξεργασία κειμένου");
    actions.Push("Αποθήκευση αρχείου");

    // Εκτύπωση των ενεργειών
    Console.WriteLine("Οι ενέργειες είναι:");
    foreach (string action in actions)
    {
        Console.WriteLine(action);
    }

    // Αναίρεση της τελευταίας ενέργειας
    string lastAction = actions.Pop();
    Console.WriteLine("\nΗ τελευταία ενέργεια '" + lastAction + "' αναίρεθηκε.");

    // Εκτύπωση των υπολοίπων ενεργειών
    Console.WriteLine("\nΟι υπόλοιπες ενέργειες είναι:");
    foreach (string action in actions)
    {
        Console.WriteLine(action);
    }
}

}

Αναλυτική Εξήγηση:

    Δημιουργία Στοίβας Ενεργειών: Χρησιμοποιούμε τη στοίβα για να αποθηκεύσουμε ενέργειες όπως "Άνοιγμα αρχείου", "Επεξεργασία κειμένου", "Αποθήκευση αρχείου".

    Αναίρεση με Pop(): Χρησιμοποιούμε το Pop() για να "αναίρεσουμε" την τελευταία ενέργεια που αποθηκεύτηκε, δηλαδή την "Αποθήκευση αρχείου".



Συμπέρασμα

Η στοίβα είναι μια απλή αλλά ισχυρή δομή δεδομένων που λειτουργεί με την αρχή LIFO (Last In, First Out). Μπορείς να τη χρησιμοποιήσεις σε πολλά σενάρια, όπως αποθήκευση ενεργειών, διαχείριση δεδομένων και μαθηματικούς υπολογισμούς. Οι βασικές μέθοδοι που πρέπει να θυμάσαι είναι:

    Push(): Προσθέτει ένα στοιχείο στην κορυφή της στοίβας.
    Pop(): Αφαιρεί το στοιχείο από την κορυφή της στοίβας.
    Peek(): Βλέπει το στοιχείο στην κορυφή χωρίς να το αφαιρεί.
    Count: Επιστρέφει το πλήθος των στοιχείων.
    Clear(): Διαγράφει όλα τα στοιχεία.

1. Περιορισμοί των Στοίβων

Οι στοίβες λειτουργούν με τη λογική Last In, First Out (LIFO). Αυτό σημαίνει ότι μπορείς να προσθέσεις και να αφαιρέσεις στοιχεία μόνο από την κορυφή. Δεν μπορείς να αφαιρέσεις ή να δεις τα στοιχεία που βρίσκονται κάτω από την κορυφή χωρίς πρώτα να αφαιρέσεις όλα τα στοιχεία πάνω από αυτά. Αυτός είναι ένας περιορισμός, αλλά σε πολλές περιπτώσεις, όπως σε υπολογισμούς ή προγράμματα αναίρεσης (undo), αυτή η λειτουργία είναι πολύ χρήσιμη.

2. Εξαίρεση κατά το `Pop()` ή `Peek()` από άδεια στοίβα

Όταν προσπαθείς να αφαιρέσεις (Pop) ή να δεις (Peek) το στοιχείο στην κορυφή μιας άδειας στοίβας, η C# θα σου πετάξει μια εξαίρεση (exception) τύπου InvalidOperationException.

Παράδειγμα:

Stack stack = new Stack();

// Αν η στοίβα είναι άδεια, αυτό θα προκαλέσει εξαίρεση:
try
{
int element = stack.Pop(); // Αυτό θα προκαλέσει σφάλμα αν η στοίβα είναι άδεια
}
catch (InvalidOperationException ex)
{
Console.WriteLine(“Σφάλμα: Η στοίβα είναι άδεια.”);
}

3. Stack Overflow

Το Stack Overflow είναι μια κατάσταση που μπορεί να προκύψει όταν προσπαθείς να χρησιμοποιήσεις υπερβολικά μεγάλη μνήμη στη στοίβα και ξεπερνάς τα όρια που η μνήμη του συστήματος επιτρέπει για αυτή τη δομή. Αυτό συμβαίνει κυρίως όταν υπάρχει πολύ βαθιά αναδρομή (recursion) σε ένα πρόγραμμα, δηλαδή όταν μια συνάρτηση καλεί τον εαυτό της ξανά και ξανά χωρίς να υπάρχει μια βάση εξόδου από τον βρόχο των κλήσεων.

Στη στοίβα των κλήσεων (call stack), κάθε φορά που καλείται μια μέθοδος, αποθηκεύεται προσωρινά στην μνήμη μέχρι να ολοκληρωθεί. Εάν η μέθοδος δεν ολοκληρώνεται ή καλεί τον εαυτό της ασταμάτητα, τότε η στοίβα μπορεί να “γεμίσει” και να οδηγήσει σε σφάλμα Stack Overflow.

Παράδειγμα Stack Overflow:

Δες ένα παράδειγμα αναδρομής που οδηγεί σε Stack Overflow:

class Program
{
    static void Main()
    {
        CallMyself();  // Ξεκινάει η αναδρομή
    }

    static void CallMyself()
    {
        CallMyself();  // Η μέθοδος καλεί τον εαυτό της ασταμάτητα
    }
}

Σε αυτό το παράδειγμα, η μέθοδος CallMyself() καλεί τον εαυτό της χωρίς όριο. Καθώς οι κλήσεις συνεχίζονται χωρίς να υπάρχει “βάση εξόδου”, η στοίβα κλήσεων γεμίζει και οδηγεί σε Stack Overflow.

Πώς να αποφύγεις το Stack Overflow:

Για να αποφύγεις το Stack Overflow, θα πρέπει να βεβαιώνεσαι ότι κάθε αναδρομική μέθοδος έχει ένα βασικό σενάριο (base case) που τερματίζει την αναδρομή όταν πληρούται μια συγκεκριμένη συνθήκη.

Σωστό παράδειγμα με βάση εξόδου:

class Program
{
static void Main()
{
CallMyself(5); // Ξεκινάει η αναδρομή με όριο
}

static void CallMyself(int counter)
{
    if (counter == 0)
    {
        return;  // Βασικό σενάριο: όταν το counter γίνει 0, σταματά η αναδρομή
    }

    Console.WriteLine(counter);
    CallMyself(counter - 1);  // Αναδρομή, αλλά με μείωση του counter
}

}

Σε αυτό το παράδειγμα, η μέθοδος CallMyself(int counter) καλείται μόνο όσο το counter είναι μεγαλύτερο από το 0. Όταν το counter φτάσει στο 0, η αναδρομή σταματά.

4. Πότε να χρησιμοποιήσεις τη στοίβα

Οι στοίβες είναι εξαιρετικά χρήσιμες όταν έχεις να κάνεις με σενάρια όπου χρειάζεσαι τη δομή Last In, First Out (LIFO). Ορισμένα παραδείγματα όπου μπορείς να χρησιμοποιήσεις στοίβες είναι:

1. Αναίρεση ενεργειών (Undo)

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

2. Αναδρομικοί υπολογισμοί

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

3. Έλεγχος παρενθέσεων σε εκφράσεις

Ένα κλασικό παράδειγμα χρήσης της στοίβας είναι ο έλεγχος αν οι παρενθέσεις σε μια μαθηματική έκφραση είναι σωστά τοποθετημένες. Κάθε φορά που βρίσκουμε μια ανοιχτή παρένθεση, την προσθέτουμε στη στοίβα, και κάθε φορά που βρίσκουμε μια κλειστή παρένθεση, την αφαιρούμε από τη στοίβα.

Παράδειγμα ελέγχου παρενθέσεων:

using System;
using System.Collections.Generic;

class Program
{
static bool AreParenthesesBalanced(string expression)
{
Stack stack = new Stack();

    foreach (char ch in expression)
    {
        if (ch == '(')
        {
            stack.Push(ch);  // Προσθήκη ανοιχτής παρένθεσης στη στοίβα
        }
        else if (ch == ')')
        {
            if (stack.Count == 0)
            {
                return false;  // Βρέθηκε κλειστή παρένθεση χωρίς αντίστοιχη ανοιχτή
            }
            stack.Pop();  // Αφαίρεση της αντίστοιχης ανοιχτής παρένθεσης
        }
    }

    return stack.Count == 0;  // Αν η στοίβα είναι άδεια, οι παρενθέσεις είναι ισορροπημένες
}

static void Main()
{
    string expression = "(1 + (2 * 3) - (4 / 2))";
    bool isBalanced = AreParenthesesBalanced(expression);

    Console.WriteLine("Η έκφραση είναι ισορροπημένη; " + isBalanced);
}

}

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

Συμπέρασμα

Η στοίβα (stack) είναι μια πολύ χρήσιμη δομή δεδομένων που βασίζεται στην αρχή LIFO (Last In, First Out). Είναι ιδανική για σενάρια όπως η αναδρομή, η διαχείριση κλήσεων μεθόδων, η αναίρεση ενεργειών, και πολλά άλλα. Στην C#, μπορούμε να τη χρησιμοποιήσουμε εύκολα με τη κλάση Stack<T>, η οποία προσφέρει πολλές λειτουργίες όπως Push(), Pop(), Peek(), και Count.

Σημαντικά σημεία που πρέπει να θυμάσαι:

Stack Overflow: Προσοχή στην υπερβολική αναδρομή που μπορεί να προκαλέσει σφάλματα στη στοίβα.

Εξαίρεση σε άδεια στοίβα: Αν προσπαθήσεις να κάνεις Pop ή Peek σε άδεια στοίβα, θα πάρεις εξαίρεση.

Η στοίβα χρησιμοποιείται σε πολλά πρακτικά προβλήματα όπως το undo/redo, οι αναδρομές, και η διαχείριση εκφράσεων.

Στην C#, η στοίβα (stack) είναι μια δομή δεδομένων που λειτουργεί με την αρχή LIFO (Last In, First Out), όπου τα στοιχεία που προστίθενται τελευταία είναι τα πρώτα που αφαιρούνται. Η C# παρέχει την κλάση Stack<T> για να δουλέψεις με στοίβες.

Προσθήκη στοιχείου στη στοίβα

Για να προσθέσεις ένα στοιχείο στη στοίβα, χρησιμοποιείς τη μέθοδο Push.

Stack stack = new Stack();
stack.Push(1); // Προσθήκη του στοιχείου 1 στη στοίβα
stack.Push(2); // Προσθήκη του στοιχείου 2 στη στοίβα
stack.Push(3); // Προσθήκη του στοιχείου 3 στη στοίβα

Αντικατάσταση στοιχείου στη στοίβα

Η αντικατάσταση ενός στοιχείου στην κορυφή της στοίβας περιλαμβάνει την αφαίρεση του στοιχείου που βρίσκεται στην κορυφή (μέθοδος Pop) και στη συνέχεια την προσθήκη του νέου στοιχείου με τη μέθοδο Push.

Παράδειγμα αντικατάστασης του στοιχείου στην κορυφή:

Stack stack = new Stack();
stack.Push(1);
stack.Push(2);
stack.Push(3); // Η στοίβα τώρα έχει: 3 (στην κορυφή), 2, 1

// Αφαίρεση του στοιχείου στην κορυφή
int topElement = stack.Pop(); // topElement = 3, η στοίβα τώρα έχει: 2, 1

// Προσθήκη νέου στοιχείου
stack.Push(4); // Η στοίβα τώρα έχει: 4 (στην κορυφή), 2, 1

Εναλλακτική Αντικατάσταση

Αν θέλεις να αντικαταστήσεις το στοιχείο στην κορυφή της στοίβας χωρίς να το χρειαστείς για άλλη χρήση, μπορείς να κάνεις απευθείας αντικατάσταση με την ακόλουθη προσέγγιση:

if (stack.Count > 0)
{
stack.Pop(); // Αφαιρούμε το στοιχείο από την κορυφή
}
stack.Push(4); // Προσθέτουμε το νέο στοιχείο

Σημαντικά Σημεία

Η μέθοδος Push προσθέτει ένα στοιχείο στην κορυφή της στοίβας.
Η μέθοδος Pop αφαιρεί και επιστρέφει το στοιχείο από την κορυφή της στοίβας.
Μπορείς να χρησιμοποιήσεις τη μέθοδο Peek αν θέλεις να δεις το στοιχείο στην κορυφή της στοίβας χωρίς να το αφαιρέσεις.

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

οι στοίβες (stacks) παρέχουν μια σειρά από λειτουργίες που είναι χρήσιμες σε διάφορα σενάρια προγραμματισμού. Εκτός από τις βασικές λειτουργίες Push, Pop και Peek, υπάρχουν μερικές άλλες ενέργειες που μπορείς να κάνεις με τις στοίβες στην C#. Ακολουθούν μερικές από αυτές:

1. Peek

Η μέθοδος Peek σου επιτρέπει να δεις το στοιχείο που βρίσκεται στην κορυφή της στοίβας χωρίς να το αφαιρέσεις.
Χρήση:

Stack stack = new Stack();
stack.Push(1);
stack.Push(2);
stack.Push(3);
int topElement = stack.Peek(); // topElement = 3, η στοίβα παραμένει η ίδια

2. Count

Η ιδιότητα Count επιστρέφει τον αριθμό των στοιχείων που βρίσκονται αυτήν τη στιγμή στη στοίβα.
Χρήση:

Stack stack = new Stack();
stack.Push(1);
stack.Push(2);
stack.Push(3);
int count = stack.Count; // count = 3

3. Contains

Η μέθοδος Contains σου επιτρέπει να ελέγξεις αν ένα συγκεκριμένο στοιχείο υπάρχει στη στοίβα.
Χρήση:

Stack stack = new Stack();
stack.Push(1);
stack.Push(2);
stack.Push(3);
bool containsTwo = stack.Contains(2); // containsTwo = true

4. Clear

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

Stack stack = new Stack();
stack.Push(1);
stack.Push(2);
stack.Clear(); // Η στοίβα είναι πλέον άδεια

5. Enumeration (foreach loop)

Μπορείς να κάνεις enumerate (διατρέξεις) τη στοίβα χρησιμοποιώντας έναν βρόχο foreach. Σημειώνεται ότι η στοίβα διατρέχεται με αντίστροφη σειρά, δηλαδή από το τελευταίο στοιχείο που προστέθηκε μέχρι το πρώτο.
Χρήση:

Stack stack = new Stack();
stack.Push(1);
stack.Push(2);
stack.Push(3);

foreach (int item in stack)
{
Console.WriteLine(item); // Εκτυπώνει: 3, 2, 1
}

6. ToArray

Η μέθοδος ToArray μετατρέπει τη στοίβα σε πίνακα (array), διατηρώντας την αντίστροφη σειρά των στοιχείων.
Χρήση:

Stack stack = new Stack();
stack.Push(1);
stack.Push(2);
stack.Push(3);
int[] array = stack.ToArray(); // array = {3, 2, 1}

7. Copy To

Μπορείς να αντιγράψεις τα στοιχεία της στοίβας σε έναν πίνακα με την CopyTo μέθοδο.
Χρήση:

Stack stack = new Stack();
stack.Push(1);
stack.Push(2);
stack.Push(3);
int[] array = new int[3];
stack.CopyTo(array, 0); // array = {3, 2, 1}

Χρήσεις της στοίβας σε πραγματικά σενάρια:

Περιήγηση στο ιστορικό: Όπως συμβαίνει με τα προγράμματα περιήγησης στο διαδίκτυο, όπου χρησιμοποιείται στοίβα για την περιήγηση στην ιστορικότητα των σελίδων (back/forward).

1. Περιήγηση στο Ιστορικό (Back/Forward)

Αυτό το παράδειγμα προσομοιώνει τη λειτουργία ιστορικού μιας εφαρμογής περιήγησης στο διαδίκτυο, χρησιμοποιώντας δύο στοίβες: μία για το ιστορικό “πίσω” (back) και μία για το ιστορικό “μπροστά” (forward).

using System;
using System.Collections.Generic;

class BrowserHistory
{
    private Stack<string> backStack = new Stack<string>();
    private Stack<string> forwardStack = new Stack<string>();
    private string currentPage;

    public void Visit(string url)
    {
        if (currentPage != null)
        {
            backStack.Push(currentPage);
        }

        currentPage = url;
        forwardStack.Clear(); // Καθαρίζουμε το forward stack, καθώς αλλάζουμε πορεία

        Console.WriteLine("Visited: " + currentPage);
    }

    public void Back()
    {
        if (backStack.Count > 0)
        {
            forwardStack.Push(currentPage);
            currentPage = backStack.Pop();

            Console.WriteLine("Back to: " + currentPage);
        }
        else
        {
            Console.WriteLine("No pages in back history.");
        }
    }

    public void Forward()
    {
        if (forwardStack.Count > 0)
        {
            backStack.Push(currentPage);
            currentPage = forwardStack.Pop();

            Console.WriteLine("Forward to: " + currentPage);
        }
        else
        {
            Console.WriteLine("No pages in forward history.");
        }
    }
}

class Program
{
    static void Main()
    {
        BrowserHistory browser = new BrowserHistory();
        browser.Visit("google.com");
        browser.Visit("stackoverflow.com");
        browser.Visit("github.com");

        browser.Back();    // Επιστρέφει στο "stackoverflow.com"
        browser.Back();    // Επιστρέφει στο "google.com"
        browser.Forward(); // Προχωράει στο "stackoverflow.com"
    }
}

Εκτίμηση εκφράσεων: Σε αλγορίθμους υπολογισμού για εκφράσεις, όπως μετατροπές από infix σε postfix και η αξιολόγηση postfix εκφράσεων.

2. Εκτίμηση Εκφράσεων (Infix to Postfix Conversion και Αξιολόγηση Postfix Εκφράσεων)

Αυτό το παράδειγμα δείχνει πώς να μετατρέψεις μια infix έκφραση (όπως 3 + 4 * 2) σε postfix (όπως 3 4 2 * +) και πώς να αξιολογήσεις την postfix έκφραση.

using System;
using System.Collections.Generic;

class ExpressionEvaluator
{
    // Προτεραιότητα τελεστών
    private static int GetPrecedence(char ch)
    {
        switch (ch)
        {
            case '+':
            case '-':
                return 1;
            case '*':
            case '/':
                return 2;
            case '^':
                return 3;
            default:
                return -1;
        }
    }

    // Μετατροπή infix σε postfix
    public static string InfixToPostfix(string exp)
    {
        Stack<char> stack = new Stack<char>();
        string result = "";

        for (int i = 0; i < exp.Length; i++)
        {
            char c = exp[i];

            // Αν ο χαρακτήρας είναι αριθμός, τον προσθέτουμε στο αποτέλεσμα
            if (char.IsLetterOrDigit(c))
            {
                result += c;
            }
            // Αν ο χαρακτήρας είναι '(', τον βάζουμε στη στοίβα
            else if (c == '(')
            {
                stack.Push(c);
            }
            // Αν ο χαρακτήρας είναι ')', αφαιρούμε όλα από τη στοίβα μέχρι να βρούμε '('
            else if (c == ')')
            {
                while (stack.Count > 0 && stack.Peek() != '(')
                {
                    result += stack.Pop();
                }
                stack.Pop(); // Αφαιρούμε και την '('
            }
            else // Αν ο χαρακτήρας είναι τελεστής
            {
                while (stack.Count > 0 && GetPrecedence(c) <= GetPrecedence(stack.Peek()))
                {
                    result += stack.Pop();
                }
                stack.Push(c);
            }
        }

        // Αδειάζουμε τη στοίβα
        while (stack.Count > 0)
        {
            result += stack.Pop();
        }

        return result;
    }

    // Αξιολόγηση postfix έκφρασης
    public static int EvaluatePostfix(string exp)
    {
        Stack<int> stack = new Stack<int>();

        for (int i = 0; i < exp.Length; i++)
        {
            char c = exp[i];

            // Αν ο χαρακτήρας είναι αριθμός, τον βάζουμε στη στοίβα
            if (char.IsDigit(c))
            {
                stack.Push(c - '0'); // Μετατροπή από char σε int
            }
            else // Αν είναι τελεστής, βγάζουμε δύο αριθμούς από τη στοίβα και εκτελούμε την πράξη
            {
                int val1 = stack.Pop();
                int val2 = stack.Pop();

                switch (c)
                {
                    case '+':
                        stack.Push(val2 + val1);
                        break;
                    case '-':
                        stack.Push(val2 - val1);
                        break;
                    case '*':
                        stack.Push(val2 * val1);
                        break;
                    case '/':
                        stack.Push(val2 / val1);
                        break;
                }
            }
        }

        return stack.Pop(); // Το τελικό αποτέλεσμα βρίσκεται στην κορυφή της στοίβας
    }
}

class Program
{
    static void Main()
    {
        string infix = "3+4*2/(1-5)";
        string postfix = ExpressionEvaluator.InfixToPostfix(infix);
        Console.WriteLine("Postfix: " + postfix);

        int result = ExpressionEvaluator.EvaluatePostfix(postfix);
        Console.WriteLine("Result: " + result);
    }
}

Αναίρεση ενεργειών: Σε επεξεργαστές κειμένου ή γραφικών όπου οι ενέργειες του χρήστη αποθηκεύονται σε στοίβα για να μπορούν να αναιρεθούν.

3. Αναίρεση Ενεργειών (Undo/Redo σε Επεξεργαστή Κειμένου)

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

using System;
using System.Collections.Generic;

class TextEditor
{
private Stack undoStack = new Stack();
private Stack redoStack = new Stack();
private string currentText = “”;

public void Type(string text)
{
    undoStack.Push(currentText); // Αποθήκευση της τρέχουσας κατάστασης για αναίρεση
    currentText += text;
    redoStack.Clear(); // Καθαρίζουμε το redo stack καθώς υπάρχει νέα ενέργεια

    Console.WriteLine("Current Text: " + currentText);
}

public void Undo()
{
    if (undoStack.Count > 0)
    {
        redoStack.Push(currentText); // Αποθήκευση της τρέχουσας κατάστασης για επανάληψη
        currentText = undoStack.Pop();

        Console.WriteLine("Undo: " + currentText);
    }
    else
    {
        Console.WriteLine("Nothing to undo.");
    }
}

public void Redo()
{
    if (redoStack.Count > 0)
    {
        undoStack.Push(currentText); // Αποθήκευση της τρέχουσας κατάστασης για αναίρεση
        currentText = redoStack.Pop();

        Console.WriteLine("Redo: " + currentText);
    }
    else
    {
        Console.WriteLine("Nothing to redo.");
    }
}

}

class Program
{
static void Main()
{
TextEditor editor = new TextEditor();
editor.Type(“Hello”);
editor.Type(” World”);
editor.Undo(); // Ακύρωση προσθήκης ” World”
editor.Redo(); // Επανάληψη προσθήκης ” World”
}
}

ασκησεις στοιβες Download

Τι είναι η Στοίβα;

Παράδειγμα με Πιάτα:

Πώς Δημιουργούμε μια Στοίβα στην C#;

Αναλυτική Εξήγηση του Κώδικα:

Άλλες Χρήσιμες Μέθοδοι για τη Στοίβα

1. Peek: Βλέπουμε το στοιχείο που είναι στην κορυφή χωρίς να το αφαιρέσουμε.

2. Count: Μας λέει πόσα στοιχεία υπάρχουν στη στοίβα.

3. Clear: Διαγράφει όλα τα στοιχεία από τη στοίβα.

Πού Χρησιμοποιούμε τις Στοίβες;

Παράδειγμα: Αναίρεση Τελευταίας Ενέργειας

1. Περιορισμοί των Στοίβων

2. Εξαίρεση κατά το Pop() ή Peek() από άδεια στοίβα

3. Stack Overflow

Παράδειγμα Stack Overflow:

Πώς να αποφύγεις το Stack Overflow:

4. Πότε να χρησιμοποιήσεις τη στοίβα

1. Αναίρεση ενεργειών (Undo)

2. Αναδρομικοί υπολογισμοί

3. Έλεγχος παρενθέσεων σε εκφράσεις

Παράδειγμα ελέγχου παρενθέσεων:

Συμπέρασμα

Προσθήκη στοιχείου στη στοίβα

Αντικατάσταση στοιχείου στη στοίβα

Παράδειγμα αντικατάστασης του στοιχείου στην κορυφή:

Εναλλακτική Αντικατάσταση

Σημαντικά Σημεία

1. Peek

2. Count

3. Contains

4. Clear

5. Enumeration (foreach loop)

6. ToArray

7. Copy To

Χρήσεις της στοίβας σε πραγματικά σενάρια:

1. Περιήγηση στο Ιστορικό (Back/Forward)

2. Εκτίμηση Εκφράσεων (Infix to Postfix Conversion και Αξιολόγηση Postfix Εκφράσεων)

3. Αναίρεση Ενεργειών (Undo/Redo σε Επεξεργαστή Κειμένου)

2. Εξαίρεση κατά το `Pop()` ή `Peek()` από άδεια στοίβα