325 - Identifying Legal Pascal Real Constants

[Archangel]

Does anybody have any idea of tricky input ?? I got so many times wrong answer...><

[arc16]

me too
anyway, is 0e-0 legal or illegal?

[obayashi]

It's just a simple DFA problem but the judge gave me WA.
Please help me.

Code: Select all

#include <iostream>
using namespace std;
char str[1000];
int trans[8][4] = 
{
	{1,2,9,9},
	{9,2,9,9},
	{9,2,3,5},
	{9,4,9,9},
	{9,4,9,5},
	{6,7,9,9},
	{9,7,9,9},
	{9,7,9,9}
};
int getMap (char c) {
	switch (c)
	{
		case '+':
		case '-':
			return 0;
			break;
		case '0':
		case '1':
		case '2':
		case '3':
		case '4':
		case '5':
		case '6':
		case '7':
		case '8':
		case '9':
			return 1;
			break;
		case '.':
			return 2;
			break;
		case 'e':
		case 'E':
			return 3;
			break;
		default:
			return 4;
			break;
	}
}
int check ()
{
	int len = strlen(str);
	int state = 0;
	int i,j;
	char *p = str;
	for (i=len-1;i>=0;i--)
		if (str[i]!=' ')
		{
			str[i+1] = '\0';
			break;
		}
	while (*p==' ') p++;
	cout<<p;
	for (;*p;p++)
	{
		j = getMap(*p);
		state = trans[state][j];
		if (state==9) return 0;
	}
	return (state==2 || state==4 || state==7);
}
int main ()
{
	while (1)
	{
		cin.getline(str,999);
		if (str[0]=='*') break;
		if (check())
		{
			cout<<" is legal."<<endl;
		} else
		{
			cout<<" is illegal."<<endl;
		}
		
	}
	return 0;
}

[Jorge Pinto]

My accepted solution gives this output on these tests:

Input:
1E1
1e1
1E
1EE1
1 E1
.1E1
1E.1
1E1.1
++1E1
1E--1
1.1.1E1
abcd
1
1.1
0e-0
*

Output:
1E1 is legal.
1e1 is legal.
1E is illegal.
1EE1 is illegal.
1 E1 is illegal.
.1E1 is illegal.
1E.1 is illegal.
1E1.1 is illegal.
++1E1 is illegal.
1E--1 is illegal.
1.1.1E1 is illegal.
abcd is illegal.
1 is illegal.
1.1 is legal.
0e-0 is legal.

Hope it helps

Jorge Pinto

[obayashi]

thank u!!!
i found where the problem lies and fixed it.

"1" is not a real constant...

[deddy one]

what is the tricky input in this problem???

[angga888]

Before, I get Accepted on this problem, I got frustated on WA. Since there are so many tricky cases on this problem, you must be very careful.
I think the followings will help you :
1. No any other valid character are allowed (e.g : a,b,c,d,...)
2. Using more than 1 dot before e/E is illegal (e.g: 1.1.1e1 is illegal)
3. 0e-0 is legal
4. An integer value is illegal (e.g: 9999 is illegal)
5. The exponent should be in integer
6. And so on.

[deddy one]

thx angga
I guess I failed on your first rule,

one more thing :
"e" can only appear 1 time right???
just like dot.

[deddy one]

another WA again and again
I almost give up already in this one

could anyone give me a really2 good tricky input
behind this
or maybe send me his exe so I can double check
everything again

I've tried almost every test case I could think of and
the result always WA over and over again

[Dominik Michniewski]

Try this method:

only same states are allowed, also create biggest figure of good constant, it is: x[.(x)+][{E|e}(x)+]
where (x)+ means one or more digit
[x] means optional part of expression
{x|y} means one and exactly one of specified in brackets values

create a graph of all possible states of this expression -> it's quite small (below 20 states) and mark states which are correct as end states. implement finite state machine and run it )))

I did it in this way and got accepted first time - very important are boundary conditions - unexcepted characters in input and so on ...

Best regards
Dominik

[deddy one]

ok, I'll try to code it again


thx Dominik,
but I still
really needed the bad tricky input cases.

[Dominik Michniewski]

I'ii try to send it to you (on this page) tomorrow (If I will be able to find it on my hard disk ). Try all correct / incorrect strings and remember that, you must cut leading and trialing spaces, tabs and so on, but not in the middle of examined string

Good luck
Dominik

[deddy one]

well, ummm
actually in my code I didn't just cut out
the leading or trailing spaces, but
it cuts out all the spaces within the input line

that's the first thing my code do after
reading the input

is it wrong??

[andrew10]

Would you like to show the accepted program for me please?
I really need your help for this program in C Language.

Thanks

[andrew10]

Would you like to show the accepted program for me please?
I really need your help for this program in C Language.

Thanks