warshall.cpp

编译原理中在自下而上分析和优先分析方法中使用的Washall算法

#include <stdio.h>
#define  COL 5
#define  ROW 5

double ComputeStrToDouble(string &strVal, int flag)
{
	int i;
    int count = strVal.size();
	double sum=0.0;
	if(flag==0)
	{
		for(i=0;i<count;i++)
		{
			sum=sum*10.0+strVal[i]-'0';
		}
	}
	if(flag==1)
	{
		for(i=count-1;i>=0;i--)
		{
			sum=(sum+strVal[i]-'0')/10;
		}
	}
	return sum;
}

bool SplitStringToArray(string strValue, queue<double>& dbValueArray)
{
#define  BEGIN 0
#define  SIGN  1
#define  DIGIT 2
#define  COMMA 3
#define  POINT 4
#define  END   5
	
	string tempStr;
	char temp;
	double tempValue;
	int position=0;
	int signFlag,posFlag;
	int oldStatus=BEGIN;
	signFlag=0;
	posFlag=0;
    long cnt = strValue.length();	
    do
	{
		if(cnt == position) return false;
		temp=strValue[position++];
		switch(temp) 
		{
		case '-':
			if(oldStatus==BEGIN||oldStatus==COMMA)
			{
				signFlag=1;
				oldStatus=SIGN;
			}
			else
				return false;
			break;
		case '0':
		case '1':
        case '2':
		case '3':
        case '4':
		case '5':
		case '6':
		case '7':
		case '8':
		case '9':
			if(oldStatus==BEGIN||oldStatus==DIGIT||
				oldStatus==COMMA||oldStatus==POINT||oldStatus==SIGN)
			{
				if(oldStatus==COMMA||oldStatus==POINT||oldStatus==SIGN)
				{
					tempStr.empty();
					tempStr = "";
				}
				tempStr+=temp;
				oldStatus=DIGIT;
			}
			else
				return false;
			break;
		case '.':
			if(oldStatus==DIGIT)
			{
				posFlag=1;
                oldStatus=POINT;
                tempValue=ComputeStrToDouble(tempStr,0);
			}
			else
				return false;
			break;
		case ',':
		case '#':
			if(oldStatus==DIGIT)
			{
				if(posFlag==1)
				{
					tempValue+=ComputeStrToDouble(tempStr,posFlag);
				}
				if(posFlag==0)
				{
					tempValue=ComputeStrToDouble(tempStr,posFlag);
				}
				if(signFlag==1)  
					tempValue=-tempValue;
				dbValueArray.push(tempValue);
				if(temp==',')  oldStatus=COMMA;
				if(temp=='#')  oldStatus=END;
				signFlag=0;
				posFlag=0;
			}
			else
				return false;
			break;
		default:
			return false;
		}
	}while(temp!='#');
	return true;
}

bool GetMatrixBody(double **m, long row, long col, FILE *fh)
{
	char ch;
	long i,j;
	bool bRet;
	ch = fgetc(fh);
	while(ch=='\t'||ch=='\n'||ch==' ')  ch = fgetc(fh);
	if(ch!='{') return false;
	
	string* row_value = new string[row];
    queue<double>* stack_value = new queue<double>[row]; 	
	for(i=0;i<row;i++)  row_value[i] = "";
	
	i = 0;
	
	do 
	{
		ch = fgetc(fh);
		while(ch=='\t'||ch=='\n'||ch==' ')  ch = fgetc(fh);
		if(ch=='}') break;
		do {
			row_value[i]+=ch;
		} while((ch=fgetc(fh))!='#');
		row_value[i]+=ch;
		i++;
	} while(!feof(fh));
    
	if(i!=row) 
	{
		delete[] stack_value;
		delete[] row_value;
		return false;
	}
	
	
	for(i=0;i<row;i++)
    {
		bRet = SplitStringToArray(row_value[i],stack_value[i]);
		if(bRet==false)
		{
			delete[] stack_value;
			delete[] row_value;
			return false;
		}
		if(stack_value[i].size()!=col)
		{
			delete[] stack_value;
			delete[] row_value;
			return false;
		}
    }
	
	for(i=0;i<row;i++)
	{
		for(j=0;j<col;j++)
		{
			m[i][j] = stack_value[i].front();
			stack_value[i].pop();
		}
	}
	
	delete[] stack_value;
	delete[] row_value;
	return true;	
}

void main()
{
	int i,j,k;
	int MR[ROW][COL] ={
				{0,1,1,0,0},
				{1,0,1,0,1},
				{0,1,0,0,1},
				{0,0,0,0,0},
				{1,0,0,1,0}
	};

	for(i = 0;i < COL; i++)
	{
		for(j = 0;j < ROW; j++)
		{
			if (MR[j][i] == 0) continue;
			for(k = 0; k < COL; k++)
			{
                if (MR[i][k] == 0) continue;
                MR[j][k] = 1;
			}
		}
	}

	for(i = 0;i < COL; i++)
	{
		for(j = 0;j < ROW; j++)
		{
			printf("%d",MR[i][j]);
			if (j < ROW - 1) printf(",");
		}
		printf("\n");
	}

	getchar();
}