String to double conversion - Part 2

[Evyn]

Hi all,

I have recently asked for advice:
http://groups.google.com/group/comp...1b/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; // gives expected
output
tmp = (sArr - 48); // gives expected number

}
return tmp;
}


Regards,
Jim

 

[tragomaskhalos]

Hi all,

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 - see below.

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)

Don't pass strings by value, you may incur needless
copying; use const string& s

{
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

Apart from the fact that defining a variable-length
automatic array is non-standard, the above lines are
pointless; why are you *copying* the data ?

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

}

Your loop should then become:
for (int i = 0; i < s.size() ; ++i) {
int itmp = s - '0';
:
}
On each iteration itmp contains the integer value of
the character, eg '0' => 0, '1' => 1 etc (assuming
that string genuinely only contains digits)
You now need to figure out how to build up a double
from this. One way would be to divide itmp by
increasing powers of 10.0 and add the result to
an accumulator variable.

 

[Gianni Mariani]

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_value = 0;
has_accepted = false;

while ( has_another_char )
{
ch = next_value;

switch( state )
{

.... set the "has_acceppted" 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]

Evyn wrote:
...

No need.


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]

<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 = <eE> opt_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]

Evyn wrote:

No need.

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.

 

[Evyn]

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