RPN-kalkulatorer (RPN står for Reverse Polish Notation, se http://en.wikipedia.org/wiki/Reverse_Polish_notation) er kalkulatorer der operander (verdier) angis først og så operatorene (operasjoner), istedenfor den vanlige infix-notasjonen. For å regne ut 1 + 2 så angis altså 1 og to og så angis +, som gir resultatet 3. For å bygge videre på resultatet, angir en nye operander og operatorer, f.eks. regnes (1 + 2) * 3 ut ved å angi sekvensen 1 2 + 3 *. Implementasjonen er svært enkelt, en legger bare operandene på en stack ettersom de angis, og operatorene fjerner og bruker disse og legger resutlatet tilbake.
rpncalc1.py
Nedenfor vises en enkel Python-implementasjon, med forklaringer til høyre.
# rpncalc1.py
operands = []
while (True):
print(operands)
token = raw_input(" > ")
try:
operand = float(token)
operands.append(operand)
except ValueError:
if (token == "exit"):
break
elif (token == "+"):
operands.append(operands.pop() + operands.pop())
elif (token == "-"):
operands.append(operands.pop() - operands.pop())
else:
print("Unsupported operator: " + token)
print("program exited")
| #-tegnet angir at resten av linja er en kommentar. Akkurat denne brukes her for å angir hvor det er lurt å legge koden. Tilordningen initialisere operands-variablene til en tom liste med operander. while-løkka (se while-kontrollstrukturen) brukes for å repetere en blokk med kode, inntil en bestemt betingelse er oppfylt. Her er betingelsen True, dvs. alltid sann, så løkke vil aldri stoppe, med mindre den avbrytes innenfra! Legg forøvrig merke til hvordan en i Python bruker innrykk (mellomrom først på linja) for å angi hvilke setninger som hører til blokken. print skriver ut operand-stacken, så brukeren ser hva kalkulator-tilstanden er. raw_input brukes deretter for å lese inn en "noe" fra brukeren, som er er ment å være enten en operand eller en operator. Først prøver vi inni en try-blokk å gjøre om token, altså det brukeren skrev inn, til et desimaltall. Hvis det går så legges tallet til operands-lista med append, altså bakerst, så det fungerer som en stack. Dersom konverteringen til desimaltall ikke går, så utløses et ValueError-unntak, som vi håndteres (fanges opp) med except. Vi sjekker da først om programmet skal avsluttes, og så håndterer vi hver operator i en elif-gren (se if-kontrollstrukturen). Her har vi begrenset oss til pluss (+) og minus (-). For hver av disse operatorene så tas to operander av lista med pop, operasjonen utføres og resultatet legges tilbake med append. Den siste else-grenen sier fra til brukeren at token ikke ble gjenkjent som operator. |
Kjør koden og se at det virker ved å skrive inn ulike operander og operatorer. Vi har plantet (minst) to feil i koden: Den ene har med manglende operander å gjøre, den andre med håndteringen av minus. Prøv å se om du finner en måte å rette dem på, før du leser videre!
Koden over bruker flere variabler for å holde rede på tilstanden til programmet. Den viktigste variablen er operands, som refererer til lista med operander, som utvides og minskes ved gjennomgang av løkka. I tillegg har vi de to variablene token og operand, som holder det brukeren skrev inn som henholdvis (rå)tekst (string) og og konvertert til desimaltall (float). Mens det er viktig at operands-variablen beholder sin verdi for hver runde i løkka, så er det ikke viktig at token og operand gjør det. Tvert imot, så tenker en gjerne at disse er lokale for løkka, selv om Python ikke behandler dem annerledes enn operands i så måte. I andre språk, f.eks. Java, så er det mulig å opprette (deklarere) såkalt blokk-lokale variabler.
La oss se på hvordan variablene hånderes i detalj, når programmet utføres.
| Ved oppstart av programmet tanker vi oss at det opprettes et slags notatark, med samme navn som programmet. Fra starten er arket tomt, som vist til venstre. | |
| Når tilordningen til operands utføres, så noteres navnet og verdien på notatarket. | |
Når raw_input utføres, så blir programmet liggende og vente til brukeren har skrevet inn tekst, og denne teksten tilordnes så til token. Siden token ikke finnes, så utvides notatarket med denne variablen og tilhørende verdi. Her antar vi at brukeren skriver inn 1.0. | |
| token har nå verdien 1.0 (som tekst, altså en string) og denne lar seg konvertere til desimaltall (altså en float-verdi). Dermed blir operand-tilordningen utført for første gang, så operand får verdien 1.0. | |
| På linjen deretter så legges operand til operands-lista. Her leses operands-variablen, men den endres ikke, det er det jo lista som gjør. | |
| For å gjøre poenget med at det er lista som operands refererer til som endres og ikke operands selv, så kan vi tegne tilstanden litt annerledes. | |
Vi antar i andre runde av løkka at brukeren skriver inn 2.0. Siden token og operand allerede finnes, så vil disse få nye verdier. operands refererer fortsatt til samme liste, som igjen er utvidet med en ny operand. | |
Når brukeren i tredje runde i løkka skriver inn +, så utløses ValueError-unntaket før tilordningen av operand rekker å bli utført. Og derfor endres ikke operand, kun token. operands endrer fortsatt ikke verdi, men lista den refererer til endrer seg. Hvis en hadde utført linja operands.append(operands.pop() - operands.pop()) i små steg, så ville en sett at lista faktisk endrer seg tre ganger: Først fra [1.0, 2.0] til [1.0] når pop kalles første gang, så fra [1.0] til [] når pop kalles andre gang og så til [3.0] når svaret legges til med append.
| |
rpncalc2.py
fd