(H) Käänteinen puolalainen notaatio¶

Tavoite: Opin käyttämään C++:n taulukkotietotyyppiä.

Ohjeita: Luo uusi projekti: student/08/reverse_polish.

Käänteinen puolalainen notaatio esittää lausekkeen sellaisessa muodossa, että kunkin osalausekkeen operandit kirjoitetaan ennen operaattoria. Esimerkiksi lauseke 2 + 3 kirjoitetaan muodossa 2 3 +. Samalla periaatteella monimutkaisempi lauseke 2 * 3 + 4 kirjoitetaan puolalaisittain 2 3 * 4 +, ja lauseke 2 + 3 * 4 muodossa 2 3 4 * +. Merkintätavalla on se etu, että sulkuja ei tarvita. Esimerkiksi lausekkeen (2 + 3) * 4 puolalainen muoto on 2 3 + 4 *.

Lisäksi lausekkeen evaluointi on helppoa. Apuna voidaan käyttää taulukkoa, jonka voi kuvitella pinoksi siten, että taulukon ensimmäinen alkio on pinon pohja-alkio. Lauseketta voidaan lukea vasemmalta oikealta. Aina kun vuorossa on operandi, se lisätään pinon päällimmäiseksi. Kun taas vuorossa on operaattori, poistetaan pinosta kaksi päällimmäistä alkiota, suoritetaan poistetuille alkioille kyseinen operaatio, ja lisätään operaation tulos pinon päällimmäiseksi.

Esimerkiksi lausekkeen 2 3 + 4 * tapauksessa edellä kuvatut vaiheet näyttävät tältä:

Lausekkeen alapuolella oleva pieni nuoli kertoo lukukohdan.

Kun lauseke saadaan luettua loppuun, pinossa pitäisi olla täsmälleen yksi alkio, joka on koko lausekkeen tulos. Jos näin ei ole, lauseke ei ollut oikean muotoinen.

Toteuta ohjelma, jolle annetaan syötteenä puolalaisen notaation mukainen lauseke ja joka evaluoi sen ja tulostaa lausekkeen tuloksen. Samalla tulee tarkastettua, noudattaako annettu lauseke puolalaista notaatiota.

Jos lauseke noudattaa puolalaista notaatiota, pääohjelman paluuarvo on EXIT_SUCCESS. Muussa tapauksessa pääohjelma palauttaa arvon EXIT_FAILURE.

Esimerkkejä ohjelman toiminnasta:

Input an expression in reverse Polish notation (end with #):
EXPR> 2 3 4 * + #
Correct: 14 is the result

Ohjelma ilmoittaa, jos operandeja tai operaattoreita on liian vähän:

Input an expression in reverse Polish notation (end with #):
EXPR> 2 3 4 * #
Error: Too few operators

Input an expression in reverse Polish notation (end with #):
EXPR> 2 3 4 * + + #
Error: Too few operands

Lausekkeen pitää alkaa numeromerkillä. Jos näin ei ole, ohjelma ilmoittaa siitä:

Input an expression in reverse Polish notation (end with #):
EXPR> + 2 3 #
Error: Expression must start with a number

Ohjelma tuntee aritmeettiset operaattorit: +, -, * ja /. Jos operaattorina on jotakin muuta, ohjelma ilmoittaa siitä:

Input an expression in reverse Polish notation (end with #):
EXPR> 2 3 4 * % #
Error: Unknown character

Ohjelma tunnistaa myös nollalla jaon:

Input an expression in reverse Polish notation (end with #):
EXPR> 2 0 / 3 + #
Error: Division by zero

Vihjeitä:

• Ohjelman saama (laillinen) syöte koostuu sekä numeroista että edellä lueteltujen laskutoimitusten symboleista. Syötteen merkit kannattaa siis lukea char-tyyppisinä, mutta laskutoimitusten suorittamista varten luvut pitää muuttaa kokonaisluvuiksi.
• Riittää, että ohjelma toimii yksinumeroisilla luvuilla. Jos haluat ohjelman toimivan myös suuremmilla luvuilla, voi olla kätevää käyttää istream-luokan putback-funktiota. Kyseinen funktio laittaa viimeksi luetun merkin takaisin syötevirtaan. Voit siis lukea merkin ensin char-tyyppisenä. Jos kyseessä oli numeromerkki, sen voi laittaa takaisin syötevirtaan ja lukea sitten syötteestä int-tyyppinen arvo. Tällöin saat luettua kerralla suuremman kuin yksinumeroisen luvun.
• Huomaa edellä kuvatusta evaluointialgoritmista, että taulukkoon (pinoon) tallennetaan vain lukuja, ei operaattorisymboleita.
• Voit olettaa, että syötteen pituus on enintään 80 merkkiä.