Page 1 of 5

325 - Identifying Legal Pascal Real Constants

Posted: Wed Jul 24, 2002 10:57 pm
by Archangel
Does anybody have any idea of tricky input ?? :cry: I got so many times wrong answer...><

Posted: Sun Aug 18, 2002 1:13 pm
by arc16
me too :(
anyway, is 0e-0 legal or illegal?

325 DFA? WHY WA?

Posted: Tue Sep 17, 2002 8:03 am
by 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;
}

Posted: Thu Oct 10, 2002 6:10 pm
by 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

Posted: Sat Oct 12, 2002 7:43 am
by obayashi
thank u!!!
i found where the problem lies and fixed it.

"1" is not a real constant...

325 legal constant

Posted: Sat Jan 04, 2003 5:11 am
by deddy one
what is the tricky input in this problem???

Posted: Mon Jan 06, 2003 6:55 am
by 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.

Posted: Mon Jan 06, 2003 8:30 am
by 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.

Posted: Mon Jan 06, 2003 9:24 am
by 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 :cry:

Posted: Mon Jan 06, 2003 10:09 am
by 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

Posted: Mon Jan 06, 2003 1:03 pm
by deddy one
ok, I'll try to code it again


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

Posted: Mon Jan 06, 2003 3:01 pm
by 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

Posted: Mon Jan 06, 2003 6:43 pm
by 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??

Posted: Wed Jan 08, 2003 10:42 am
by andrew10
Would you like to show the accepted program for me please?
I really need your help for this program in C Language.

Thanks

Posted: Wed Jan 08, 2003 10:44 am
by andrew10
Would you like to show the accepted program for me please?
I really need your help for this program in C Language.

Thanks