| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
小妹泣血告求!为什么输“(V|V)”会把“(”留在栈里#include<iostream>
#include<string>
using namespace std;
const StackMaxSize=1000;
char w;
struct Stack
{
char stack[StackMaxSize];
int top;
};
void InitStack(Stack &S)
{
S.top=-1;
}
int StackEmpty(Stack& S)
{
return S.top==-1;
}
char Peek(Stack &S)
{
if(S.top==-1)
{
cerr<<"Stack is empty!"<<endl;
exit(1);
}
return S.stack[S.top];
}
void Push(Stack& S,const char& item)
{
if(S.top==StackMaxSize-1)
{
cerr<<"Stack overflow!"<<endl;
exit(1);
}
S.top++;
S.stack[S.top]=item;
}
char Pop(Stack& S)
{
if(S.top==-1)
{
cerr<<"Stack is empty!"<<endl;
exit(1);
}
char temp=S.stack[S.top];
S.top--;
return temp;
}
int Precedence(char op)
{
switch(op)
{
case'!':
return 3;
case'&':
return 2;
case'|':
return 1;
case'(':
return 0;
default:
return -1;
}
}
void Change(char* s1,char* s2)
{
Stack R;
InitStack(R);
int i,j;
i=0;
j=0;
char ch=s1[i];
while(ch!='\0')
{
if(ch==' ')
{
ch=s1[++i];
}
else if(ch=='(')
{
Push(R,ch);
ch=s1[++i];
}
else if(ch==')')
{
while(Peek(R)!='(')
{
s2[j++]=Pop(R);
}
Pop(R);
ch=s1[++i];
}
else if((ch=='|')||(ch=='&')||(ch=='!'))
{
w=Peek(R);
while(Precedence(w)>=Precedence(ch))
{
s2[j++]=w;
Pop(R);w=Peek(R);
}
Push(R,ch);
ch=s1[++i];
}
else
{
s2[j++]=ch;
ch=s1[++i];
}
while(!StackEmpty(R))
{
ch=Pop(R);
if(ch=='(')
{
cerr<<"expression error!"<<endl;
exit(1);
}
else
{
s2[j++]=ch;
}
}
s2[j++]='\0';
}
}
char Compute(char *str)
{
Stack S;
InitStack(S);
int len=strlen(str);
char ch;
char x;
for(int i=0;i<len;i++)
{
ch=str[i];
switch(ch)
{
case'|':
if((Pop(S)=='V')||(Pop(S)=='V'))
x='V';
else
x='F';
break;
case'!':
if(Pop(S)=='V')
x='F';
else
x='V';
break;
case'&':
if((Pop(S)=='V')&&(Pop(S)=='V'))
x='V';
else
x='F';
break;
default:
x=ch;
}
Push(S,x);
}
if(!StackEmpty(S))
{
x=Pop(S);
if(StackEmpty(S))
return x;
else
{
cerr<<"expression error 777!"<<endl;
exit(1);
}
}
else
{
cerr<<"Stack is empty!"<<endl;
exit(1);
}
}
void main()
{
char a[30];
char b[30];
int cas=0;
while(cin.getline(a,sizeof(a)))
{
Change(a,b);
cout<<"Expression "<<++cas<<": "<<Compute(b)<<endl;
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator