编译原理:正则表达式/词法分析/DFA

发布时间：2020-12-14 02:03:30 所属栏目：百科来源：网络整理

导读：Is It a Number Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 889Accepted Submission(s): 264 Problem Description In some programming languages(like C/C++),we define numbers like this: n

Is It a Number

Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 889Accepted Submission(s): 264

Problem Description

In some programming languages(like C/C++),we define numbers like this:
number -> digits optional_fraction optional_exponent
optional_fraction -> [empty] | .digits
optional_exponent -> [empty] | E digits | E - digits
digits -> digit | digits digit
digit -> [0-9]
Given a string,you have to tell whether it is a legal number.

Input

The first line of input contains an integer T(1<=T<=100) which indicate the number of test cases. Then T test cases follow. Each test case contains one line. Each line contains a string whose length will not exceed 100.
Note: there are no spaces and tabs at the begin and the end of the string.

Output

For each test case,you have to tell whether the string is a legal number. If it is a legal number,output "YES" in a single line,otherwise,output "NO" in a single line.

Sample Input

  
  
   
   5 0123 123.456 0.456E-5 123 456 0.456EF

Sample Output

  
  
   
   YES YES YES NO NO

思路：这道题很类似编译原理的词法分析：自顶向下的分析。具体可以参见《编译原理与实践》的109页和前边的自顶向下分析思路。差不多就是一个直接翻译的过程，实际上计算机是可以用LEX自动

完成这一步骤的，这也是为什么DFA取名有限自动机的原因，是可以自动完成匹配的，人工匹配也比较简单，关系是处理好细节问题。如果是终结符则写成函数，如果是终结

符则直接匹配。一开始用getchar() WA 是两次，估计是末尾符号没有处理好，换成字符数组就AC了。

#include<stdio.h>
#include<stdlib.h>

char buf[3000];

char *token; //全局字符标志

bool match(char expectedToken)//字符匹配，匹配当前字符并且读入下一个字符
{
	if(expectedToken == *token)
	{
		//token = getchar();
		++token;
		return true;
	}
	return false;
}

bool isDigit(char expectedToken)//digit -> [0-9]
{
	return ('0' <= expectedToken && expectedToken <='9');
}

//digits -> digit | digits digit
//消除左递归
//digits -> digit digits'
//digits'-> digit digits'|$  
bool digits()
{
	if(!isDigit(*token))
		return false;
	while(isDigit(*token))
	{
		//token = getchar();
		++token;
	}
	return true;
}
//optional_fraction -> [empty] | .digits
bool optional_fraction()
{
	if(*token != '.')
		return true;
	else
	{
		match('.');
		return digits();
	}
}

//optional_exponent -> [empty] | E digits | E - digits
bool optional_exponent()
{
	if(*token != 'E')
		return true;
	else
	{
		match('E');
		if(*token == '-')
		{
			match('-');
		}
		return digits();
	}
}
//number -> digits optional_fraction optional_exponent
bool number()
{
	return digits() && optional_fraction()
		&& optional_exponent() && (*token == 0);//细节：最后判断是否已到末尾，很重要
}

int main()
{	
	int T;
	scanf("%dn",&T);
	while(T--)
	{
		gets(buf);
		token = buf;
		puts(number() ? "YES" : "NO");
	}
	return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!