Xây dựng chương trình chuyển biểu thức từ trung tố sang hậu tố
#include
#include
using namespace std;
struct Node
{
char Data;
Node *Next;
};typedef Node * Stack;
Node *TaoNut(char X)
{
Node *p;p=new Node;
p->Data=X;
return p;
}
void CreateStack(Stack &S)
{
S=NULL;
}
bool isEmpty(Stack S)
{
return (S==NULL);
}
void Push(Stack &S,char X)
{
Node *p;
p=TaoNut(X);
p->Next=S;
S=p;
}
char Top(Stack S)
{
if(S!=NULL)
return S->Data;
}
void Pop(Stack &S)
{
Node *p;
if(S!=NULL)
{
p=S;S=S->Next;
delete(p);
}
}
bool istoantu(char c)
{
return c=='+' || c=='-' || c=='*' ||c=='/'||c=='^';
}
int UT(char x){
if ((x=='*')|| (x=='/') || (x=='%')||(x=='^')) return 2;
if ((x=='+') || (x=='-')) return 1;
}
void in_S(Stack S)
{
Node *p;
for(p=S;p!=NULL;p=p->Next)
cout<Data;
}
void in_P(int t, char P[])
{
for(int k=t;k<>
cout<<>
}
int main()
{
Stack S;S=NULL;
int i=0,j=0;
char t;
CreateStack(S);//((A+(B-C))^D-(E+F))
char str[25]="((a-b)*(a+b))",str1[20]="";;
cout<<"STT\t P\t\t\t\t Q\t\t \t\n";
while (i < strlen(str))
{
if(str[i]=='(')
Push(S,str[i]);
else if(str[i]==')')
while(!isEmpty(S))
{
if(Top(S)!=')'&&
Top(S)!='('){str1[j]+=Top(S);j++;Pop(S);}
else {Pop(S);break;}
}
else if(istoantu(str[i])&&istoantu(Top(S))&& UT(Top(S))>=UT(str[i]))
{while(UT(Top(S))>=UT(str[i])&&!isEmpty(S)&&istoantu(Top(S)))
{
str1[j]+=Top(S);j++;Pop(S);
}
Push(S,str[i]);
}
else if(istoantu(str[i])) Push(S,str[i]);
else {str1[j]+=str[i];j++;}
cout<<>
in_P(i,str);
cout<<"\t\t\t\t"<<>
in_S(S);cout<<"\n";
i++;
Sleep(1000);
}
cout<<"Chuoi trung to"<
cout<<"\nChuoi hau to: "<<>
system("pause");
}