I've written code that converts an infix expression into a postfix expression. There are two functions for checking the expression, one for checking expression without brackets and the other for checking and converting expression with brackets.
The function which converts non-bracket expression works completely fine but the one which converts with brackets is giving an error.
When i enter and expression like (a+b)*(c-d) , it correctly converts a+b and then pushed * into stack. But somehow, the program does not recognize the starting bracket of (c-d) as a bracket and continues converting it like normal (for without bracket). I have no idea why it is not recognizing it as a bracket, this small problem is ruining the whole output.
Can anyone tell me why it does not recognize ( in (c-d) as an opening bracket? Here's my code:
class Stack
{
.
.
.
void push(char value) //push value onto top of stack
{
if(isFull()==true) //only possible when stack is not full
cout<<endl<<"Sorry! Stack is already full, no more entries allowed!"<<endl;
else //add value to top of stack is stack is not empty
{
top++;
array[top]=value;
cout<<endl<<value<<" pushed onto the stack!"<<endl;
}
}
char pop() //remove an element from the top
{
if(isEmpty()==true) //if stack empty, nothing can be popped
cout<<endl<<"Sorry stack empty! Nothing to be popped!"<<endl;
else // otherwise return element at located at the top
{
return array[top--];
cout<<endl<<array[top]<<" popped"<<endl;
}
}
bool checkPrecedence(char a, char b) // function to check the precedence of operators
{
int precA,precB;
switch(a) //assigning value for precedence to operator A
{
case '+':
precA=1;
break;
case '-':
precA=1;
break;
case '*':
precA=2;
break;
case '/':
precA=2;
break;
case '^':
precA=3;
break;
case '(':
precA=0;
break;
}
switch(b) //assigning value for precedence to operator A
{
case '+':
precB=1;
break;
case '-':
precB=1;
break;
case '*':
precB=2;
break;
case '/':
precB=2;
break;
case '^':
precB=3;
break;
case '(':
precB=0;
break;
}
if (precA<precB) //comparing precedence
return false;
else if (precA>precB)
return true;
else if (precA==precB)
return true;
}
void checkExpression(char expr[]) //function to convert expression without brackets
{
int i=0; //control character number of input
int j=0; //control character number of output
int iter=0; //keep track of iterations
int noStack=0; //to keep track of size of stack at a particular time
char ch=expr[i]; //taking first character from input
char c;
noStack=top+1;
cout<<endl<<strlen(expr)<<endl; //displaying length of expression
while(i<strlen(expr)) //keep checking until the whole expression is not checked
{
iter++;
if((ch=='+' || ch=='-' || ch=='*' || ch=='/' || ch=='^') && (isEmpty()==true)) // if we encounter an operator and stack is empty
{
push(ch); //push operator onto stack
noStack++;
cout<<endl<<retrieve_top();
}
if((noStack==1) && (iter==2)) //so that single operator in stack is not compared with itself and added to output
{
}
else if(ch=='+' || ch=='-' || ch=='*' || ch=='/' || ch=='^') //if we encounter an operator when stack already contains an operator
{
cout<<endl<<retrieve_top();
c=pop(); //pop the element on top
noStack--;
if( checkPrecedence(c,ch)== true) // and then compare the precedence of the 2
{
outputString[j]=c; //if top of stack has greater precedence, add it to output
j++;
cout<<endl<<c<<" added to output";
push(ch); //and push the other operator onto stack
noStack++;
if(noStack==2)
{
c=pop();
noStack--;
outputString[j]=c;
j++;
}
cout<<endl<<retrieve_top()<<endl;
}
else //otherwise first push the operator on stack which was previously on top and then push the other operator on top of it
{
push(c);
noStack++;
push(ch);
noStack++;
cout<<endl<<retrieve_top()<<endl;
}
}
else // otherwise, if operand encountered, add it to output
{
cout<<endl<<ch<<" added to output";
outputString[j]=ch;
j++;
}
i++;
ch=expr[i]; //check next character from expression
}
if( (isEmpty()==false) && (i==strlen(expr)) ) //if input has ended and stack still contains operators
{
while(isEmpty()!=true) //keep popping and adding them to output until stack becomes empty
{
cout<<endl<<retrieve_top()<<endl;
c=pop();
noStack--;
cout<<endl<<retrieve_top();
cout<<endl<<c<<" added to output";
outputString[j]=c;
j++;
}
}
}
void checkBracedExpression(char expr[]) //function to convert expression containing brackets
{
int i=0; //control character number of input
int j=0; //control character number of output
int iter=0; //keep track of iterations
int noStack=0; //to keep track of size of stack at a particular time
char ch=expr[i]; //taking first character from input
char c;
noStack=top+1;
cout<<endl<<strlen(expr)<<endl;
while(i<strlen(expr))
{
iter++;
if (ch=='(') //if we encounter a bracket
{
do
{
if (ch=='+' || ch=='-' || ch=='*' || ch=='/' || ch=='^'||ch=='(' ) //and character input is an operator, push it on the stack
{
push(ch);
noStack++;
}
else //otherwise, add it to output
{
outputString[j]=ch;
j++;
cout<<endl<<ch<<" added to output";
}
i++;
ch=expr[i]; //check next character
}
while (ch!=')'); //keep checking until we reach )
if(ch==')') //when we reach )
{
do //keep popping elements until we encounter ( in the stack
{
c=pop();
noStack--;
if (c=='(') //if ( is encountered, ignore it
{}
else
{
outputString[j]=c; //otherwise, add it to output
j++;
cout<<endl<<c<<" added to output";
}
}
while(c!='(');
}
}
else // otherwise, continue normal expression checking
{
if((ch=='+' || ch=='-' || ch=='*' || ch=='/' || ch=='^') && (isEmpty()==true)) // if we encounter an operator and stack is empty
{
push(ch);
noStack++;
}
if((noStack==1) && (iter==2)) //so that single operator in stack is not compared with itself and added to output
{
}
else if(ch=='+' || ch=='-' || ch=='*' || ch=='/' || ch=='^') //if we encounter an operator when stack already contains an operator
{
//cout<<endl<<retrieve_top();
c=pop();
noStack--;
if( checkPrecedence(c,ch)== true)
{
outputString[j]=c;
j++;
cout<<endl<<c<<" added to output";
push(ch);
noStack++;
if(noStack==2)
{
c=pop();
noStack--;
outputString[j]=c;
j++;
}
}
else
{
push(c);
noStack++;
push(ch);
noStack++;
}
}
else
{
cout<<endl<<ch<<" added to output";
outputString[j]=ch;
j++;
}
i++;
ch=expr[i];
}
i++;
ch=expr[i];
if( (isEmpty()==false) && (i==strlen(expr)) )
{
while(isEmpty()!=true)
{
c=pop();
noStack--;
cout<<endl<<c<<" added to output";
outputString[j]=c;
j++;
}
}
}
}
void displayOutputString()
{
cout<<endl<<"Output String: "<<outputString<<endl;
}
.
.
.
};
int main()
{
char expression[50];
Stack object;
int option;
object.createStack();
do
{
cout<<endl<<"1.Convert simple expression."<<endl<<"2.Convert bracket expression."<<endl<<"3.Exit"<<endl<<"Your option: ";
cin>>option;
cout<<endl;
switch(option)
{
case 1:
cout<<endl<<"Enter the expression (in infix): ";
cin.ignore();
cin>>expression;
object.checkExpression(expression);
object.displayOutputString();
break;
case 2:
cout<<endl<<"Enter the expression (in infix): ";
cin.ignore();
cin>>expression;
object.checkBracedExpression(expression);
object.displayOutputString();
break;
}
}
while (option!=3);
return 0;
}