Hunter Liu's Website

7. Week 4 Tuesday: Loops

Prior to discussing loops, our primary way of making our programs interactive was by asking the user for some inputs (sometimes) and then having some branching logic involving if statements. These programs tend to be underwhelming, and anything more sophisticated was out of reach. Even a simple word game like hangman is out of reach. Thinking through the pseudocode very loosely, we’ll have to include a command like “Repeat until the user has run out of misses…” Moreover, we’ll have to “compare the user’s guess with each letter in the secret word”, etc. If statements alone simply aren’t enough.

The problem is that commands involving repetition aren’t possible with if statements alone (sort of, but we don’t talk about goto). This is of course exactly what loops help us do.

These come in two main flavours. First, there’s while loops, which address commands like “repeat while some condition is met” or “repeat until some condition is met”. The syntax is

1while( /* condition */ ) {
2    /* code */ 
3} 

C++ interprets this as the following set of commands:

1. Check if condition is true.
2. If yes, execute the code and go back to step 1.
3. If no, end the loop.

That’s it! Draw a flowchart if these three steps are confusing.

What’s most important is that C++ will check the condition before each iteration of the loop; forgetting about this order of events is a common source of mistakes.

The other flavour of loops are for loops, which address commands like “repeat for every character in this string” or “repeat for every integer \(1, 2, \ldots, n\)” (which is equivalent to repeating something \(n\) times). The for loop’s syntax is more complicated and is comprised of four parts:

1for(/* setup */; /* condition */; /* update */) {
2    /* code */
3} 

Everything in the for loop is an expression, and I have made the semicolons between them clear. C++ interprets the above as follows:

1. Execute the setup command once.
2. Check if the condition is true.
3. If it is, execute the code in the body, then execute the update command and return to step 2.
4. If it isn’t, end the loop.

Again, a flowchart may be a better depiction of this process.

1for(/* setup */; /* condition */; /* update */) {
2    /* code */ 
3} 

1/* setup */; 
2while(/* condition */) {
3    /* code */ 
4    /* update */ 
5} 

While these flowcharts can seem somewhat clunky and unnatural, there are some parallels to pseudocode that we can make:

• The pseudocode “Repeat command while condition is true” corresponds to the C++ code

  1while(/* condition */) {
  2    /* command */ 
  3} 
  

• The pseudocode “Repeat command \(N\) times” corresponds to the C++ code

  1for(int i = 0; i < N; i++) {
  2    /* command */ 
  3} 
  

  Replace \(N\) with whatever the number is; this can be a variable! Note also that there is a strict inequality…think about why.
• The pseudocode “Repeat command for each index \(i = 0, 1, \ldots, N - 1\)” corresponds to the C++ code

  1for(int i = 0; i < N; i++) {
  2    /* command */ 
  3} 
  

  This is typically used in conjunction with strings when one wants to perform an operation on each character.

That was quite a bit of text, so let’s look at an example.

Sample Run: 
INPUT  I live at 123 RAM Street. 
OUTPUT I live at *** RAM Street. 

Let’s write some pseudocode first to describe what we want to happen.

1. Accept a line of text from the user’s input and store it in a string variable line.
2. For each character c in the user’s input, repeat the following:
   • If c is a digit, replace it with an asterisk.
   • Otherwise, do nothing.
3. Print out the modified string.

But how can we use loops to do something for every character c in a string? At some point, we’re going to have to use the .at() function for strings, and we’ll be repeating some operation on line.at(0), line.at(1), etc. So, we ought to rephrase our pseudocode in terms of the index rather than the character:

1. Accept a line of text from the user’s input and store it in a string variable line. Let N be its length.
2. For each index i = 0, 1, 2, ..., N - 1, repeat the following:
   • Set c to the character at index i.
   • If c is a digit, replace it with an asterisk.
   • Otherwise, do nothing.
3. Print out the modified string.

Let’s convert this to code step by step.

For the first step, we need to be sensitive to spaces, so we’ll use getline rather than a cin.

1string line; 
2getline(cin, line); 
3int N = line.length(); 

For the second step, we’ll set up a for loop and write out the code according to the template earlier:

 1for(int i = 0; i < N; i++) {
 2    // get the character at index
 3    char c = line.at(i); 
 4
 5    // if it's a digit, replace it! 
 6    if(c >= '0' && c <= '9') {
 7        line.at(index) = '*'; 
 8        // why doesn't "c = '*';" work? 
 9    } 
10
11    // otherise, do nothing (no code) 
12} 

And of course, at the end, we’ll need to print something out.

1cout << line << endl; 

Let’s take a look at another similar example.

Sample Run:
INPUT   John Smith
OUTPUT  JOHN SMITH

INPUT   John Old McDonald
OUTPUT  JOHN OLD MCDONALD

INPUT   John O'Niel McDonald, Sr.
OUTPUT  JOHN ONIEL MCDONALD SR

As usual, we’ll begin by producing some pseudocode. The first approach we’ll demonstrate is one where we create a fresh empty string, then append alphabetic characters from the user’s input one at a time (capitalising if necessary) and skipping over the non-space non-alphabetic characters. More specifically,

