Evaluarea unei expresii matematice in scrierea postfixata in C++

1 comment - This post in english

Scrierea postfixata (forma poloneza inversa) [...] este o forma de reprezentare a unei expresii matematice aritmetice in care operatorii sunt scrisi, specificati dupa operanzi.
Avantaje ale scrierii postfixate fata de scrierile prefixata si infixata:

  • Evidentierea clara a ordinii de efectuare a operatiilor;
  • Parantezele pentru fortarea prioritatii de aplicare a operatorilor nu mai sunt necesare;
  • Evaluarile sunt usor de efectuat cu ajutorul calculatorului.


Algoritmul de evaluare e unei expresii in scrierea postfixata este:

  1. Se initializeaza structura de tip stiva;
  2. Atat timp cat nu s-a ajuns la sfarsitul scrierii postfixate, memorata de asemenea intr-o structura de date:
  3. 2.1 Se extrage urmatorul element din scrierea postfixata;
    2.2 Daca elementul extras este valoare, atunci acesta se depune pe structura stiva;
    2.3 Altfel, daca elementul este operator, atunci:

    a. Se extrage elementul din varful stivei, elementul y;
    b. Se extrage elementul din varful stivei, elementul x;
    c. Se efectueaza operatia x operator y;
    d. Se depune rezultatul pe stiva;

  4. Ultima valoarea extrasa de pe stiva reprezinta rezultatul evaluarii expresiei matematice.

In aplicatia de mai jos, se utilizeaza structura de tip stiva [...] pentru stocarea valorilor, operanzilor expresiilor aritmetice precum si o structura de tip coada [...] pentru stocarea expresiei in scriere postfixata.

#include <iostream>
 
using namespace std;
 
struct NodStiva{
	double val;
	NodStiva* next;
};
 
struct NodCoada{
	double val;
	char op;
	NodCoada* next;
};
 
 
NodStiva* push(NodStiva* vf,double v){
	NodStiva* nou=new NodStiva;
	nou->val=v;
	nou->next=vf;
	return nou;
}
 
NodStiva* pop(NodStiva* vf,double *v){
	if(vf){
		*v=vf->val;
		NodStiva* t=vf;
		vf=vf->next;
		delete t;
		return vf;
	}
	return vf;
}
 
NodCoada* put(NodCoada* c,double v,char o){
	NodCoada* nou=new NodCoada;
	nou->val=v;
	nou->op=o;
	nou->next=NULL;
	if(!c)
		return nou;
	else{
		NodCoada* t=c;
		while(t->next)
			t=t->next;
		t->next=nou;
		return c;
	}
}
 
NodCoada* get(NodCoada* c,double *v, char* o){
	if(c){
		*v=c->val;
		*o=c->op;
		NodCoada* t=c;
		c=c->next;
		delete t;
		return c;
	}
	return c;
}
 
 
void main(){
	NodStiva* stack=NULL;
	NodCoada* queue=NULL;
	double opd;
	char opr, opt='d';
 
	//initializarea scrierii postfixate
	while(opt=='d'){
		int i;
		cout<<"Operand/Operator?(1/0)";
		cin>>i;
		if(i==1){
			cout<<"Valoarea operandului:";
			cin>>opd;
			opr=0;
			queue=put(queue,opd,opr);
		}
		else
			if(i==0){
				cout<<"Simbol operator:('+'/'-'/'*'/'/')";
				cin>>opr;
				opd=0;
				queue=put(queue,opd,opr);
			}
			else
				cout<<"Eroare la introducere!";
		cout<<"Continuati?(d/n)";
		cin>>opt;
	}
 
	//algoritmul de evaluare a expresiei
	while(queue){
		queue=get(queue,&opd,&opr);
		if(!opr){
			stack=push(stack,opd);
		}
		else{
			double opd1,opd2, rez;
			stack=pop(stack,&opd2);
			stack=pop(stack,&opd1);
			switch(opr){
				case '+':
					rez=opd1+opd2;
					break;
				case '-':
					rez=opd1-opd2;
					break;
				case '*':
					rez=opd1*opd2;
					break;
				case '/':
					rez=opd1/opd2;
					break;
				default:
					cout<<"Operator eronat introdus!"<<endl;
			}
			stack=push(stack,rez);
		}
	}
 
	stack=pop(stack,&opd);
	cout<<"Rezultatul evaluarii expresiei aritmetice este: "<<opd;
}

In cadrul aplicatiei, au fost construite functii pentru implementarea operatiilor pe structuri de tip stiva (push, pop) si coada (put, get).
Pentru implementarea structurii de tip stiva, este utilizata o lista simpla in care structura elementelor este formata din valoare operand din expresia matematica si adresa elementului succesor in cadrul listei.
Pentru implementarea structurii de tip coada este utilizata o lista simpla in care structura elementelor este formata din valoare operand, simbol aritmetic din expresia matematica si adresa elementului succesor. In cadrul nodului, valoarea operandului si simbolul aritmetic sunt mutual exclusive din punct de vedere logic. Astfel, atunci cand simbolul contine valoarea 0 ASCII, activ logic este campul valoare operand. Daca simbolul contine valorile ASCII asociate ‘+‘, ‘-‘, ‘*‘, ‘/‘ atunci acesta este activ, fiid utilizat mai departe in cadrul algoritmului de evaluare.

, , , ,