2. String Traversal (by index), and the Accumulator Pattern with Strings

Quick Overview of Day

WDTPD string questions. Explore string traversal (for loop by index), in and not in operators, and the accumulator pattern with strings. Work on practice problems covering these ideas.

  • CS20-CP1 Apply various problem-solving strategies to solve programming problems throughout Computer Science 20.
  • CS20-FP1 Utilize different data types, including integer, floating point, Boolean and string, to solve programming problems.
  • CS20-FP2 Investigate how control structures affect program flow.
  • CS20-FP3 Construct and utilize functions to create reusable pieces of code.

2.1. What Does This Program Do?

Note

Your teacher may choose to use the following examples as a class activity, by displaying the examples, and having you take a guess as to what you think each will do before running the code.

What will the following programs output? Why?

2.2. Traversal and the for Loop: By Index

It is also possible to use the range function to systematically generate the indices of the characters. The for loop can then be used to iterate over these positions. These positions can be used together with the indexing operator to access the individual characters in the string.

Consider the following codelens example.

(string_for_loop_by_index_1)

The index positions in “apple” are 0,1,2,3 and 4. This is exactly the same sequence of integers returned by range(5). The first time through the for loop, current_index will be 0 and the “a” will be printed. Then, current_index will be reassigned to 1 and “p” will be displayed. This will repeat for all the range values up to but not including 5. Since “e” has index 4, this will be exactly right to show all of the characters.

In order to make the iteration more general, we can use the len function to provide the bound for range. This is a very common pattern for traversing any sequence by position. Make sure you understand why the range function behaves correctly when using len of the string as its parameter value.

You may also note that iteration by position allows the programmer to control the direction of the traversal by changing the sequence of index values. Recall that we can create ranges that count down as well as up so the following code will print the characters from right to left.

Note

Remember that when using the range() function with three arguments, the arguments are interpreted as starting_number, ending_number, and amount_to_step_by. The range function begins at the starting_number, and goes up to, but not including, the ending_number.

(string_for_loop_by_index_3)

Trace the values of current_index and satisfy yourself that they are correct. In particular, note the start and end of the range.

2.2.1. Check Your Understanding

    string-acc1: How many times is the letter o printed by the following statements?

    sentence = "python rocks"
    for current_index in range(len(sentence)):
      if current_index % 2 == 0:
          print(sentence[current_index])
    
  • 0
  • The for loop visits each index but the selection only prints some of them.
  • 1
  • o is at positions 4 and 8
  • 2
  • Yes, it will print all the characters in even index positions and the o character appears both times in an even location.
  • Error, the for statement cannot have an if inside.
  • The for statement can have any statements inside, including if as well as for.

2.3. The in and not in operators

The in operator tests if one string is a substring of another:

Note that a string is a substring of itself, and the empty string is a substring of any other string. (Also note that computer scientists like to think about these edge cases quite carefully!)

The not in operator returns the logical opposite result of in.

2.4. The Accumulator Pattern with Strings

Combining the in operator with string concatenation using + and the accumulator pattern, we can write a function that removes all the vowels from a string. The idea is to start with a string and iterate over each character, checking to see if the character is a vowel. As we process the characters, we will build up a new string consisting of only the nonvowel characters. To do this, we use the accumulator pattern.

Remember that the accumulator pattern allows us to keep a “running total”. With strings, we are not accumulating a numeric total. Instead we are accumulating characters onto a string.

Line 5 uses the not in operator to check whether the current character is not in the string vowels. The alternative to using this operator would be to write a very large if statement that checks each of the individual vowel characters. Note we would need to use logical and to be sure that the character is not any of the vowels.

if each_char != 'a'  and each_char != 'e'  and each_char != 'i'  and
   each_char != 'o'  and each_char != 'u'  and each_char != 'A'  and
   each_char != 'E'  and each_char != 'I'  and each_char != 'O'  and
   each_char != 'U':

     string_without_vowels = string_without_vowels + each_char

Look carefully at line 6 in the above program (string_without_vowels = string_without_vowels + each_char). We will do this for every character that is not a vowel. This should look very familiar. As we were describing earlier, it is an example of the accumulator pattern, this time using a string to “accumulate” the final result. In words it says that the new value of string_without_vowels will be the old value of string_without_vowels concatenated with the value of each_char. We are building the result string character by character.

