Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

小妹泣血告求!为什么输“(V|V)”会把“(”留在栈里

Posted by 08huozhixin at 2008-07-09 19:07:02 on Problem 2106
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator