String processing II (tokenizing with state)

Many problems give you a string with items separated by a delimiter, like a comma or space. You need to split it into individual tokens and process each one. This is tokenization.

What is a token?

A token is a unit of text between delimiters. In the string "apple,banana,cherry", the delimiter is a comma, and the tokens are "apple", "banana", and "cherry". Tokenization is the process of extracting these units.

Building tokens with state

To tokenize, keep track of whether you are currently inside a token or between tokens. Start with an empty current token. Loop through each character. If the character is a delimiter, the token is complete, so save it and reset. If the character is not a delimiter, add it to the current token.

1s = "apple,banana,cherry"2tokens = []3current_token = ""4
5for char in s:6    if char == ",":7        tokens.append(current_token)8        current_token = ""9    else:10        current_token += char11
12if current_token:13    tokens.append(current_token)14
15for token in tokens:16    print(token)

This prints each token on its own line: apple, banana, cherry.

The key idea is state. At any point, you are either building a token or waiting for the next one. When you see a delimiter, you finish the current token and switch to waiting. When you see a non-delimiter character, you add it to the current token.

1s = input()2tokens = []3current_token = ""4
5for char in s:6    if char == ",":7        tokens.append(current_token)8        current_token = ""9    else:10        current_token += char11
12if current_token:13    tokens.append(current_token)14
15for token in tokens:16    print(token)

apple,banana,cherry

apple
banana
cherry

Handling edge cases

What if the string ends with a delimiter? The loop finishes, and current_token might still hold the last token. Check if current_token: after the loop and append it if it is not empty. This handles the case where the string ends without a trailing delimiter.

What if there are two delimiters in a row, like "apple,,banana"? After the first comma, current_token is appended (it is "apple"). After the second comma, current_token is empty. You might append an empty string, depending on the problem. If the problem forbids empty tokens, check if current_token: before appending.

Multiple delimiters

Some problems have multiple delimiters, like spaces and commas. You can check if the character is any of them:

1s = "apple, banana; cherry"2tokens = []3current_token = ""4
5for char in s:6    if char in ", ;":7        if current_token:8            tokens.append(current_token)9            current_token = ""10    else:11        current_token += char12
13if current_token:14    tokens.append(current_token)

The condition char in ", ;" checks whether the character is a space, comma, or semicolon. Any of them ends the current token.

A delimiter longer than one character

So far every delimiter has been a single character. Some problems separate items with a longer marker, such as "::" between fields in "name::score::rank". A single-character check like char == ":" would split on the wrong boundary, cutting "::" into two empty gaps instead of treating it as one separator.

The fix is to look ahead in the string instead of checking one character at a time. An index-based loop lets you peek further than the current position, so you can compare a whole slice to the delimiter rather than a single character.

1s = "name::score::rank"2tokens = []3current_token = ""4i = 05
6while i < len(s):7    if s[i:i + 2] == "::":8        tokens.append(current_token)9        current_token = ""10        i += 211    else:12        current_token += s[i]13        i += 114
15tokens.append(current_token)16print(tokens)

s[i:i + 2] is a two-character slice starting at i. When it matches "::", the token is complete, and i advances by 2 to skip both delimiter characters. Otherwise, the single character s[i] joins the current token, and i advances by 1. The output is ['name', 'score', 'rank'].

Trace the first few steps. At i = 0, s[0:2] is "na", which does not match "::", so "n" joins current_token and i becomes 1. This repeats for "a", "m", and "e", building current_token up to "name" by the time i reaches 4. At i = 4, s[4:6] is "::", so "name" is appended to tokens, current_token resets to "", and i jumps to 6, skipping both colons in a single step. The same pattern repeats for "score" and then "rank", and the final tokens.append(current_token) after the loop catches "rank", which never met a trailing delimiter.

A two-character slice at the very end of the string is safe, even when only one character remains there. s[i:i + 2] never raises an error the way indexing with s[i + 1] alone might. A slice that runs past the end of the string simply returns whatever characters remain, even an empty string, rather than crashing the program.

Validation while tokenizing

You can validate each token as you build it. For example, count the digits in a token:

1s = "apple123,banana45,cherry9"2tokens = []3current_token = ""4
5for char in s:6    if char == ",":7        digit_count = sum(1 for c in current_token if c.isdigit())8        tokens.append((current_token, digit_count))9        current_token = ""10    else:11        current_token += char12
13if current_token:14    digit_count = sum(1 for c in current_token if c.isdigit())15    tokens.append((current_token, digit_count))

After each token, you can process it right away rather than waiting until the loop is done. This is useful when you need to discard some tokens or count specific properties.

Common mistakes

The most common one is forgetting to append the last token after the loop ends. Nothing inside the loop runs once the string is exhausted. If the string does not end in a delimiter, whatever is left in current_token never makes it into tokens unless you check for it explicitly.

A second is appending empty tokens by accident. If two delimiters sit next to each other, current_token is empty at the moment you would append it. Guard the append with if current_token: unless the problem specifically wants empty tokens kept.

A third is checking for only one delimiter when the problem allows several. Writing char == ":" where the problem also accepts commas or spaces tokenizes incorrectly on any input that mixes them. Use char in "delimiters" instead of a single equality check whenever more than one delimiter character is valid.

Finally, resist the urge to modify the input string itself as you scan it. Strings in Python cannot be changed in place, so build the list of tokens and let the original string stay exactly as it was read.