Take a close look also at the initialization of string_without_vowels. We start with an empty string and then begin adding new characters to the end.

Step through the function using codelens to see the accumulator variable grow.

(string_accumulator_pattern_2)

2.4.1. Check Your Understanding

    string-acc2: What is printed by the following statements:

    some_string = "ball"
    another_string = ""
    for item in some_string:
        another_string = another_string + item
    print(another_string)
    
  • ball
  • Yes, the repeated concatenation will cause another_string to become the same as some_string.
  • llab
  • Look again at the *order* of the concatenation!

    string-acc3: What is printed by the following statements:

    some_string = "ball"
    another_string = ""
    for item in some_string:
        another_string = item + another_string
    print(another_string)
    
  • ball
  • Look again at the *order* of the concatenation!
  • llab
  • Yes, the order is reversed due to the order of the concatenation.

Consider the following table, which shows the values of the variables as the code iterates:

iteration item another_string item + another_string
1 "b" "" "b"
2 "a" "b" "ab"
3 "l" "ab" "lab"
4 "l" "lab" "llab"
        string-acc4: Construct a block of code that correctly implements the accumulator pattern with strings. After the code has finished executing, ``new_word`` is printed, and will have the same value as ``original_word``.original_word = "clockwork"
new_word = ""
for letter in original_word:
    new_word = new_word + letter
print(new_word)
        

2.5. Practice Problems

Try the following practice problems. You can either work directly in the textbook, or use Thonny. Either way, copy/paste your finished code into Thonny and save your solution into your Computer Science 20 folder when you finish!

Hint: For each of the following, you will want to use the accumulator pattern with strings. In other words, you first need to create an empty string, then concatenate letters onto it as needed.

2.5.1. Even Letters of a Word

Note

The only thing you need to do for this question is to complete the function definition! You do not need to call the function, as that will be done automatically for you.

Create a function with a single parameter word that returns the even letters of the word (the first letter is even, since we start counting our index values at 0). For example, given the word “Saskatoon”, the function should return “Ssaon”.

Examples:

even_letters("Saskatoon") "Ssaon"

even_letters("Saskatchewan") "Ssacea"

even_letters("Roughriders") "Ruhies"

Since you are trying to get only the even letters, you need to know which index value you are currently on. That means we need to traverse the string using a for counter in range() style loop. The accumulator pattern will look something like this:

def even_letters(word):
    new_word = ""
    for counter in range(len(word)):
        # add a question here...
        new_word = new_word + word[counter]
    return new_word

2.5.2. Reverse Me

Note

The only thing you need to do for this question is to complete the function definition! You do not need to call the function, as that will be done automatically for you.

Create a function with a single parameter word that returns the word spelled backwards. For example, if the word was “Saskatoon”, the function should return “nootaksaS”.

Examples:

reverse_me("Saskatoon") "nootaksaS"

reverse_me("Saskatchewan") "nawehctaksaS"

reverse_me("Roughriders") "sredirhguoR"

2.5.3. Letter Destroyer

Note

The only thing you need to do for this question is to complete the function definition! You do not need to call the function, as that will be done automatically for you.

Create a function with two parameters, word and letter_to_destroy. The function should return the word, but without any of the occurrences of the letter_to_destroy in the string. For example, if the word was “Saskatoon”, and the letter_to_destroy was ‘o’, the function should return “Saskatn”.

Examples:

letter_destroyer("Saskatoon", "o") "Saskatn"

letter_destroyer("Saskatchewan", "a") "Ssktchewn"

letter_destroyer("roughriders", "r") "oughides"

2.5.4. QWERTY Finder

Note

The only thing you need to do for this question is to complete the function definition! You do not need to call the function, as that will be done automatically for you.

Create a function that takes in a single parameter word and returns the location of the first occurrence of one of the following letters: “qwerty”. If none of these letters exist in the word, have the function return -1. For example, if the word was “Saskatoon”, the function should return 5 (the index value for the t in “Saskatoon”).

Examples:

qwerty_finder("Saskatoon") 5

qwerty_finder("Naomi") -1

qwerty_finder("bunnyhug") 4

Next Section - 3. String Methods