RPN una volta costituito la base di un programmatore di computer in tutto il mondo. Oggi non è così ben conosciuto. Pertanto, illustrazione comica, raffigurante un "reverse" panini con salsicce polacche di fuori, può ancora essere frainteso da alcuni programmatori esperti. Non molto bene spiegare la battuta, ma in questo caso sarà pienamente giustificato.
infisso
Tutti i programmatori, e la maggior parte degli studenti hanno familiarità con l'uso degli operatori. Ad esempio, i valori di espressione x + di somma per le variabili xey usate segno più. Meno noto è il fatto che questo è preso da matematica notazione, chiamato infissa notazione, infatti, è un grosso problema per le macchine. Questo operatore riceve in ingresso due valori vengono rilevati sulla sinistra e destra. Nella programmazione notazione utilizzata opzionalmente con operazioni segni. Ad esempio, x + y può essere scritta come una funzione di piegatura (x, y), in cui il compilatore ed eventualmente converte notazione infissa. Tuttavia, tutti sanno la matematica è troppo bello per non usare espressioni aritmetiche, che formano una sorta di mini-linguaggio interno in quasi ogni linguaggio di programmazione.
formula Traduttore
Il primo linguaggio di programmazione Fortran veramente di successo è diventato così in gran parte perché l'espressione aritmetica (cioè formula ..) E 'convertito (broadcast) nel codice, da qui il nome di essa – formula di traduzione. Prima di questo, dovevano scrivere, ad esempio, piegato a forma di funzioni (e moltiplicare (b, c)). Nel problema COBOL di attuare formula di conversione automatica è stata considerata molto difficile, perché i programmatori dovevano scrivere le cose come Aggiungere A To B mutliply Di C.
Cosa c'è di sbagliato con infisso?
Il problema è che gli operatori hanno proprietà quali priorità e associatività. A causa di questo, la definizione della funzione infisso diventa compito non banale. Ad esempio, moltiplicazione ha precedenza maggiore addizione o sottrazione, il che significa che l'espressione 2 + 3 * 4 non è uguale alla somma di 2 e 3, moltiplicato per 4, come sarebbe nello svolgimento degli operatori da sinistra a destra. Infatti, moltiplicare 3 per 4 e aggiungere 2. Questo esempio illustra che il calcolo dell'espressione infissa richiede spesso un cambiamento nell'ordine di operatori e operandi. Inoltre, è necessario utilizzare le parentesi per cercare la notazione più chiaro. Ad esempio, (2 + 3) * (4 + 5), non si può scrivere senza le parentesi, perché 2 + 3 * 4 + 5 significa che è necessario moltiplicare 3 per 4 e aggiungere 2 e 5.
L'ordine in cui si desidera calcolare gli operatori richiede un lungo ricordo. A causa di questo, gli studenti che iniziano a imparare l'aritmetica, spesso ottengono i risultati sbagliati, anche se le operazioni effettive vengono eseguite correttamente. È necessario insegnare l'ordine delle istruzioni di azione a memoria. In primo luogo, l'azione deve essere eseguita in parentesi, poi moltiplicazione e divisione, e infine addizione e sottrazione. Ma c'è un altro modo di scrivere espressioni matematiche come infissa notazione è solo uno dei possibili "piccole lingue" che possono essere aggiunti a più.
Prefisso e postfix notazione
Due delle alternative più noti è quello di registrare l'operatore prima o dopo la sua operandi. Sono conosciuti come il prefisso e suffisso notazione. Logico Yan Lukasevich ha inventato il primo nel 1920. Ha vissuto in Polonia, in modo che il disco si chiama polacco. Versione Postfix rispettivamente, chiamato Reverse Polish Notation (ARF). L'unica differenza tra questi due metodi è la direzione in cui leggere il record (da sinistra a destra o da destra a sinistra), quindi è sufficiente considerare in dettaglio uno solo di essi. L'operatore OPN è scritto dopo che i suoi operandi. Così, l'espressione AB + rappresenta un esempio RPN per A + B.
numero illimitato di operandi
L'immediato vantaggio notazione è che riassume l'operatore n-adic ed infisso notazione è davvero solo lavora con due operandi, t. E. sono intrinsecamente adatto solo per operazioni binarie. Ad esempio, ABC @ è l'espressione polacca inversa utilizzando indicatore triadica che è il valore massimo di A, B e C. In questo caso l'operatore agisce sulla sinistra dei tre operando stessa e corrisponde ad una funzione chiamata @ (A, B, C). Se si tenta di scrivere il simbolo @ come infisso, come A @ aC o qualcosa del genere, diventa chiaro che semplicemente non funziona.
La priorità in ordine
RPN ha un altro vantaggio che la priorità degli operatori può essere rappresentato dall'ordine del loro aspetto. Allo stesso tempo mai bisogno bretelle, anche se possono essere inclusi come operazioni di caratteri per facilitare la conversione da notazione infissa. Ad esempio, AB + C * – equivalente inequivocabile (A + B) * C, quindi la moltiplicazione non può essere calcolato solo l'aggiunta eseguita, che dà un secondo operando per la moltiplicazione. Cioè, se la calcolato AB + C * da un operatore alla volta, otteniamo AB + C * -> (AB +) * C -> (A + B) * C.
algoritmo di calcolo
L'operatore OPN sembra la stessa di una funzione che prende come argomenti due valori scritti sulla sua sinistra. Inoltre, è una notazione naturale per uso in linguaggi di programmazione, come la modalità di calcolo corrisponde alle operazioni di stack e la necessità di analisi viene eliminato. Ad esempio, lo scaricatore nell'espressione 5 + 6 * 7 apparirà come 5, 6, 7 *, +, e può essere calcolato semplicemente scansione da sinistra a destra e scrivere i valori in una pila. Ogni volta che un segno comune di funzionamento, selezionato dall'elemento superiore 2 della memoria del computer, l'operatore viene utilizzato e il risultato restituito alla memoria. Quando il risultato dell'espressione di calcolo sarà in cima alla pila.
Ad esempio:
- S = () 5, 6, 7, *, + 5 posto sulla pila.
- S = (5) 6, 7, *, + 6 posto sulla pila.
- S = (5, 6), 7 *, 7 + posizionare la pila.
- S = (5, 6, 7), * 2 + scegliere valori dalla pila, uso * e inserire il risultato nella pila.
- S = (5, 6 * 7) = (5, 42) + 2 valori selezionati dalla pila, per applicare + e inserire il risultato nella pila.
- S = (5 + 42) = (47) di calcolo è completato, il risultato viene memorizzato in cima alla pila.
Questo algoritmo può essere controllato RPN più volte, ma ogni volta che funzionerà, non importa quanto sia complessa l'espressione aritmetica.
OPN e pile sono strettamente collegati. Questo esempio dimostra come utilizzare la memoria per calcolare il valore della notazione polacca inversa. Meno ovvio è che si può utilizzare lo stack, conversione espressione infissa standard nella insufficienza renale acuta.
Esempi di linguaggi di programmazione
Pascal RPN realizzato come questo (mostra la parte del programma).
Per leggere i numeri e operatori nel ciclo chiamata procedura, che determina se il numero o segno funzionamento token. Nel primo caso, il valore memorizzato nella pila, e la seconda dell'azione corrispondente due numeri pila superiori viene eseguita e il risultato viene memorizzato.
toktype: = num;
lettura (s);
se c in [ '+', '-', '*', '/'] poi iniziare
se eoln poi cn: = '' altra lettura (CN);
se cn = '' allora
caso di un
'+': Toktype: = aggiungere; '-': toktype: = sub;
'*': Toktype: = mul; '/': Toktype: = div
fine
else begin
se a = '-' allora SGN: = -1 errore altro: = c '+';
con: = cn
fine
fine;
se (non errore) e (toktype = num) poi ControllaNumero;
se toktype num quindi iniziare
y = ostacoli; x: = pop;
se non errore quindi
caso di toktype
aggiungere: z: = x + y; sub: z: = x-y; mul: z: = x * y; div: z: = x / y
fine
push (z);
RPN C-attuazione (parte illustrata del programma):
per (s = strtok (s, w); s; s = strtok (0, w)) {
a = strtod (s, & e);
se (e> s) push (a);
#define rpnop (x) printf ( "% c:", * s), b = pop (), a = pop (), push (x)
else if (* s == '+') rpnop (a + b);
else if (* s == '-') rpnop (a – b);
else if (* s == '*') rpnop (a * b);
else if (* s == '/') rpnop (a / b);
rpnop #undef
}
implementazioni hardware
In quei giorni, quando la tecnologia informatica era molto costoso, si è pensato una buona idea per costringere la gente ad utilizzare scaricatori di sovratensione. Nel 1960-zioni., Come ora, era possibile acquistare le calcolatrici, che funzionano in notazione polacca inversa. Per aggiungere 2 e 3 di loro deve entrare 2, poi 3, e premere il pulsante "più". A prima vista, gli operandi di ingresso per l'operatore sembrava complicato e difficile da ricordare, ma dopo un po 'alcuni sono dipendenti da questo modo di pensare e non riuscivano a capire il motivo per cui gli altri insistono sulla stupida infisso, che è così complicato e così è limitato.
società Burroughs anche costruito un mainframe, che non aveva altra memoria, ad eccezione di stack. L'unica cosa che rende la macchina – applicato l'algoritmi e metodi RPN alla pila centrale. Tutte le operazioni venivano considerati scaricatori operatori, che si applica al n valori superiori. Ad esempio, il team ha preso l'indirizzo di ritorno dalla cima della pila, e così via. D. L'architettura di una tale macchina era semplice, ma non abbastanza veloce per competere con le architetture più comuni. Molti, tuttavia, ancora rimpiangere il fatto che un approccio così semplice ed elegante per il computing, dove ogni programma è stato espressione di OPN, ha trovato la sua continuazione.
Uno calcolatrici time con RPN erano popolari, e alcune persone ancora dare loro preferenza. Inoltre, hanno sviluppato una pila orientati lingue, come Forth. Oggi è poco utilizzato, ma ancora nostalgico dai suoi ex utenti.
Quindi qual è il significato battute circa la salsiccia polacca inversa?
Se assumiamo che l'operatore della salsiccia, la notazione infissa, dovrebbe essere entro il rotolo come hot dog convenzionale. RPN si trova in due metà ottengono essi pronto dopo calcolo. Ora viene la parte difficile – senape. Lei è già sulla salsiccia, t. E. già calcolato come un operatore unario. Si ritiene che la senape dovrebbe anche essere indicato come uncalculated e, pertanto, dovrebbe essere spostato a destra della salsiccia … Ma è possibile, ciò richiederebbe troppo grande pila di …
