Conversia unei expresii matematice din scrierea infixata in scrierea postfixata in C++

10 comments - This post in english

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:

      2.1 Se citeste urmatorul token (operand/operator) din expresia infixata;
      2.2 Daca este tokenul este operand, acesta se adauga in structura de stocare a scrierii postfixate;
      2.3 Daca este operatorul (, atunci acesta se introduce in stiva;
      2.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;
      2.5 altfel, nu este unul din operatorii (, ):

      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;
      b. 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.

, , , ,


  1. #1 by miru on January 5th, 2010

    Aveam si eu o intrebare.In ce ai compilat programul. Eu l-am rulat in Dev C++ si nu merge,,,ruleaza dar nu rezolva tot :(

    • #2 by marius.popa on January 5th, 2010

      Programul a fost compilat sub Visual Studio 2008. Din testele pe care le-am facut nu au rezultat probleme. Atentie si la restrictiile de introducere a datelor.
      Daca imi dai detalii cu privire la ce nu rezolva programul voi fi in masura sa revin cu detalii.

    • #3 by miru on January 6th, 2010

      Pai cum am spus am rulat programul in Dev c++ si poate si asta este o pb…
      Aveam initial eroarea main must return int asa ca am modificat void main cu int main si am introdus la sf return 0;
      Asa ruleaza programul imi apare Introduceti expresia in forma infixata iar dupa ce introduc si apas enter imi dispare fereastra deci nu genereaza nici un rezultat.

  2. #4 by miru on January 6th, 2010

    Pai cum am spus poate prima pb este ca eu am rulat programul in Dev c++….mi-a dat o eroare ca main must return int…asa ca am modificat void main cu int main si am introdus si la sf return 0…dupa modificarile astea ruleaza programul imi apare Introduceti expresia in forma infixata introduc expresia si cand dau enter se inchide fereastra adik nu genereaza nici un rezultat…:((
    O sa incer sa il rulez in Visual2008 sa vad poate asa merge …si m-ai salva foarte mult:D

  3. #5 by miru on January 6th, 2010

    Pai pb ar fi ca eu l-am rulat in Dev C++…
    Imi da eroarea main must return int asa ca ma modificat void main cu int main si am introdus la sf retrun 0;
    Imi ruleaza progrmul dar nu rezolva…ma lasa sa introduc expresi si apoi se inchide fereastra:((

  4. #6 by miru on January 6th, 2010

    Eroarea ar fi ca at cand ruleaza dupa ce introduc expresia se inchide fereastra deci nu genereaza nici un rezultat :( (

    • #7 by marius.popa on January 7th, 2010

      Recunosc ca nu am lucrat in Dev C++ si nu cunosc modul de operare al acestui mediu. Intuitiv pot spune ca este posibil ca aplicatia sa ruleze, iar la return-ul din functia main fereastra de executie sa se inchida fara a mai apuca vizualizarea rezultatului.
      De exemplu, in Borland C rezolvam aceasta problema fortand oprirea executiei aplicatiei printr-un apel de functie de citire de la tastatura (foloseam functia getch()).
      In Visual Studio 2008, problema se rezolva foarte simplu prin selectarea din meniul Debug a optiunii Start Without Debugging (asta dupa obtinerea executabilului prin compilarea sursei si link-editare obj).

  5. #8 by miru on January 7th, 2010

    Ms oricum am reusit sa ii dau de cap..dar ca sa ruleze corect in Dev c++ tb modificat cate lucruri

  6. #9 by sheche on December 30th, 2010

    pune un _getch() la sfarsitul programului ca sa se blocheze executia intainte de iesirea din main.
    #include

    iar ultima linie din main sa fie
    _getch();

(will not be published)