Calcolatrice con Priorità Operazioni
Guida Completa: Algoritmo per Implementare una Calcolatrice con Priorità Operazioni
Implementare una calcolatrice che rispetti la priorità delle operazioni (nota anche come ordine delle operazioni o PEMDAS/BODMAS) è un problema classico nell’informatica. Questo articolo esplora gli algoritmi fondamentali, le strutture dati necessarie e le best practice per creare una calcolatrice che gestisca correttamente parentesi, esponenti, moltiplicazioni, divisioni, addizioni e sottrazioni.
1. Comprensione della Priorità delle Operazioni
La priorità delle operazioni segue queste regole standard:
- Parentesi: Le espressioni tra parentesi vengono valutate per prime, dall’interno verso l’esterno
- Esponenti: Potenze e radici vengono calcolate successivamente
- Moltiplicazione e Divisione: Da sinistra a destra
- Addizione e Sottrazione: Da sinistra a destra
| Operatore | Priorità | Associatività | Esempio |
|---|---|---|---|
| () | 1 (massima) | N/A | (2+3)*4 = 20 |
| ^ | 2 | Destra | 2^3^2 = 512 |
| *, / | 3 | Sinistra | 10/2*3 = 15 |
| +, – | 4 | Sinistra | 10-3+2 = 9 |
2. Algoritmi per la Valutazione delle Espressioni
Esistono due approcci principali per implementare una calcolatrice con priorità:
2.1 Algoritmo di Shunting-Yard (Dijkstra)
L’algoritmo di Shunting-Yard, inventato da Edsger Dijkstra, converte un’espressione matematica dalla notazione infissa (standard) alla notazione polacca inversa (RPN), che può essere facilmente valutata con uno stack.
Passaggi:
- Inizializza una pila per gli operatori e una coda per l’output
- Scansiona l’espressione da sinistra a destra
- Se il token è un numero, aggiungilo all’output
- Se il token è un operatore:
- Mentre esiste un operatore in cima alla pila con priorità maggiore o uguale
- Poppa l’operatore dalla pila all’output
- Push l’operatore corrente sulla pila
- Se il token è una parentesi aperta, push sulla pila
- Se il token è una parentesi chiusa:
- Poppa dalla pila all’output fino a trovare la parentesi aperta
- Poppa la parentesi aperta (ma non aggiungerla all’output)
2.2 Valutazione Ricorsiva
Un approccio alternativo utilizza la ricorsione per gestire le parentesi e la priorità:
- Trova la parentesi più interna (o l’intera espressione se non ci sono parentesi)
- Valuta l’espressione più interna ricorsivamente
- Sostituisci il risultato nell’espressione originale
- Ripeti fino a quando tutta l’espressione non è valutata
3. Implementazione Pratica in JavaScript
Ecco come implementare l’algoritmo di Shunting-Yard in JavaScript:
function evaluateExpression(expression) {
const outputQueue = [];
const operatorStack = [];
const precedence = {'^': 4, '*': 3, '/': 3, '+': 2, '-': 2};
// Funzione per gestire gli operatori
const processOperator = (operator) => {
while (operatorStack.length > 0 &&
precedence[operatorStack[operatorStack.length-1]] >= precedence[operator]) {
outputQueue.push(operatorStack.pop());
}
operatorStack.push(operator);
};
// Rimuovi spazi e scansiona i token
let tokens = expression.replace(/\s+/g, '').split(/([+\-*/^()])/).filter(t => t !== '');
for (const token of tokens) {
if (!isNaN(token)) {
outputQueue.push(parseFloat(token));
} else if (token === '(') {
operatorStack.push(token);
} else if (token === ')') {
while (operatorStack[operatorStack.length-1] !== '(') {
outputQueue.push(operatorStack.pop());
}
operatorStack.pop(); // Rimuovi la parentesi aperta
} else {
processOperator(token);
}
}
// Svuota la pila degli operatori
while (operatorStack.length > 0) {
outputQueue.push(operatorStack.pop());
}
// Valuta l'espressione in RPN
const evaluationStack = [];
for (const token of outputQueue) {
if (typeof token === 'number') {
evaluationStack.push(token);
} else {
const b = evaluationStack.pop();
const a = evaluationStack.pop();
switch (token) {
case '+': evaluationStack.push(a + b); break;
case '-': evaluationStack.push(a - b); break;
case '*': evaluationStack.push(a * b); break;
case '/': evaluationStack.push(a / b); break;
case '^': evaluationStack.push(Math.pow(a, b)); break;
}
}
}
return evaluationStack[0];
}
4. Gestione degli Errori
Una calcolatrice robusta deve gestire diversi tipi di errori:
- Parentesi non bilanciate: Contare le parentesi aperte e chiuse
- Divisione per zero: Verificare il divisore prima dell’operazione
- Espressioni non valide: Validare la sintassi dell’espressione
- Overflow numerico: Gestire numeri troppo grandi
| Tipo di Errore | Esempio | Soluzione |
|---|---|---|
| Parentesi non bilanciate | 3 + (2 * 4 | Contare le parentesi e restituire errore |
| Divisione per zero | 10 / (2 – 2) | Verificare divisore prima della divisione |
| Operatore mancante | 5 3 + 2 | Validare la sintassi dell’espressione |
| Numero non valido | 3 + abc | Filtrare solo numeri e operatori validi |
5. Ottimizzazioni e Best Practice
Per creare una calcolatrice performante:
- Pre-compilazione: Convertire l’espressione in RPN una sola volta e riutilizzarla
- Caching: Memorizzare i risultati di espressioni frequenti
- Tokenizzazione avanzata: Gestire numeri decimali, notazione scientifica
- Supporto funzioni: Aggiungere sin, cos, log, etc.
- Interfaccia utente: Mostrare i passaggi intermedi del calcolo
6. Confronto tra Diversi Metodi di Implementazione
Diversi approcci hanno vantaggi e svantaggi:
| Metodo | Vantaggi | Svantaggi | Complessità |
|---|---|---|---|
| Shunting-Yard | Gestisce facilmente priorità e parentesi | Richiede due passaggi (conversione + valutazione) | O(n) |
| Ricorsivo | Codice più leggibile per espressioni semplici | Può causare stack overflow per espressioni molto lunghe | O(n) |
| Valutazione diretta | Un solo passaggio | Codice complesso per gestire priorità | O(n) |
| Parser generato | Molto flessibile, supporta grammatiche complesse | Curva di apprendimento ripida (ANTLR, etc.) | O(n) |
7. Estensioni Avanzate
Per una calcolatrice professionale, considerare:
- Variabili: Supporto per variabili (es: x=5, poi 3*x+2)
- Funzioni personalizzate: Definizione di funzioni utente
- Unità di misura: Conversione automatica (es: 5km + 2m)
- Storia dei calcoli: Memorizzazione e richiamo espressioni precedenti
- Grafici: Visualizzazione di funzioni matematiche
8. Risorse Accademiche e Standard
Per approfondire l’argomento:
- NIST – National Institute of Standards and Technology: Standard per il calcolo numerico
- IEEE – Institute of Electrical and Electronics Engineers: Standard IEEE 754 per l’aritmetica in virgola mobile
- Stanford University – CS Education Library: Algoritmi per la valutazione delle espressioni
9. Esempi Pratici di Implementazione
Ecco alcuni esempi di espressioni e come vengono valutate:
| Espressione | Passaggi di Valutazione | Risultato |
|---|---|---|
| 3 + 4 * 2 |
1. 4 * 2 = 8 2. 3 + 8 = 11 |
11 |
| (3 + 4) * 2 |
1. (3 + 4) = 7 2. 7 * 2 = 14 |
14 |
| 10 / 2 – 3 |
1. 10 / 2 = 5 2. 5 – 3 = 2 |
2 |
| 2 ^ 3 ^ 2 |
1. 3 ^ 2 = 9 2. 2 ^ 9 = 512 |
512 |
10. Test e Validazione
È fondamentale testare la calcolatrice con:
- Casi semplici: 2+3, 5*4
- Priorità operatori: 2+3*4, 10/2*3
- Parentesi: (2+3)*4, 2*(3+4)
- Numeri negativi: -5+3, 4*-2
- Decimali: 3.5+2.1, 10.5/2
- Errori: 10/, 5+, (2+3, 1/0
Una suite di test automatizzati può aiutare a garantire la correttezza dell’implementazione in tutte le situazioni.