Reading

Section 7.1 of Problem Solving with C++.

This changes everything ...

Several weeks ago, the addition of loops to our programs had a huge impact on the power we wielded as programmers. Before loops, the computer never performed more steps than the poor programmer typed in. With loops, a short, simple program could make the computer do an almost limitless amount of work!

Today we are introducing another game-changing idea: arrays. Up til now, a program couldn't store -- couldn't remember -- anything except in variables. This meant that the program coulcn't remember more data than the number of variables than the programmer put into the program — essentially the program can't remember more data than the programmer typed in while creating the program. Arrays shatter that limitation: an array is a single variable with which a program can store and retrieve a nearly limitless amount of data. With loops and arrays you can — very literally, and in a sense that is made mathematically rigorous in SI340, Theory of Computing — harness the full potential of the computer.

A Simple Problem Made Difficult

Let's start with a simple problem: Write a program that reads firstname lastname, and prints out firstname, lastname. For example, a typical run of the program might look like:
~/$ ./prog
Chris Brown
Brown, Chris
... where the red text is user input. This should be no problem, something like this will do:
string first, last;
cin >> first >> last;
cout << last << ", " << first << endl;
Now let's make things more difficult: Suppose I also want to capitalize all the letters in the names. No matter how hard you work with what we've learned of C++, there's no way you can write this program! You can capitalize, you can switch first and last names, you just can't do both together. The problem is that you need to access the characters within the strings first and last, and you need to know how many characters are in the strings.

The "how many characters are in the strings" part is easy. It turns out that whenever you have an object of type string you can put a .length() at the end of it and the resulting expression returns the length of the string. So, from the previous code I could ask for first.length() and (with first name "Chris") the result would be 5.

As you might suspect, it is also possible to reference characters within a string - not by specific names, but by indices. So the initial character of the string first, for example, has index 0. To reference it, say for printing, you write first[0], which we usually read as "first zub zero". Characters within a string are thus indexed from zero up to one less than the length of the string, like this:

Chris
01234

Using indices, we can make sure that every character within the string first is printed in capitals:
for(int i = 0; i < first.length(); i++)
  if ('a' <= first[i] && first[i] <= 'z')
    cout << char(first[i] - ('a' - 'A'));
  else
    cout << first[i];
In fact, it might be kind of nice to make a function to do the printing in capitals for us, and produce a program like this.

The Idea of Arrays

When we access an ordered collection of objects, all of the same type, by indices rather than by individual names, we are using arrays. This is one of the most powerful ideas in computer science, so you better learn to love it! The excercises below and the remainder of the notes here are just to help you play with the idea of accessing objects within an array by index rather than by specific name. A string is, essentially, and array of objects of type char. In coming lectures, you'll see that we can have arrays of any type of object we choose.
Donald Knuth http://xkcd.com/163/

Arrays allow us to store and compute with large amounts of information in programs without needing separate variable names for each object we store. In the past example, a single variable name first stood for as many char objects as needed.

The key behind this indexing with strings, is that the expression first[i] is an object of type char. (In particular, it is an lvalue of type char, meaning that it can, among other things, appear on the left-hand side of an assignment.) You don't need any special rules to tell you what you can and can't do with an expression like first[i], because anything you can do with a char you can do with it.
Important! The first item in the array is at index 0. Don't use a negative number for an index, and don't use a number that is greater than or equal to the length of the string! There aren't any characters there to index!

Modifying Strings

Now, we might want to actually change the string we've got - for example modify it so that all of its letters are capitals. We can do this the following way:
string s;
cin >> s;

for(int i = 0; i < s.length(); i++)
  if ('a' <= s[i] && s[i] <= 'z')
    s[i] = s[i] - ('a' - 'A');

cout << s << endl;
You say "How do I know I can assign a value to s[i] like that?" Well, s[i] is an lvalue of type char like any other so, you can assign to it just like you assign to any char variable!

Problems

  1. Print in reverse (non-recursive)
  2. Print in reverse (recursive!)
  3. A predicate that tests whether two strings are reverses of each other.
  4. palindromes
  5. A predicate that takes a string s and a char c, and tests whether or not c appears in s.