Monday, 29 June 2015

The Fifth Problem (3)

And then to evaluate the final string.  Work down the string keeping a running accumulator: each time you hit a digit, multiply your accumulator by 10 and add the value of the digit: but if you hit a plus or a minus, add or subtract the value of the remainder of the string.  So we get this:-

The main function...

val :: String -> Int
val s = valx 0 s

This works by calling its auxiliary function...

valx n [] = n
valx n (c:cs) =
    case c of
      '+' -> n + valx 0 cs
      '-' -> n - valx 0 cs
      _ -> valx ((n * 10) + (ord c - ord '0')) cs

And so...

*Main Data.Char> val "1+2+34-5+67-8+9"

Wrong answer.

The reason is that doing it recursively implicitlty brackets from the end of the string, so we are working out 1+(2+(34-(5+(67-(8+9))))) but really we want to work out (((((1+2)+34)-5)+67)-8)+9

OK so I want an auxiliary function that takes an accumulator for the whole expression, and as I go along a smaller accumulator for the value of the number I'm working through.  And a number -1 or +1 for the last sign character I encountered.

At the start, the accumulators are zero and the sign is +1.

Each time I hit either a + or a - character I either add or subtract the value of my current number to or from the accumulator.  Also I set the sign for the next number, and set the little accumulator back to

When I hit a digit I use it to increase the value of the current number.

So I get this:

eval :: String -> Int
eval s = evalx 0 0 1 s

evalx :: Int -> Int -> Int -> String -> Int

evalx acc cur sgn "" = 
    acc + (sgn * cur)

evalx acc cur sgn (c:cs) =
    case c of
      '+' -> evalx (acc + (sgn * cur)) 0 1 cs
      '-' -> evalx (acc + (sgn * cur)) 0 (-1) cs
      _ -> evalx acc ((cur * 10) + (ord(c) - ord('0'))) sgn cs

*Main Data.Char> eval "1+2+34-5+67-8+9"

This one does work.

No comments:

Post a Comment