String to double conversion - Part 2

[Evyn]

Hi all,

I have recently asked for advice:

http://groups.google.com/group/comp.lang.c++/browse_thread/thread/1b42e6855a2c571b/e63d8f10b51f015c?lnk=raot#e63d8f10b51f015c

My task is to convert a string of characters to a double. The string
is read from a file and will be in the format 12345. The double output
must be 0.12345.

My answer to this problem was:

double convert(string s)
{
return atof((string(". ") + s).c_str());
}

The prof. was happy, but he told me to write my own atof. So I have
converted the string to an array of char. Is this the right strategy?
If so, how to I actually convert the array to a double? (As you no
doubt can see, I am pretty much in the dark here).

double stof(string s)
{
// c_str - Returns a pointer to a null-terminated array of
characters representing the string's contents.

const char* p = s.c_str();
int len = strlen(p); // get length
char sArr[len];
memcpy(sArr, s.c_str(), len); // copy to char array

double tmp;
for(int i = 0;i<len;i++)
{
cout << endl << i << " = " << sArr[i]; // gives expected
output
tmp = (sArr[i] - 48); // gives expected number

}
return tmp;
}


Regards,
Jim

[Gianni Mariani]

Re: String to double conversion - Part 2

Evyn wrote:
....

The prof. was happy, but he told me to write my own atof. So I have
converted the string to an array of char. Is this the right strategy?

No need.

If so, how to I actually convert the array to a double? (As you no
doubt can see, I am pretty much in the dark here).

The basis for lexical analysis is "state machine". Think about what a
floating point number looks like.

+1.e-3
-.3
+.0e0
1e-1
..1
1

- starts with optional + or -
- either of -
digits
-or-
"." digits
-or-
digits "." digits
- the optionally
"e" or "E" followed by optional "+" or "-" followed by digits


state machine would look like:

state_0
\+ -state_1
\- -state_1
\. -state_2
0-9 -state_3
{eof} -state_4
state_4
FINAL
No transitions for this dfa state
state_1
\. -state_2
0-9 -state_3
state_3
ACCEPT
\. -state_5
0-9 -state_3
E -state_6
e -state_6
state_10
ACCEPT
0-9 -state_10
E -state_6
e -state_6
state_5
ACCEPT
0-9 -state_9
E -state_6
e -state_6
state_9
ACCEPT
0-9 -state_9
E -state_6
e -state_6
state_2
0-9 -state_10
state_8
ACCEPT
0-9 -state_8
state_6 (exponent)
\+ -state_7
\- -state_7
0-9 -state_8
state_7 (exponent)
0-9 -state_8


That's an 11 state state machine.

The basic algorithm is:

state = state_0;
double last_accepted_v alue = 0;
has_accepted = false;

while ( has_another_cha r )
{
ch = next_value;

switch( state )
{

.... set the "has_accepp ted" flag and the accept value if it is an
accepted state
}
}

if (has_accepted)
{
return accpeted value;
}

throw or something.

It's a really rough explanation so I hope it helps but it should give
you an idea of the kind of books you can read or other examples you can
look at.

[osmium]

Re: String to double conversion - Part 2

"Gianni Mariani" writes:

Evyn wrote:
...

>The prof. was happy, but he told me to write my own atof. So I have
>converted the string to an array of char. Is this the right strategy?

>
No need.
>

>If so, how to I actually convert the array to a double? (As you no
>doubt can see, I am pretty much in the dark here).

>
The basis for lexical analysis is "state machine". Think about what a
floating point number looks like.
>
+1.e-3
-.3
+.0e0
1e-1
.1
1

<snip nice explanation>

Another way that may be helpful is to produce a "railroad track" syntax
chart (as commonly used in Pascal) for allowable representations for a
double. I find such a method easier to follow.

http://en.wikipedia.org/wiki/Syntax_diagram

[Gianni Mariani]

Re: String to double conversion - Part 2

osmium wrote:

"Gianni Mariani" writes:
>

>Evyn wrote:
>...

>>The prof. was happy, but he told me to write my own atof. So I have
>>converted the string to an array of char. Is this the right strategy?

>No need.
>>

>>If so, how to I actually convert the array to a double? (As you no
>>doubt can see, I am pretty much in the dark here).

>The basis for lexical analysis is "state machine". Think about what a
>floating point number looks like.
>>
>+1.e-3
>-.3
>+.0e0
>1e-1
>.1
>1

>
<snip nice explanation>
>
Another way that may be helpful is to produce a "railroad track" syntax
chart (as commonly used in Pascal) for allowable representations for a
double. I find such a method easier to follow.
>

http://en.wikipedia.org/wiki/Syntax_diagram

>
>

The state machine in my previous post was generated from this:

digit = <0-9.
sign = <+\-.
opt_sign = [ sign , 0, 1 ] .
digits = [ digit, 1, ] .
exp = <eEopt_sign digits .
opt_exp = [ exp, 0, 1 ] .
float =
opt_sign (digits|("." digits)|(digits "."[digit,0,])) opt_exp .

.... it's an aardvark lexical analyser syntax.

[James Kanze]

Re: String to double conversion - Part 2

On Oct 10, 3:54 pm, Gianni Mariani <gi4nos...@mari an.wswrote:

Evyn wrote:

...

The prof. was happy, but he told me to write my own atof. So I have
converted the string to an array of char. Is this the right strategy?

No need.

If so, how to I actually convert the array to a double? (As you no
doubt can see, I am pretty much in the dark here).

The basis for lexical analysis is "state machine". Think about what a
floating point number looks like.

[Detailed explination deleted...]

You're right, of course, but I rather suspect (or hope for him,
at least) that this is more than what the prof wanted. And of
course, it's only the tip of the iceberg; the real problem is
doing the actual conversion without introducing rounding errors.
Thus, for example, if---as seems to be the case---the only
floating point values he'll really have to convert are of the
form \.[0-9]+, the obvious answer is a simple loop over the
digits:

double value = 0.0 ;
while ( *iter != end
&& isdigit( static_cast< unsigned char >( *iter ) ) {
value += *iter - '0' ;
value /= 10 ;
}

Except that, of course, this doesn't work in practice.

--
James Kanze (GABI Software) email:james.kan ze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

[Evyn]

Re: String to double conversion - Part 2

Thanks for the help and advice! Let me give it a go.