How to: Transform a Mathematical Expression from Infix Writing to Postfix Writing in C++

1 comment - This post in romanian

Postfix writing (Reverse Polish Form) was made by Polish mathematician Jan Łukasiewicz. Particularities of this form of writing mathematical expressions are presented in [...].
An algorithm for transforming a writing mathematical expressions from infix to postfix writing was developed by Edsger Dijkstra (Dijkstra Shunting Algorithm).

Algorithm requires:

  • Use a stack type structure [...] in which are stored temporarily expression operators;
  • Each operator is assigned to a value of hierarchy in the below table:
( [ { 1
) ] } 2
+ - 3
* / 4

Conversion algorithm is:

  1. It initializes the stack structure and storage structure of postfix writing;
  2. As long as there was no end of mathematical expression in infix form:
    2.1 The next token is read (operand/operator) in infix expression;
    2.2 If the token is operand, it is added in storage structure for postfix writing;
    2.3 If it is the operator (, then it is inserted into the stack;
    2.4 If it is operator ), then transfer operators from stack to postfix structure up to meeting operator ( in stack; operator ( is extracted from stack, without being transferred to the structure of storing the postfix writing;
    2.5 Otherwise (it is no one of the operators (,)):
    a. As long as the operator hierarchy of the stack top is higher than the hierarchy of the current operator, the operator passes from the stack top to the structure of postfix writing;
    b. Current operator is inserted in stack;
  3. It passes all the remaining operators from to writing postfix.

In the application that follows, the storage structure of the mathematical expressions in postfix writing is queue [...].

#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<<"Give the mathematical expression in infix writing ";
	cin>>ExprInfix;
 
	//transformation algorithm infix -> postfix with unsigned /
integer operands 
	int i=0;
 
	//extract 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 error \
at input!";
						vb_op=1;
					}
				}
			}
		}
	}
 
	while(stack){
		stack=pop(stack,&o);
		queue=put(queue,0,o);
	}
 
	//display expression in postfix writing 
	NodCoada* t;
	if(!vb_op){
		t=queue;
		while(t){
			if(t->opd)
				cout<<t->opd<<" ";
			else
				cout<<t->opr<<" ";
			t=t->next;
		}
	}
 
	//deallocate heap memory for queue structure 
	while(queue){
		t=queue;
		queue=queue->next;
		delete t;
	}
 
}

In the application, functions were for push and extracting an operator on the stack (push, pop), adding to queue structure of a token from mathematical expression (put) and determining an operator hierarchy (priority).
Structure of a node in the stack contains the symbol associated with an arithmetic operator and the information about the node successor.
The structure of queue node contains either the integer numerical value of the token, or symbol associated with the character, and the information about the node successor.
The two int and char fields are mutually exclusive by initializing the value zero field not to be considered in the operation of extraction queue or display queue.
Restrictions of the conversion operation implemented in above application aim:

  • All operands are positive integers and not zero;
  • Round brackets are used only for forcing assessment priority of some subexpressions.

Tokens are extracted from the string entered from the keyboard. Operands values are obtained by applying the function conversion standard ASCII-to-int, atoi.
If in the string entered from the keyboard it is identified an operator or symbol that was not spelled out according to priority list, then vb_op boolean variable is set to 1. Mathematical expression in postfix writing is shown only for vb_op = 0.

, , , ,