C/the.ansi.c.programming.language/c.programming.notes/homework/PS4.html

   1 <!DOCTYPE HTML PUBLIC "-//W3O//DTD W3 HTML 2.0//EN">
   2 <!-- This collection of hypertext pages is Copyright 1995-7 by Steve Summit. -->
   3 <!-- This material may be freely redistributed and used -->
   4 <!-- but may not be republished or sold without permission. -->
   5 <html>
   6 <head>
   7 <link rev="owner" href="mailto:scs@eskimo.com">
   8 <link rev="made" href="mailto:scs@eskimo.com">
   9 <title>Assignment #4</title>
  10 </head>
  11 <body>
  12 <H1>Assignment #4</H1>
  13
  14
  15
  16
  17
  18 <B>Introductory C Programming
  19 <br>
  20 <br>
  21 UW Experimental College
  22 </B><br>
  23 <br>
  24 <B>Assignment #4
  25 </B><p><B>Handouts:
  26 </B></p><p><a href="PS4.html">Assignment #4</a>
  27 <br><a href="PS3a.html">Answers to Assignment #3</a>
  28 <br>Class Notes, Chapters
  29 <a href="http://www.eskimo.com/~scs/cclass/notes/sx6.html">6</a>,
  30 <a href="http://www.eskimo.com/~scs/cclass/notes/sx7.html">7</a>,
  31 and
  32 <a href="http://www.eskimo.com/~scs/cclass/notes/sx8.html">8</a>
  33 <br>``Expressions and Statements'' handout
  34 <p><B>Reading Assignment:
  35 </B></p><p><a href="http://www.eskimo.com/~scs/cclass/notes/sx6.html">Class Notes, Chapter 6</a>
  36 <br><a href="http://www.eskimo.com/~scs/cclass/notes/sx7.html">Class Notes, Chapter 7</a>
  37 (Sec. 7.3 is a bit advanced, but do at least skim it)
  38 <br><a href="http://www.eskimo.com/~scs/cclass/notes/sx8.html">Class Notes, Chapter 8</a>
  39 <p><B>Review Questions:
  40 </B></p><OL><li>What would the expression
  41 <pre>
  42         c = getchar() != EOF
  43 </pre>
  44 do?
  45 <li>Why must the variable used to hold <TT>getchar</TT>'s return value be
  46 type <TT>int</TT>?
  47 <li>What is the difference between the prefix and postfix forms
  48 of the <TT>++</TT> operator?
  49 <li>(trick question)
  50 What would the expression
  51 <pre>
  52         i = i++
  53 </pre>
  54 do?
  55 <li>What is the definition of a string in C?
  56 <li>(Advanced)
  57 What will the <TT>getline</TT> function
  58 from
  59
  60 section 6.3
  61 of the notes
  62 do
  63 if successive calls to <TT>getchar</TT> return the four values
  64 <TT>'a'</TT>, <TT>'b'</TT>, <TT>'c'</TT>, and <TT>EOF</TT>?
  65 Is <TT>getline</TT>'s behavior reasonable?
  66 Is it possible for this situation to occur,
  67 that is,
  68 for a ``line'' somehow not to be terminated by <TT>\n</TT>?
  69 </OL><br>
  70 <br>
  71 <p><B>Tutorial Section:
  72 </B></p><OL><li>Here is a toy program for computing your car's gas mileage.
  73 It asks you for the distance driven on the last tank of gas,
  74 and the amount of gas used
  75 (i.e. the amount of the most recent fill-up).
  76 Then it simply divides the two numbers.
  77 <pre>
  78 #include &lt;stdio.h&gt;
  79 #include &lt;stdlib.h&gt;       /* for atoi() */
  80
  81 int getline(char [], int);
  82
  83 int main()
  84 {
  85         char inputline[100];
  86         float miles;
  87         float gallons;
  88         float mpg;
  89
  90         printf("enter miles driven:\n");
  91         getline(inputline, 100);
  92         miles = atoi(inputline);
  93
  94         printf("enter gallons used:\n");
  95         getline(inputline, 100);
  96         gallons = atoi(inputline);
  97
  98         mpg = miles / gallons;
  99         printf("You got %.2f mpg\n", mpg);
 100
 101         return 0;
 102 }
 103
 104 int getline(char line[], int max)
 105 {
 106 int nch = 0;
 107 int c;
 108 max = max - 1;                  /* leave room for '\0' */
 109
 110 while((c = getchar()) != EOF)
 111         {
 112         if(c == '\n')
 113                 break;
 114
 115         if(nch &lt; max)
 116                 {
 117                 line[nch] = c;
 118                 nch = nch + 1;
 119                 }
 120         }
 121
 122 if(c == EOF &amp;&amp; nch == 0)
 123         return EOF;
 124
 125 line[nch] = '\0';
 126 return nch;
 127 }
 128 </pre>
 129 For each of the two pieces of information requested
 130 (mileage and gallons)
 131 the code uses a little three-step procedure:
 132 (1) print a prompt,
 133 (2) read the user's response as a string,
 134 and
 135 (3) convert that string to a number.
 136 The same character array variable, <TT>inputline</TT>,
 137 can be to hold the string
 138 used both times,
 139 because we don't care about keeping the string around
 140 once we've converted it to a number.
 141 The function for converting a string to an integer is <TT>atoi</TT>.
 142 (The compiler then automatically converts the integer returned by
 143 <TT>atoi</TT> into a floating-point number to be stored in
 144 <TT>miles</TT> or <TT>gallons</TT>.
 145 There's another function we could have used, <TT>atof</TT>,
 146 which converts a string--possibly including a decimal point--directly
 147 into a floating-point number.)
 148 <br>
 149 <br>
 150 You might wonder why we're reading the user's response as a string,
 151 only to turn around and convert it to a number.
 152 Isn't there a way to read a numeric response directly?
 153 There is
 154 (one way is with a function called <TT>scanf</TT>),
 155 but we're going to do it this way
 156 because it will give us more flexibility later.
 157 (Also, it's much harder to react gracefully to any errors by the
 158 user
 159 if you're using <TT>scanf</TT> for input.)
 160 <br>
 161 <br>
 162 Obviously, this program would be a nuisance to use if you had
 163 several pairs of mileages and gallonages to compute.
 164 You'd probably want the program to prompt you repetitively for
 165 additional pairs, so that you wouldn't have to re-invoke the
 166 program each time.
 167 Here is a revised version which has that functionality.
 168 It keeps asking you for more distances and more gallon amounts,
 169 until you enter 0 for the mileage.
 170 <pre>
 171 #include &lt;stdio.h&gt;
 172 #include &lt;stdlib.h&gt;       /* for atoi() */
 173
 174 int getline(char [], int);
 175
 176 int main()
 177 {
 178         char inputline[100];
 179         float miles;
 180         float gallons;
 181         float mpg;
 182
 183         for(;;)
 184                 {
 185                 printf("enter miles driven (0 to end):\n");
 186                 getline(inputline, 100);
 187                 miles = atoi(inputline);
 188
 189                 if(miles == 0)
 190                         break;
 191
 192                 printf("enter gallons used:\n");
 193                 getline(inputline, 100);
 194                 gallons = atoi(inputline);
 195
 196                 mpg = miles / gallons;
 197                 printf("You got %.2f mpg\n\n", mpg);
 198                 }
 199
 200         return 0;
 201 }
 202 </pre>
 203 The (slightly) tricky part about writing a program like this is:
 204 what kind of a loop should you use?
 205 Conceptually, it seems you want some sort of a while loop along
 206 the lines of ``<TT>while(miles != 0)</TT>''.
 207 But that won't work, because we don't have the value of
 208 <TT>miles</TT>
 209 until after we've prompted the user for it and read it in and
 210 converted it.
 211 <br>
 212 <br>
 213 Therefore, the code above uses what at first looks like an
 214 infinite loop: ``<TT>for(;;)</TT>''.
 215 A <TT>for</TT> loop with no condition tries to run forever.
 216 But, down in the middle of the loop,
 217 if we've obtained a value of 0 for <TT>miles</TT>,
 218 we execute the <TT>break</TT> statement which forces the loop to terminate.
 219 This sort of situation
 220 (when we need the body of the loop to run part way through before
 221 we can decide whether we really wanted to make that trip or not)
 222 is precisely what the <TT>break</TT> statement is for.
 223 <li>Next, we're going to write our own version of the <TT>atoi</TT> function,
 224 so we can see how it works
 225 (or might work)
 226 inside.
 227 (I say ``might work'' because there's no guarantee that
 228 your compiler's particular implementation of <TT>atoi</TT> will
 229 work just like this one, but it's likely to be similar.)
 230 <pre>
 231 int myatoi(char str[])
 232 {
 233         int i;
 234         int digit;
 235         int retval = 0;
 236
 237         for(i = 0; str[i] != '\0'; i = i + 1)
 238                 {
 239                 digit = str[i] - '0';
 240                 retval = 10 * retval + digit;
 241                 }
 242
 243         return retval;
 244 }
 245 </pre>
 246 You can try this function out and work with it
 247 by rewriting the gas-mileage program slightly to use it.
 248 (Just replace the two calls to <TT>atoi</TT> with <TT>myatoi</TT>.)
 249 <br>
 250 <br>
 251 Remember, the definition of a string in C is that it is an array
 252 of characters, terminated by <TT>'\0'</TT>.
 253 So the basic strategy of this function is to look at the input
 254 string,
 255 one character at a time,
 256 from left to right,
 257 until it finds the terminating <TT>'\0'</TT>.
 258 <br>
 259 <br>
 260 The characters in the string are assumed to be digits:
 261 <TT>'1'</TT>, <TT>'5'</TT>, <TT>'7'</TT>, etc.
 262 Remember that in C, a character's value is the numeric value of
 263 the corresponding character in the machine's character set.
 264 It turns out that we can write this string-to-number conversion
 265 code <em>without</em> knowing what character set our machine uses
 266 or what the values are.
 267 (If you're curious, in the ASCII character set which most
 268 machines use, the character
 269 <TT>'0'</TT> has the value 48,
 270 <TT>'1'</TT> has the value 49,
 271 <TT>'2'</TT> has the value 50,
 272 etc.)
 273 <br>
 274 <br>
 275 Whatever value the character <TT>'0'</TT> has,
 276 <TT>'0' - '0'</TT> will be zero.
 277 (<em>Anything</em> minus itself is 0.)
 278 In any realistic character set,
 279 <TT>'1'</TT> has a value 1 greater than <TT>'0'</TT>,
 280 so <TT>'1' - '0'</TT> will be 1.
 281 Similarly, <TT>'2' - '0'</TT> will be 2.
 282 So we can get the ``digit'' value of a character
 283 (on the range 0-9) by subtracting the value of the
 284 character <TT>'0'</TT>.
 285 Now all we have to do is figure out how to combine the digits
 286 together into the final value.
 287 <br>
 288 <br>
 289 If you look at the number 123 from left to right, the first thing
 290 you see is the digit 1.
 291 You might imagine that you'd seen the whole number,
 292 until you saw the digit 2 following it.
 293 So now you've seen the digits 1 2,
 294 and how you can get the number 12 from the digits 1 and 2
 295 is to multiply the 1 by 10 and add the 2.
 296 But wait!
 297 There's still a digit 3 to come,
 298 but if you multiply the 12 by 10 and add 3, you get 123,
 299 which is the answer you wanted.
 300 So the algorithm for converting digits to their decimal value is:
 301 look at the digits from left to right,
 302 and for each digit you find, multiply the number you had before by 10
 303 and add in the digit you just found.
 304 (When the algorithm begins, ``the number you had before''
 305 starts out as 0.)
 306 When you run out of digits, you're done.
 307 (The code above uses a variable named <TT>retval</TT> to keep track
 308 of ``the number you had before'', because it ends up being the
 309 value to be returned.)
 310 <br>
 311 <br>
 312 If you're not convinced that this algorithm will work,
 313 try adding the line
 314 <pre>
 315         printf("digit = %d, retval = %d\n", digit, retval);
 316 </pre>
 317 at the end of the loop,
 318 so you can watch it as it runs.
 319 <br>
 320 <br>
 321 The code above works correctly as long as the string contains
 322 digits and only digits.
 323 But if
 324 the string contained, say, the letter <TT>'Q'</TT>,
 325 the code would compute the value <TT>'Q' - '0'</TT>,
 326 which would be a meaningless number.
 327 So we'd like to have the code do something reasonable if it
 328 should happen to encounter any non-digits
 329 (that is, if someone should happen to call it with a string
 330 containing non-digits).
 331 <br>
 332 <br>
 333 One way for the string to contain non-digits is if it contains
 334 any leading spaces.
 335 For example,
 336 the string <TT>"   123"</TT> should clearly be
 337 converted to the value 123,
 338 but our code above wouldn't be able to do so.
 339 One thing we need to do is skip leading spaces.
 340 And the other thing we'll do
 341 (which isn't perfect, but is a reasonable compromise)
 342 is that if we hit a non-space, non-digit character,
 343 we'll just stop
 344 (i.e. as if we'd reached the end of the string).
 345 This means that the call <TT>myatoi("123abc")</TT> will return 123,
 346 and <TT>myatoi("xyz")</TT> will return 0.
 347 (As it happens,
 348 the standard <TT>atoi</TT> function will behave exactly the same way.)
 349 <br>
 350 <br>
 351 Classifying characters (space, digit, etc.) is easy if we include
 352 the header file <TT>&lt;ctype.h&gt;</TT>,
 353 which gives us functions like
 354 <TT>isspace</TT> which returns true if a character is a space character,
 355 and
 356 <TT>isdigit</TT> which returns true if a character is a digit character.
 357 <br>
 358 <br>
 359 Putting this all together, we have:
 360 <pre>
 361 #include &lt;ctype.h&gt;
 362
 363 int myatoi(char str[])
 364 {
 365         int i;
 366         int retval = 0;
 367
 368         for(i = 0; str[i] != '\0'; i = i + 1)
 369                 {
 370                 if(!isspace(str[i]))
 371                         break;
 372                 }
 373
 374         for(; str[i] != '\0'; i = i + 1)
 375                 {
 376                 if(!isdigit(str[i]))
 377                         break;
 378                 retval = 10 * retval + (str[i] - '0');
 379                 }
 380
 381         return retval;
 382 }
 383 </pre>
 384 (You may notice that I've deleted the <TT>digit</TT> variable in
 385 this second example, because we didn't really need it.)
 386 <br>
 387 <br>
 388 There are now two loops.
 389 The first loop starts at 0 and looks for space characters;
 390 it stops
 391 (using a <TT>break</TT> statement)
 392 when it finds the first non-space character.
 393 (There may not be any space characters, so it may stop right away,
 394 after making zero full trips through the loop.
 395 And the first loop doesn't do anything except look for non-space characters.)
 396 The second loop starts where the first loop left off--that's why
 397 it's written as
 398 <pre>
 399         for(; str[i] != '\0'; i = i + 1)
 400 </pre>
 401 The second loop looks at digits;
 402 it stops early if it finds a non-digit character.
 403 <br>
 404 <br>
 405 The remaining problem with the <TT>myatoi</TT> function is that
 406 it doesn't handle negative numbers.
 407 See if you can add this functionality.
 408 The easiest way is to look for a <TT>'-'</TT> character up front,
 409 remember whether you saw one, and then at the end,
 410 after reaching the end of the digits and just before returning <TT>retval</TT>,
 411 negate <TT>retval</TT> if you saw the <TT>'-'</TT> character earlier.
 412 <li>Here
 413 is a silly little program
 414 which asks you to type a word, then does something unusual with
 415 it.
 416 <pre>
 417 #include &lt;stdio.h&gt;
 418
 419 extern int getline(char [], int);
 420
 421 int main()
 422 {
 423         char word[20];
 424         int len;
 425         int i, j;
 426
 427         printf("type something: ");
 428         len = getline(word, 20);
 429
 430         for(i = 0; i &lt; 80 - len; i++)
 431                 {
 432                 for(j = 0; j &lt; i; j++)
 433                         printf(" ");
 434                 printf("%s\r", word);
 435                 }
 436         printf("\n");
 437
 438         return 0;
 439 }</pre>
 440 (To understand how it works, you need to know that <TT>\r</TT> prints
 441 a carriage return without a linefeed.)
 442 Type it in and see what
 443 it does.
 444 (You'll also need a copy of the <TT>getline</TT> function.)
 445 See if you can
 446 modify the program to move the word from right to
 447 left instead of left to right.
 448 </OL><br>
 449 <br>
 450 <p><B>Exercises:
 451 </B></p><OL><li>Type in the character-copying program from
 452
 453 section 6.2
 454 of the notes, and run it to see how it works.
 455 (When
 456 you run it, it will wait for you to type some input.  Type a few
 457 characters, hit RETURN; type a few more characters, hit RETURN
 458 again.  Hit control-D or control-Z when you're finished.)
 459 <li>Type in the <TT>getline()</TT> function
 460 and its
 461 test program
 462 from
 463
 464 section 6.3
 465 of the notes,
 466 and run it to see how it works.  You can either place
 467 <TT>getline()</TT> and its test program (<TT>main()</TT>) in one source file or,
 468 for extra credit, place <TT>getline()</TT> in a file <TT>getline.c</TT> and the
 469 test program in a file <TT>getlinetest.c</TT> (or perhaps <TT>gtlntst.c</TT>), for
 470 practice in compiling a program from two separate source files.
 471 <li>Rewrite the <TT>getline</TT> test program from Exercise 2
 472 to use the loop
 473 <pre>
 474         while(getline(line, 256) != EOF)
 475                 printf("%s\n", line);
 476 </pre>
 477 That is, have it simply copy a line at a time, without printing
 478 ``You typed''.  Compare the behavior of the character-copying and
 479 line-copying programs.  Do they behave differently?
 480 <br>
 481 <br>
 482 Now rewrite the character-copying program from Exercise 1 to use the loop
 483 <pre>
 484         while((c = getchar()) != EOF)
 485                 printf("you typed '%c'\n", c);
 486 </pre>
 487 and try running it.  Now do things make more sense?
 488 <li>The standard library contains a function, <TT>atoi</TT>, which
 489 takes a string (presumably a string of digits) and converts it
 490 to an integer.  For example, <TT>atoi("123")</TT> would return the integer
 491 123.
 492 <br>
 493 <br>
 494 Write a program which reads lines (using <TT>getline</TT>), converts each
 495 line to an integer using <TT>atoi</TT>, and computes the average of all
 496 the numbers read.  (Like the example programs in the notes, it
 497 should determine the end of ``all the numbers read'' by checking for
 498 <TT>EOF</TT>.)
 499 See how much of the code from
 500
 501 assignment 3, exercise 7
 502 you can reuse
 503 (if you did that exercise).
 504 Remember
 505 that integer division truncates, so you'll have to declare some
 506 of your variables as <TT>float</TT> or <TT>double</TT>.
 507 <br>
 508 <br>
 509 For extra credit, also compute the standard deviation
 510 (see
 511
 512 assignment 3, exercise 7).
 513 <li>Write a rudimentary checkbook balancing program.
 514 It will use <TT>getline</TT> to read a line, which will contain either
 515 the word <TT>"check"</TT> or <TT>"deposit"</TT>.  The next line will contain the
 516 amount of the check or deposit.  After reading each pair of lines,
 517 the program should
 518 compute and
 519 print the new balance.
 520 You can declare the variable to hold the running balance
 521 to be type <TT>float</TT>,
 522 and you can use the function <TT>atof</TT>
 523 (also in the standard library)
 524 to convert an amount string read by <TT>getline</TT>
 525 into a floating-point number.
 526 When the program reaches end-of-file
 527 while reading <TT>"check"</TT> or <TT>"deposit"</TT>, it should exit.  (In outline,
 528 the program will be somewhat similar to the average-finding program.)
 529 <br>
 530 <br>
 531 For example, given the input
 532 <pre>
 533         deposit
 534         100
 535         check
 536         12.34
 537         check
 538         49.00
 539         deposit
 540         7.01
 541 </pre>
 542 the program should print something like
 543 <pre>
 544         balance: 100.00
 545         balance: 87.66
 546         balance: 38.66
 547         balance: 45.67
 548 </pre>
 549 <br>
 550 <br>
 551 Extra credit:
 552 Think about how you might
 553 have the program
 554 take the word <TT>"check"</TT> or <TT>"deposit"</TT>, <em>and</em>
 555 the amount, from a single line (separated by whitespace).
 556 <li>Rewrite the ``compass'' code from
 557
 558 Assignment 2 (exercise 4)
 559 to use <TT>strcpy</TT> and <TT>strcat</TT> to build the <TT>"northeast"</TT>, <TT>"southwest"</TT>,
 560 etc. strings.  (Don't worry about capitalizing them carefully.)
 561 You should be able to write it in a cleaner way, without so many
 562 <TT>if</TT>'s and <TT>else</TT>'s.  Remember to declare the array in which you build
 563 the string big enough to hold the largest string you build (including
 564 the trailing <TT>\0</TT>).
 565 <li>Write a program to read its input, one character at
 566 a time, and print each character <em>and</em> its decimal value.
 567 <li>Write a program to read its input, one line at a time,
 568 and print each line backwards.  To do the reversing, write a function
 569 <pre>
 570         int reverse(char line[], int len)
 571         {
 572         ...
 573         }
 574 </pre>
 575 to reverse a string, in place.  (It doesn't have to return anything
 576 useful.)
 577 </OL><hr>
 578 <hr>
 579 <p>
 580 This page by <a href="http://www.eskimo.com/~scs/">Steve Summit</a>
 581 // <a href="copyright.html">Copyright</a> 1995-9
 582 // <a href="mailto:scs@eskimo.com">mail feedback</a>
 583 </p>
 584 </body>
 585 </html>