Group tagged words into noun phrases with a tag pattern, as NLTK's RegexpParser does.
What to build
A program that brackets the noun phrases of a tagged sentence.
Requirements
- The input is
word/TAGitems (tag after the last/). A noun phrase is an optional DET, then any number of ADJ, then one or more NOUN or PROPN. Phrases are found from left to right and never overlap; each is as long as possible. - Print the sentence's words with every noun phrase in square brackets, for example
[the old dog] chased [a ball], thennoun phrases: N.
Input
One line of tagged words.
Output
Two lines.
Constraints
At most 500 words.
Example
Input:
the/DET old/ADJ dog/NOUN chased/VERB a/DET big/ADJ red/ADJ ball/NOUN
Output:
[the old dog] chased [a big red ball]
noun phrases: 2
Why it works
Writing each tag as one letter turns the phrase pattern into a regular expression over a string, and the regex engine's leftmost, longest matching gives exactly the non-overlapping chunks.
Examples
Example 1 · Input
the/DET old/ADJ dog/NOUN chased/VERB a/DET big/ADJ red/ADJ ball/NOUN
Expected output
[the old dog] chased [a big red ball] noun phrases: 2
Example 2 · Input
Ada/PROPN Lovelace/PROPN wrote/VERB notes/NOUN
Expected output
[Ada Lovelace] wrote [notes] noun phrases: 2
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Map DET to D, ADJ to A, NOUN and PROPN to N and every other tag to x, then search the code string with `re.finditer(r"D?A*N+", code)`.
Hint 2
Each match's `start()` and `end()` are word positions, because there is one letter per word.
Solution
Show one correct solution (try it yourself first)
import re
items = [item.rsplit("/", 1) for item in input().split()]
letters = {"DET": "D", "ADJ": "A", "NOUN": "N", "PROPN": "N"}
code = "".join(letters.get(t, "x") for _, t in items)
out, last, count = [], 0, 0
for m in re.finditer(r"D?A*N+", code):
out += [w for w, _ in items[last:m.start()]]
out.append("[" + " ".join(w for w, _ in items[m.start():m.end()]) + "]")
last = m.end()
count += 1
out += [w for w, _ in items[last:]]
print(" ".join(out))
print("noun phrases:", count)