c++ - Infix to Postfix conversion brackets error -
i've written code converts infix expression postfix expression. there 2 functions checking expression, 1 checking expression without brackets , other checking , converting expression brackets.
the function converts non-bracket expression works fine 1 converts brackets giving error.
when enter , expression (a+b)*(c-d) , correctly converts a+b , pushed * stack. somehow, program not recognize starting bracket of (c-d) bracket , continues converting normal (for without bracket). have no idea why not recognizing bracket, small problem ruining whole output.
can tell me why not recognize ( in (c-d) opening bracket? here's code:
class stack { . . . void push(char value) //push value onto top of stack { if(isfull()==true) //only possible when stack not full cout<<endl<<"sorry! stack full, no more entries allowed!"<<endl; else //add value top of stack stack not empty { top++; array[top]=value; cout<<endl<<value<<" pushed onto stack!"<<endl; } } char pop() //remove element top { if(isempty()==true) //if stack empty, nothing can popped cout<<endl<<"sorry stack empty! nothing popped!"<<endl; else // otherwise return element @ located @ top { return array[top--]; cout<<endl<<array[top]<<" popped"<<endl; } } bool checkprecedence(char a, char b) // function check precedence of operators { int preca,precb; switch(a) //assigning value precedence operator { 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 precedence operator { 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 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 @ particular time char ch=expr[i]; //taking first character input char c; nostack=top+1; cout<<endl<<strlen(expr)<<endl; //displaying length of expression while(i<strlen(expr)) //keep checking until whole expression not checked { iter++; if((ch=='+' || ch=='-' || ch=='*' || ch=='/' || ch=='^') && (isempty()==true)) // if encounter operator , stack empty { push(ch); //push operator onto stack nostack++; cout<<endl<<retrieve_top(); } if((nostack==1) && (iter==2)) //so single operator in stack not compared , added output { } else if(ch=='+' || ch=='-' || ch=='*' || ch=='/' || ch=='^') //if encounter operator when stack contains operator { cout<<endl<<retrieve_top(); c=pop(); //pop element on top nostack--; if( checkprecedence(c,ch)== true) // , compare precedence of 2 { outputstring[j]=c; //if top of stack has greater precedence, add output j++; cout<<endl<<c<<" added output"; push(ch); //and push other operator onto stack nostack++; if(nostack==2) { c=pop(); nostack--; outputstring[j]=c; j++; } cout<<endl<<retrieve_top()<<endl; } else //otherwise first push operator on stack on top , push other operator on top of { push(c); nostack++; push(ch); nostack++; cout<<endl<<retrieve_top()<<endl; } } else // otherwise, if operand encountered, add output { cout<<endl<<ch<<" added output"; outputstring[j]=ch; j++; } i++; ch=expr[i]; //check next character expression } if( (isempty()==false) && (i==strlen(expr)) ) //if input has ended , stack still contains operators { while(isempty()!=true) //keep popping , adding them output until stack becomes empty { cout<<endl<<retrieve_top()<<endl; c=pop(); nostack--; cout<<endl<<retrieve_top(); cout<<endl<<c<<" added output"; outputstring[j]=c; j++; } } } void checkbracedexpression(char expr[]) //function 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 @ particular time char ch=expr[i]; //taking first character input char c; nostack=top+1; cout<<endl<<strlen(expr)<<endl; while(i<strlen(expr)) { iter++; if (ch=='(') //if encounter bracket { { if (ch=='+' || ch=='-' || ch=='*' || ch=='/' || ch=='^'||ch=='(' ) //and character input operator, push on stack { push(ch); nostack++; } else //otherwise, add output { outputstring[j]=ch; j++; cout<<endl<<ch<<" added output"; } i++; ch=expr[i]; //check next character } while (ch!=')'); //keep checking until reach ) if(ch==')') //when reach ) { //keep popping elements until encounter ( in stack { c=pop(); nostack--; if (c=='(') //if ( encountered, ignore {} else { outputstring[j]=c; //otherwise, add output j++; cout<<endl<<c<<" added output"; } } while(c!='('); } } else // otherwise, continue normal expression checking { if((ch=='+' || ch=='-' || ch=='*' || ch=='/' || ch=='^') && (isempty()==true)) // if encounter operator , stack empty { push(ch); nostack++; } if((nostack==1) && (iter==2)) //so single operator in stack not compared , added output { } else if(ch=='+' || ch=='-' || ch=='*' || ch=='/' || ch=='^') //if encounter operator when stack contains operator { //cout<<endl<<retrieve_top(); c=pop(); nostack--; if( checkprecedence(c,ch)== true) { outputstring[j]=c; j++; cout<<endl<<c<<" added 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 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 output"; outputstring[j]=c; j++; } } } } void displayoutputstring() { cout<<endl<<"output string: "<<outputstring<<endl; } . . . }; int main() { char expression[50]; stack object; int option; object.createstack(); { 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 expression (in infix): "; cin.ignore(); cin>>expression; object.checkexpression(expression); object.displayoutputstring(); break; case 2: cout<<endl<<"enter expression (in infix): "; cin.ignore(); cin>>expression; object.checkbracedexpression(expression); object.displayoutputstring(); break; } } while (option!=3); return 0; }
in checkbracedexpression(), after
while(c!='('); can try below code?
i++; ch=expr[i]; //check next character continue; and see if works?
Comments
Post a Comment