Adott egy aritmetikai kifejezés. A kifejezésben szerepelhetnek matematikai műveleti jelek (operátorok), kerek zárójelek, operandusok (változók, konstansok). Feltesszük, hogy a zárójelezés helyes. A műveleti jelek elvégzésének rangsora (precedenciája) ismert, adott. Az így felírt (infix) kifejezés a felhasználó számára kényelmes, könnyen átlátható, viszont a fordító program számára egy olyan alakra van szükség, melyből a műveletek elvégzésének sorrendje egyértelműen, könnyen adódik. Ezt az alakot nevezzük lengyel formának, vagy postfix formának. A lengyel formára hozott kifejezés tulajdonságai:
|
infix kifejezés |
lengyel forma (postfix alak) |
Megjegyzés |
| a+b | ab+ | műveleti jel az operandusai mögött áll |
| a+b*c | abc*+ | műveletek rangsorának hatása: (prec(*) > prec(+) |
| a*b+c | ab*c+ | műveletek rangsorának hatása: (prec(*) > prec(+) |
| a*(b+c) | abc+* | zárójelezés felülbírálhatja a műveletek rangsorát |
| a/b*c | ab/c* | azonos rangú műveletek általában balról jobbra sorrendben végzendők el |
| a^b^c | abc^^ | a fenti szabály alól akad néhány kivétel, például az egymást követő hatványozás sorrendje jobbról balra értendő |
Az algoritmus működésének bemutatásához (zh/vizsga) a következő ábra javasolt:
