Ошибка преобразования скобок из инфикса в постфикс
Я написал код, который преобразует инфиксное выражение в постфиксное выражение. Есть две функции для проверки выражения, одна для проверки выражения без скобок и другая для проверки и преобразования выражения с помощью скобок.
Функция, которая преобразует выражение без скобок, работает полностью нормально, но функция, которая преобразует скобки, выдает ошибку.
Когда я вхожу и выражение вроде (a+b)*(cd), оно правильно конвертирует a + b и затем помещает * в стек. Но почему-то программа не распознает начальную скобку (cd) как скобку и продолжает преобразовывать ее как обычно (для без скобки). Я понятия не имею, почему он не распознает это как скобку, эта маленькая проблема разрушает весь вывод.
Может кто-нибудь сказать мне, почему он не распознает (в (CD), как открывающая скобка? Вот мой код:
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;
}
1 ответ
В checkBracedExpression(), после
while(c!='(');
Вы можете попробовать приведенный ниже код?
i++;
ch=expr[i]; //check next character
continue;
и посмотреть, работает ли это?