Scrierea postfixata (forma poloneza inversa) a fost realizata de matematicianul de origine poloneza Jan Lukasiewicz. Particularitati ale acestei forme de scriere a expresiilor matematice sunt prezentate la […].
Un algoritm de transformare a unei expresii matematice din scrierea infixata in scrierea postfixata a fost elaborat de Edsger Dijkstra (Dijkstra Shunting Algorithm).

Algoritmul presupune:

• Utilizarea unei structuri de tip stiva […] in care sunt stocati temporar operatorii expresiei;
• Fiecare operator are atribuita o valoare de ierarhie conform tabelului de mai jos:

( [ {	1
) ] }	2
+ –	3
* /	4

Algoritmul de conversie este:

1. Se initializeaza structura stiva si structura de stocare a scrierii postfixate;
2. Atat timp cat nu s-a ajuns la sfarsitul expresiei matematice in forma infixata:
   1. Se citeste urmatorul token (operand/operator) din expresia infixata;
   2. Daca este tokenul este operand, acesta se adauga in structura de stocare a scrierii postfixate;
   3. Daca este operatorul (, atunci acesta se introduce in stiva;
   4. Daca este operatorul ), atunci se transfera operatori din stiva in structura scriere postfixata pana la intalnirea operatorului ( in stiva; operatorul ( se extrage din stiva, fara a fi transferat in structura scriere postfixata;
   5. altfel, nu este unul din operatorii (, ):
      1. a. atat timp cat ierarhia operatorului din varful stivei este mai mare decat ierarhia operatorului curent, se trece operatorul din varful stivei in structura scriere postfixata;
      2. se introduce operatorul curent in stiva.
3. Se trec toti operatorii ramasi pe stiva in scrierea postfixata.

In aplicatia care urmeaza, structura de stocare expresiei matematice in scriere postfixata este coada […].

#include <iostream>
 
using namespace std;
 
struct NodStiva{
	char opr;
	NodStiva* next;
};
 
struct NodCoada{
	int opd;
	char opr;
	NodCoada* next;
};
 
NodStiva* push(NodStiva* vf,char c){
	NodStiva* nou=new NodStiva;
	nou->opr=c;
	nou->next=vf;
	return nou;
}
 
NodStiva* pop(NodStiva* vf,char *c){
	if(vf){
		*c=vf->opr;
		NodStiva* t=vf;
		vf=vf->next;
		delete t;
		return vf;
	}
	return vf;
}
 
NodCoada* put(NodCoada* c,int v,char o){
	NodCoada* nou=new NodCoada;
	nou->opd=v;
	nou->opr=o;
	nou->next=NULL;
	if(!c)
		return nou;
	else{
		NodCoada* t=c;
		while(t->next)
			t=t->next;
		t->next=nou;
		return c;
	}
}
 
 
int prioritate(char c){
	switch(c){
		case '(':
			return 1;
		case ')':
			return 2;
		case '+':
		case '-':
			return 3;
		case '*':
		case '/':
			return 4;
		default:
			return 5;
	}
}
 
void main(){
	NodStiva* stack=NULL;
	NodCoada* queue=NULL;
	char ExprInfix[100], SubExpr[100], o;
	int vb, vb_op=0;
 
	cout<<"Introduceti expresia matematica in forma infixata: ";
	cin>>ExprInfix;
 
	//algoritmul de transformare infixata -> postfixata cu operanzi \
intregi fara semn
	int i=0;
 
	//extragere token operand/operator
	while(ExprInfix[i]!='\0'){
		int k=0;
		if(ExprInfix[i]>47 && ExprInfix[i]<58){
			while(ExprInfix[i]>47 && ExprInfix[i]<58){
				SubExpr[k]=ExprInfix[i];
				k++;
				i++;
			}
			SubExpr[k]='\0';
			vb=1;
		}
		else{
			SubExpr[k]=ExprInfix[i];
			SubExpr[k+1]='\0';
			i++;
			vb=0;
		}
 
		if(vb){
			o=0;
			queue=put(queue,atoi(SubExpr),o);			
		}
		else{
			if(SubExpr[0]=='('){
				stack=push(stack,SubExpr[0]);
			}
			else{
				if(SubExpr[0]==')'){
					stack=pop(stack,&o);
					while(o!='('){
						queue=put(queue,0,o);
						stack=pop(stack,&o);
					}
				}
				else{
					if(prioritate(SubExpr[0])<5){
						if(stack){
						while(stack && prioritate(stack->opr) > prioritate(SubExpr[0] )){
						stack=pop(stack,&o);
						queue=put(queue,0,o);
						}
						}
 
						stack=push(stack,SubExpr[0]);
					}
					else{
						cout<<"Operator incorect introdus!";
						vb_op=1;
					}
				}
			}
		}
	}
 
	while(stack){
		stack=pop(stack,&o);
		queue=put(queue,0,o);
	}
 
	//afisarea expresiei in scriere postfixata
	NodCoada* t;
	if(!vb_op){
		t=queue;
		while(t){
			if(t->opd)
				cout<<t->opd<<" ";
			else
				cout<<t->opr<<" ";
			t=t->next;
		}
	}
 
	//dezalocare memorie heap alocata pentru structura coada
	while(queue){
		t=queue;
		queue=queue->next;
		delete t;
	}
 
}

In cadrul aplicatiei, au fost construite functii pentru punerea si extragerea unui operator pe si de pe stiva (push, pop), punerea in structura de tip coada a unui token din expresia matematica (put) si determinarea ierarhiei unui operator (prioritate).
Structura unui nod din stiva contine simbolul asociat unui operator aritmetic si informatia de legatura cu nodul succesor.
Structura unui nod din coada contine fie valoarea numerica intreaga a tokenului, fie simbolul asociat caracterului, precum si informatia de legatura cu nodul succesor. Cele doua campuri int si char se exclud reciproc prin initializarea cu valoarea zero a campului care nu trebuie considerat in cadrul operatiei de extragere din coada sau afisare a cozii.
Restrictiile de operatiei de conversie implementata in aplicatia de mai sus vizeaza:

• Toti operanzii sunt intregi pozitivi si nenuli;
• Sunt utilizate doar paranteze rotunde pentru fortarea prioritatii de evaluare a unor subexpresii.

Tokenii sunt extrasi din sirul de caractere introdus de la tastatura. Valorile operanzilor se obtin prin aplicarea functiei standard de conversie ASCII-to-int, respectiv atoi.
Daca in cadrul sirului de caractere introdus de la tastatura se identifica un operator sau simbol care nu se afla in lista precizata in functia prioritate, atunci variabila booleana vb_op este setata pe valoarea 1. Expresia matematica in scriere postfixata este afisata doar pentru vb_op=0.