How to: Evaluate a Mathematical Expression in Postfix Writing in C++

1 comment - This post in romanian

Postfix writing [...] is a form of representation of mathematical expressions in which arithmetic operatorsare written specified by operands.
Advantages of postfix writing over prefix and infix writing:

  • Highlights clear policy of making operations;
  • Brackets for forcing priority for implementing operators are not necessary;
  • Evaluations are easily performed by computer.


Algorithm for evaluation of an expression in postfix writing is:

  1. It initializes the stack structure type;
  2. As long as there was no end of postfix writing, also stored in a data structure:
    2.1 Extract the following item in postfix writing;
    2.2 If the item is a worth statement, then it is deposited on the stack structure;
    2.3 Otherwise, if the element is a operator, then:

    a. Extract from the top stack element, the element y;
    b. Extract from the top stack element, the element x;
    c. It performs the operation x operator y;
    d. Shall submit the result to stack;

  3. Last value extracted from the stack is the result of evaluating the mathematical expression.

In the application below, stack structure type [...] is used for storing values, operands of arithmetic expressions and a queue type structure [...] to store the expression in postfix writing.

#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';
 
	//initializing postfix writing 
	while(opt=='d'){
		int i;
		cout<<"Operand/Operator?(1/0)";
		cin>>i;
		if(i==1){
			cout<<"Operand value:";
			cin>>opd;
			opr=0;
			queue=put(queue,opd,opr);
		}
		else
			if(i==0){
				cout<<"Operator symbol:('+'/'-'/'*'/'/')";
				cin>>opr;
				opd=0;
				queue=put(queue,opd,opr);
			}
			else
				cout<<"Input error!";
		cout<<"Proceed?(d/n)";
		cin>>opt;
	}
 
	//algorithm to evaluate expression
	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<<"Error for input operator!"<<endl;
			}
			stack=push(stack,rez);
		}
	}
 
	stack=pop(stack,&opd);
	cout<<"Result for arithmetic evaluation: "<<opd;
}

In above application, functions were built to implement operations of the stack structure type (push, pop) and queue (put, get).
To implement stack structure type, a simply linked list structure is used and it consists of elements operand value of math expression and address of the successor element in the list.
To implement the queue structure type, a simply linked list structure is used and it consists of elements operand value, an arithmetic symbol and the address of the successor element. In the node, the operand value and arithmetic symbol are mutually exclusive. Thus, when the symbol contains ASCII value 0, the field operand value is active. If the symbol contains ASCII values associated with ‘+’, ‘-’, ‘*’, ‘/’ then it is active being used further in the evaluation algorithm.

, , , ,