El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Aplicacions de les Piles

Següent ►
►

Les piles són una estructura de dades fonamental en la programació i tenen una àmplia gamma d'aplicacions en diversos àmbits. En aquesta secció, explorarem algunes de les aplicacions més comunes de les piles, proporcionant exemples pràctics i explicacions detallades.

  1. Avaluació d'Expressions

1.1. Expressions Infix, Prefix i Postfix

Les piles són especialment útils per a l'avaluació d'expressions aritmètiques i lògiques. Hi ha tres formes principals d'expressions:

  • Infix: L'operador es troba entre els operands (per exemple, A + B).
  • Prefix: L'operador precedeix els operands (per exemple, + A B).
  • Postfix: L'operador segueix els operands (per exemple, A B +).

1.2. Avaluació d'Expressions Postfix

Les expressions postfix són més fàcils d'avaluar amb una pila. Considerem l'expressió postfix 5 6 2 + * 12 4 / -.

Pas a pas:

  1. Llegeix el primer element: 5 (operand). Empila 5.
  2. Llegeix el segon element: 6 (operand). Empila 6.
  3. Llegeix el tercer element: 2 (operand). Empila 2.
  4. Llegeix el quart element: + (operador). Desempila 6 i 2, calcula 6 + 2 = 8, i empila 8.
  5. Llegeix el cinquè element: * (operador). Desempila 5 i 8, calcula 5 * 8 = 40, i empila 40.
  6. Llegeix el sisè element: 12 (operand). Empila 12.
  7. Llegeix el setè element: 4 (operand). Empila 4.
  8. Llegeix el vuitè element: / (operador). Desempila 12 i 4, calcula 12 / 4 = 3, i empila 3.
  9. Llegeix el novè element: - (operador). Desempila 40 i 3, calcula 40 - 3 = 37, i empila 37.

El resultat final és 37.

def evaluate_postfix(expression):
    stack = []
    for char in expression.split():
        if char.isdigit():
            stack.append(int(char))
        else:
            b = stack.pop()
            a = stack.pop()
            if char == '+':
                stack.append(a + b)
            elif char == '-':
                stack.append(a - b)
            elif char == '*':
                stack.append(a * b)
            elif char == '/':
                stack.append(a / b)
    return stack.pop()

expression = "5 6 2 + * 12 4 / -"
print(evaluate_postfix(expression))  # Output: 37

  1. Control de la Recursió

Les piles són essencials per implementar la recursió. Quan una funció crida a si mateixa, el sistema operatiu utilitza una pila per mantenir el seguiment de les crides de funció.

2.1. Exemple: Factorial

El càlcul del factorial d'un nombre és un exemple clàssic de recursió.

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

print(factorial(5))  # Output: 120

En aquest exemple, cada crida a factorial es col·loca a la pila fins que n arriba a 0. Després, les crides es resolen en ordre invers.

  1. Reversió de Text

Les piles es poden utilitzar per invertir una cadena de text.

3.1. Exemple: Inversió de Cadena

def reverse_string(s):
    stack = []
    for char in s:
        stack.append(char)
    reversed_s = ''
    while stack:
        reversed_s += stack.pop()
    return reversed_s

print(reverse_string("Hello, World!"))  # Output: !dlroW ,olleH

  1. Historial de Navegació

Els navegadors web utilitzen piles per gestionar l'historial de navegació. Quan visites una pàgina nova, aquesta es col·loca a la pila. Quan prems el botó de retrocedir, la pàgina actual es treu de la pila i es mostra la pàgina anterior.

4.1. Exemple: Historial de Navegació

class BrowserHistory:
    def __init__(self):
        self.history = []
        self.forward_stack = []

    def visit(self, url):
        self.history.append(url)
        self.forward_stack.clear()

    def back(self):
        if len(self.history) > 1:
            self.forward_stack.append(self.history.pop())
            return self.history[-1]
        return None

    def forward(self):
        if self.forward_stack:
            self.history.append(self.forward_stack.pop())
            return self.history[-1]
        return None

# Exemple d'ús
browser = BrowserHistory()
browser.visit("google.com")
browser.visit("stackoverflow.com")
browser.visit("github.com")
print(browser.back())  # Output: stackoverflow.com
print(browser.back())  # Output: google.com
print(browser.forward())  # Output: stackoverflow.com

  1. Validació de Parèntesis

Les piles es poden utilitzar per validar expressions amb parèntesis, claudàtors o claus.

5.1. Exemple: Validació de Parèntesis

def is_valid_parentheses(expression):
    stack = []
    matching_parentheses = {')': '(', ']': '[', '}': '{'}
    for char in expression:
        if char in matching_parentheses.values():
            stack.append(char)
        elif char in matching_parentheses.keys():
            if stack == [] or matching_parentheses[char] != stack.pop():
                return False
    return stack == []

print(is_valid_parentheses("(([]){})"))  # Output: True
print(is_valid_parentheses("(([]){}"))   # Output: False

Conclusió

Les piles són una eina poderosa i versàtil en la programació. Hem vist com es poden utilitzar per avaluar expressions, controlar la recursió, invertir text, gestionar l'historial de navegació i validar parèntesis. Aquests exemples només rasquen la superfície de les aplicacions possibles de les piles. Practicar amb aquests exemples i implementar les teves pròpies aplicacions t'ajudarà a comprendre millor aquesta estructura de dades fonamental.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2024. Tots els drets reservats