1. Take a string full_name as input, and let N be the length of the input.
2. Create an empty string called all_caps.
3. For each index i = 0, 1, ..., N-1, perform the following:
   • Let ch be the character at index i in the user’s input.
   • If ch is a space or an upper-case letter, append it to all_caps.
   • If ch is a lower-case letter, convert it to upper-case, then append it to all_caps.
   • Otherwise, don’t do anything with ch and keep going.
4. Print out all_caps to the screen.

Let’s now convert this to code. We’ll be reliant on ASCII math and writing loops to do so. First, to take a full name as an input (which may include spaces), we should use getline rather than a direct cin statement.

1string full_name;
2getline(cin, full_name);
3int N = full_name.length();

Next, we’ll create the empty string.

1string all_caps = "";

For the loop, we’ll elect to use a for loop: we are repeating an instruction for each index of a string again. To append a character to a string, you can either use the push_back function or the += operator.

 1for(int i = 0; i < N; i++) {
 2    // obtaining the character at index i
 3    char ch = full_name.at(i);
 4
 5    // space or uppercase character: just add it to all_caps
 6    if(ch == ' ' || (ch >= 'A' && ch <= 'Z')) {
 7        all_caps += ch;
 8    }
 9
10    // lowercase character: convert to uppercase, then add.
11    if(ch >= 'a' && ch <= 'z') {
12        ch += 'A' - 'a';
13        all_caps += ch;
14    }
15
16    // remaining cases: just ignore them and don't do anything.
17}

The last step, of course, is to print out all_caps to the screen. here’s the completed code:

 1#include <iostream>     // cin, cout
 2#include <string>       // getline, strings
 3
 4using namespace std;
 5
 6int main() {
 7    // 1. read input, define N
 8    string full_name;
 9    getline(cin, full_name);
10    int N = full_name.length();
11
12    // 2. declare all_caps as empty string
13    string all_caps = "";
14
15    // 3. loop through the full_name string,
16    //    one character at a time.
17    for(int i = 0; i < N; i++) {
18        // obtaining the character at index i
19        char ch = full_name.at(i);
20
21        // space or uppercase character: just add it to all_caps
22        if(ch == ' ' || (ch >= 'A' && ch <= 'Z')) {
23            all_caps += ch;
24        }
25
26        // lowercase character: convert to uppercase, then add.
27        if(ch >= 'a' && ch <= 'z') {
28            ch += 'A' - 'a';
29            all_caps += ch;
30        }
31
32        // remaining cases: just ignore them and don't do anything.
33    }
34
35    // 4. print out the result.
36    cout << all_caps << endl;
37
38    return 0;
39}

There is an alternative solution. It’s somewhat unnatural to define a new string and rebuild the user’s input one character at a time; I suspect more human pseudocode would be as follows:

1. Take a string full_name as input and define N as its length.
2. For each index i = 0, 1, ..., N - 1, perform the following:
   • Define ch as the character at index i in full_name.
   • If ch is a lowercase letter, convert it to uppercase.
   • If ch is neither a space nor a letter, remove it from the string.
3. Print full_name to the screen.

To remove a character from a string, we can use the erase function for strings. This pseudocode directly modifies the user’s input, deleting unwanted characters and capitalising lowercase letters as we go. Let’s code this solution up:

 1// 1. read full name from user input
 2string full_name;
 3getline(cin, full_name);
 4int N = full_name.length();
 5
 6// 2. for each index 0, 1, ...., N - 1
 7for(int i = 0; i < N; i++) {
 8    // obtain character at index i
 9    char ch = full_name.at(i);
10
11    // if ch is lowercase, convert to uppercase
12    if(ch >= 'a' && ch <= 'z') {
13        // note: we should not modify ch, since it's a copy
14        // of the character in the string full_name.
15        full_name.at(i) += 'A' - 'a';
16    }
17
18    // if ch is NOT a space and NOT an uppercase letter,
19    // delete the character from the string
20    if(ch != ' ' && (ch < 'A' || ch > 'Z')) {
21        // erases one character, starting at index i.
22        full_name.erase(i, 1);
23    }
24
25    // in remaining cases, do nothing!
26}
27
28// 3. print out results.
29cout << full_name << endl;

The two problems in the code are as follows: first, the length of the string may decrease throughout the for loop. If we ever end up deleting a character, i = N - 1 would cease to be a valid index, resulting in a runtime error. The fix to this is to remove line 4, and replace the condition in the for loop with i < full_name.length(). This tells the for loop to check the length of the string at every iteration, making it robust to changes in string length.

The second problem is more subtle, and it’s revealed when we input john o'neil. The output becomes JOHN OnEIL; the for loop somehow skips over the n following the apostrophe. The reason is that when i = 6, we delete the apostrophe and update the index to i = 7. But when we delete the apostrophe, the n moves to index i = 6! This index shifting causes the for loop to skip over the n and leave it as-is. The fix is to add i-- after line 22 to adjust the index according to this backwards shift. This way, none of the characters get skipped inadvertently.