Conversion of infix string to postfix

Conversion of infix string to postfix and evaluation of postfix string to make a simple calculator application in C++.

(A) Algorithm for converting an infix expression into postfix operation

1.Add “(“ at the beginning and “)” at the end of an  infix expression Q. 2. Scan Q from left to      right and repeat step 3 to step 6. 

3 If an operand is encountered, add it into postfix P.
4. If a left parenthesis is encountered, push it onto the stack S
5. If and operator op is encountered then, 

(a) Repeatedly pop from stack S and add
it to postfix each operator which has same precedence as or higher precedence than op.
(b) Add op to Stack S. 6. If a right parenthesis is encountered, then (a) Repeatedly pop from stack S and add
it to postfix each operator until left parenthesis is encountered on stacks.
(c) Remove the left parenthesis.

(B) Algorithm for evaluation of postfix string

1. Scan postfix P from left to right and repeat step 2 and 3 for each elements of P until the NULL character or other symbol is encountered. 
2. . If an operand is encountered then push it on to the stack. 
3. If an operator op is encountered, then (a) Remove the top elements of stack S where A is the top element and B is next top element (b) Evaluate B op A (c) Place the result back onto the stack  S (d) Return top of the stack which is required

result for our calculation

Source code for both infix to postfix and postfix evaluation
/****************************************************************
Program: Conversion of Infix to Postfix String and Evaluation
Language: C/C++

Operators Used

123451. '+' For addition
2. '-' For Subtraction
3. '*' For Multiplication
4. '/' For Division
5. '^' For Exponentiation

Program Limitations

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522* This program Only process single digit operations

* Can't handle unary operation

* Only process left to right associativity

***************************************************/

#include<iostream> 
#include<cmath> 
#include<cstdlib> 

#include<string> 

#define MAX_SIZE 20 

using namespace std; 

template<class T> 

class Stack{ 

private: 

T item[MAX_SIZE]; 

int top; 

public: 

Stack(){ 

top = -1; 

} 

void push(T data){ 

if(!this->is_full()) 

item[++top] = data; 

else{ 

cout<<"Stack Error"<<endl; 

exit(10); 

} 

} 

T pop(){ 

if(!this->is_empty()) 

return item[top--]; 

else{ 

cout<<"Stack is Empty"<<endl; 

exit(11); 

} 

} 

int size(){ 

return top+1; 

} 

bool is_empty(){ 

if(top==-1) 

return true; 

else 

return false; 

} 

bool is_full(){ 

if(top==MAX_SIZE-1) 

return true; 

else 

return false; 

} 

void display(){ 

for(int i=0; i<this->size(); i++){ 

cout<<item[i]<<" "; 

} 

cout<<endl; 

} 

T return_top(){ 

return item[top]; 

} 

}; 

class Convert{ 

private: 

bool num_flag; 

bool two_digit_flag; 

public: 

Convert(); 

string return_with_bracket(string infix); 

void to_Postfix(string infix,char postfix[]); 

bool prcd(char op1, char op2); 

int isOperand(char op); 

int isOperator(char op); 

bool return_flag(){ 

return num_flag; 

} 

}; 

Convert::Convert(){ 

this->num_flag = false; 

this->two_digit_flag = false; 

} 

string Convert::return_with_bracket(string infix){ 

return("(" + infix + ")"); 
} 

