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,
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
- 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.
- . If an operand is encountered then push it on to the stack.
- 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
Source code for both infix to postfix and postfix evaluation
/****************************************************************
Program: Conversion of Infix to Postfix String and Evaluation
Language: C/C++
/****************************************************************
Program: Conversion of Infix to Postfix String and Evaluation
Language: C/C++
Operators Used
1. '+' For addition 2. '-' For Subtraction 3. '*' For Multiplication 4. '/' For Division 5. '^' For Exponentiation
Program Limitations
* 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;
}
Post A Comment:
0 comments: