Koodit: PHP: Infix/postfix-muunnos ja postfix-suoritus

Koodivinkin tarkoitus on antaa opastusta infixin ja postfixin käsitteisiin, sekä postfix-notaation
mukaisen laskutoimituksen suoritukseen. Tarkoitus _ei_ ole antaa valmista toteutusta kyseisiin operaatioon, huomaa että koodivinkin funktiot toimivat vain pelkästään yksimerkkisillä kokonaisluvuilla, ja vain peruslaskutoimituksilla (yhteen-, vähennys-, kerto ja jakolasku)! Lisäksi vinkissä käytetään PHP:n valmiita taulukkofunktioita pinon yksinkertaiseen käsittelyyn (array_push ja array_pop).

Matematiikassa käytetty infix-notaatio on luonnollinen tapa ihmiselle laskea laskutoimituksia, siinä käytetään sulkeita sekä operaattoreiden arvojärjestystä määrittämään operaatioiden suorittamisjärjestys:
2 * 5 + (2 + 2) * 2
= 18

Postfix (tai käänteinen puolalainen notaatio) on taas koneelle paljon luontevampi tapa suorittaa laskutoimituksia, sillä siinä luvut ja laskutoimitukset voidaan latoa peräkkäin jonoon (yleisimmin pinoon) josta ne voidaan suorittaa yksinkertaisesti siten että lähdetään lukemaan jonoa, ja jos vastaan tulee operaattori (eli +-/*) suoritetaan sen määrittelemä laskutoimitus kahdelle edelliselle luvulle ja korvataan operaattori sekä lasketut luvut laskutoimituksen tuloksella. Ja tätä jatketaan kunnes jäljellä on vain yksi luku, joka on siis vastaus. Notaatiossa ei tarvita laisinkaan sulkuja eikä tarvitse miettiä operaattoreiden arvojärjestystä:
2 5 * 2 2 + 2 * +
= 18

Notaatio käyttää vähän muistia, ja sen suorittaminen on yksinkertaista, joten hyvin monet laskinohjelmistot käyttävät sisäisesti postfix notaatiota, vaikka toki järjestelmän tuleekin yleensä ensin toteuttaa käyttäjän syötteestä infix–postfix-muunnos.

Postfix suomenkielisessä Wikipediassa:
http://fi.wikipedia.org/wiki/Käänteinen_puolalainen_notaatio

Käytetty muunnosalgoritmi

Infix–postfix-muunnoksessa käytetty algoritmi on yksinkertaisettu "Shunting yard algorithm": http://en.wikipedia.org/wiki/Shunting_yard_algorithm (Englanninkielinen Wikipedia).

Algoritmissa käydään infix-merkkijonoa järjestyksessä lävitse ja käsitellään sisältö seuraavasti:

Tapaus 1, operaattori "+-/*":
Jos pino on tyhjä, lisätään se pinoon.
Jos pino ei ole tyhjä, verrataan operaattoria pinon ylinpään operaattoriin,
jos sen arvojärjestys on suurempi tai yhtäsuuri kuin operaattorimme
(* ja / tärkeämpiä kuin + tai -)
otamme operaattorin pinosta pois, ja lisäämme sen vastaukseemme.
Tätä toistetaan pinoon niin kauan että vastaan tulee alempiarvoisempi operaattori,
löydämme vasemman sulkumerkin "(" tai pinosta loppuvat alkiot.
Lopuksi lisäämme operaattorin pinoon.

Tapaus 2, vasen sulkumerkki "(":
Lisätään pinoon

Tapaus 3, oikea sulkumerkki ")":
Otetaan pinosta tavaraa ja lisätään se vastaukseen,
kunnes vastaan tulee vasen sulkumerkki "("

Tapaus 4, operandi eli lukuarvo:
Lisätään vastaukseen

Lopuksi ulostetaan koko pino vastauksen perään.

Postfix-laskualgoritmi

Luetaan postfix vasemmalta oikealle, jos merkki on numero laitetaan se pinoon. Jos merkki taas on operaattori, otetaan kaksi ylintä arvoa pinosta ja suoritetaan kyseinen operaatio näille luvuille ja laitetaan toimituksen tulos pinoon. Tätä jatketaan kunnes koko postfix-merkkijono on käsitelty. Lopulta pinoon jää pelkkä vastaus.

Infix / postfix muunnos

<?php
/**
 * Muuntaa infix-notaation mukaisen laskutoimituksen postfix-notaatioon
 * HUOM! Toimii ainoastaan käytettäessä yhden merkin mittaisia kokonaislukuarvoja!
 * @param string $infix
 * @return string postfix
 */
function infixToPostfix($infix) {
	$pino = Array();
	$operaattorit = Array("*", "/", "+", "-");
	$postfix = "";

	//Merkkijonon alkiot lävitse
	for ($i = 0; $i < strlen($infix); $i++) {

		//Tapaus 1, operaattori
		if (in_array($infix[$i], $operaattorit)) {
			$pinoalkio = $pino[count($pino)-1]; // haetaan pinon päällimmäinen

			while (	!empty($pino)
					&& 	($pinoalkio == "*" || $pinoalkio == "/")
					|| 	(($pinoalkio == "+" || $pinoalkio == "-")
						&& ($infix[$i] == "+" || $infix[$i] == "-"))) {
				//echo "potkitaan pinosta: $pinoalkio ($pinoalkio >= {$infix[$i]})<br />"; //debug
				$pinoalkio = array_pop($pino);
				$postfix .= $pinoalkio;
			}
			array_push($pino, $infix[$i]);
			//echo "laitetaan pinoon: {$infix[$i]}<br />"; //debug
		}

		//Tapaus 2, vasen sulkumerkki
		elseif ($infix[$i] == "(") array_push($pino, $infix[$i]);

		//Tapaus 3, oikea sulkumerkki
		elseif ($infix[$i] == ")") {
			$pinoalkio = array_pop($pino); // haetaan pinon päällimmäinen
			while (!empty($pino) && $pinoalkio != '(') {
				$postfix .= $pinoalkio;
				$pinoalkio = array_pop($pino);
			}
		}
		//Tapaus 4, lukuarvo
		elseif (is_numeric($infix[$i])) $postfix .= $infix[$i];

	}

	//Lisätään pinon sisältö lopputulokseen
	while (!empty($pino)) {
		$postfix .= array_pop($pino);
	}

	return $postfix;
}
?>

Postfix-notaation suoritus

<?php
/**
 * Suorittaa postfix-notaation mukaisen laskutoimituksen
 * HUOM! Toimii ainoastaan käytettäessä yhden merkin mittaisia kokonaislukuarvoja!
 * @param string $postfix
 * @return laskutoimituksen tulos
 */
function evalPostfix($postfix) {
	$operaattorit = Array("*", "/", "+", "-");
	$tulos = 0;
	$pino = Array();

	//Alkiot lävitse
	for ($i = 0; $i < strlen($postfix) ; $i++) {

		//Operaattorit ottavat pinosta kaksi lukua ja suorittavat
		//operaattorin mukaisen laskutoimituksen niille
		//Lopuksi puskevat tuloksen pinoon
		if (in_array($postfix[$i], $operaattorit)) {

			//Operoitavat luvut pinosta
			$luku1 = array_pop($pino);
			$luku2 = array_pop($pino);

			//Itse operaation suoritus
			switch ($postfix[$i]):
			case '+':
				$tulos = $luku2 + $luku1;
				array_push($pino, $tulos);
				break;
			case '-':
				$tulos = $luku2 - $luku1;
				array_push($pino, $tulos);
				break;
			case '*':
				$tulos = $luku2 * $luku1;
				array_push($pino, $tulos);
				break;
			case '/':
				$tulos = $luku2 / $luku1;
				array_push($pino, $tulos);
				break;
			endswitch;

		}

		//Numerot pusketaan suoraan pinoon
		elseif (is_numeric($postfix[$i])) {
			array_push($pino, $postfix[$i]);
		}
	}

	//Lopuksi jäljellä on vain yksi luku, ja se on vastauksemme
	return $pino[0];
}
?>

Käytännön esimerkki

<?php
//Muista sisällyttää ensin funktiota

$infix = "2 * 5 + (2 + 2) * 2";
$postfix = infixToPostfix($infix);

echo "<p>Infix: {$infix} <br />\n Postfix: {$postfix} <br />\n Tulos: ".evalPostfix($postfix);
?>

Koodia saa käyttää vapaasti haluamaansa tarkoitukseen, sikäli kuin suomen tekijänoikeus sen oikeuksista minun sallii luopua. Huomioi myös käytetyn algoritmin mahdolliset tekijänoikeudet sekä patentit koodia käytettäessä, niistä minulla ei ole tarkempaa tietoa!