bool Convert::prcd(char op1, char op2){ 

if((op1=='+' || op1=='-' || op1=='*' || op1=='/') && op2=='(' ) 

return true; 

if(op1=='+' && op2=='+') 

return true; 

if(op1=='-' && op2=='-') 

return false; 

if(op1=='-' && op2=='+') 

return false; 

if(op1=='+' && op2=='-') 

return false; 

if(op1=='/' && op2=='/') 

return false; 

if(op1=='/' && (op2=='-' || op2=='+')) 

return true; 

if(op1=='*' && (op2=='+' || op2=='-')) 

return true; 

if((op1 == '-' || op1 == '+') && (op2 =='*' || op2 == '/')) 

return false; 

if((op1 == '#39; || op1 == '+') && (op2 =='*' || op2 == '/' || op2=='-')) 

return true; 

if((op1 == '-' || op1 == '+' || op1 =='*' || op1 == '/')&& op2=='^') 

return false; 

if(op1 == '^' && ( op2 == '+' || op2 =='*' || op2 == '/' || op2=='-')) 

return false; 

} 

int Convert::isOperand(char op){ 

return(op>= '0' && op <= '9'); 

} 

int Convert::isOperator(char op){ 

return(op=='+' || op=='-' || op == '/' || op=='*' || op=='^'); 

} 

void Convert::to_Postfix(string infix, char postfix[]){ 

int position, outpos=0; 

char c; 

int count = 0; 

char temp; 

char stacktop ; 

Stack<char> stack; 

for(position = 0; (c = infix[position])!='\0'; position++){ 

if(this->isOperand(c)){ 

postfix[outpos++] = c; 

this->num_flag = true; 

count++; 

if(count>=2){ 

this->two_digit_flag = true; 

} 

}else if(this->isOperator(c)){ 

count = 0; 

if(isOperator(infix[position]) && isOperator(infix[position+1])){ 

cout<<"\aMissing argument in between "<<infix[position]<<" and "<<infix[position+1] 

<<" in column "<< position+1<<endl; 

exit(9); 

} 

if(this->prcd(c, stacktop)){ 

stacktop=stack.return_top(); 

stack.push(c); 

stacktop = c; 

}else{ 

while(true){ 

temp = stack.pop(); 

postfix[outpos++] =temp; 

stacktop = stack.return_top(); 

if(prcd(c, stacktop) || stacktop=='(') 

break; 

} 

stack.push(c); 

stacktop = stack.return_top(); 

} 

} 

else if(c=='('){ 

count = 0; 

stack.push(c); 

stacktop = stack.return_top(); 

}else if(c==')'){ 

count = 0; 

while(1){ 

if(stack.size()==0){ 

cout<<"Warning!! Number of ')' is greater than '('" <<endl; 

exit(2); 

} 

temp = stack.pop(); 

if(temp!='('){ 

postfix[outpos++] = temp; 

}else{ 

break; 

} 

} 

stacktop =stack.return_top(); 

} 

else{ 

cout<<"Invalid input"; 

exit(3); 

} 

if(infix[position]==')' && infix[position+1]=='('){ 

stack.push('*'); 

stacktop = stack.return_top(); 

} 

} 

if(stack.size()!=0){ 

cout<<"Warning!!Number of '(' is greater than ')'"<<endl; 

// exit(6); 

} 

if(!this->return_flag()){ 

cout<<"You must Enter Numeric value for calculation"<<endl; 

cout<<"This program cannot perform operations on variables"; 

exit(5); 

} 

if(this->two_digit_flag){ 

cout<<"Sory! Althoug u may have entered right string"<<endl; 

cout<<"this program is only for single digit operation"<<endl; 

exit(8); 

} 

postfix[outpos] = '\0'; 

} 

class Evaluate{ 

public: 

double eval(char expr[], Convert &); 

double oper(int symb, double op1, double op2); 

}; 

double Evaluate::oper(int symb, double op1, double op2){ 

switch(symb){ 

case '+': return (op1 + op2); 

case '-': return (op1 - op2); 

case '*': return (op1 * op2); 

case '/': return (op1 / op2); 

case '^': return (pow(op1, op2)); 

} 

} 

double Evaluate::eval(char expr[],Convert &convert){ 

int c, position; 

char temp1; 

int count = 0; 

double opnd1, opnd2, value; 

Stack<double> stack; 

for(position = 0; (c = expr[position])!='\0'; position++){ 

if(convert.isOperand(c)){ 

temp1 = double(c-'0'); 

stack.push(temp1); 

}else{ 

opnd2 = stack.pop(); 

if(stack.size()==0){ 

cout<<"This program cannot process unary operation"; 

exit(1); 

} 

opnd1 = stack.pop(); 

value = oper(c, opnd1, opnd2); 

stack.push(value); 

} 

} 

if(stack.size()>=2){ 

cout<<"Sory! this program cannot calculate this"<<endl; 

cout<<"Enter +, *, /, - or ^ between bracket"<<endl; 

exit(4); 

} 

return (stack.pop()); 

} 

int main(){ 

Convert convert; 

Evaluate evaluate; 

string bracketted_infix; 

char infix[50], postfix[50]; 

char choice; 

while(1){ 

cout<<"Enter string: "; 

cin>>infix; 

cout<<endl; 

cout<<"Entered String: "<<infix<<endl; 

bracketted_infix = convert.return_with_bracket(infix); 

convert.to_Postfix(bracketted_infix, postfix); 

cout<<"Equivalent Postfix string: "<<postfix<<endl; 

cout<<"RESULT: "; 

cout<<evaluate.eval(postfix, convert); 

cout<<"\nCalculate another string?(y/n) "; 

cin>>choice; 

cout<<endl; 

if(choice=='n') 

break; 

} 

return 0; 

}