Resolve every use of a name to the declaration it refers to.
What to build
A program that resolves names in a block-structured program.
Requirements
- Lines are
{,},let NAMEoruse NAME. A declaration is visible from its line to the end of its block, including inner blocks; an inner declaration shadows an outer one. - For each use print
line K: NAME -> line D(D is the declaration it refers to) orline K: NAME is not declared. For a second declaration of a name in the same scope, printline K: NAME is already declared in this scopeand keep the first.
Input
Line 1: n. Then n lines; the braces are balanced.
Output
One line per use and per duplicate declaration, in order.
Constraints
n ≤ 100.
Example
Input:
7
let x
{
let x
use x
}
use x
use y
Output:
line 4: x -> line 3
line 6: x -> line 1
line 7: y is not declared
Why it works
A stack of scopes gives each use the nearest visible declaration, and popping a scope at } makes its names disappear.
Examples
Example 1 · Input
7
let x
{
let x
use x
}
use x
use y
Expected output
line 4: x -> line 3 line 6: x -> line 1 line 7: y is not declared
Example 2 · Input
5
let a
{
use a
let a
}
Expected output
line 3: a -> line 1
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Use a list of dictionaries: push one at `{`, pop it at `}`, and store each name's declaration line.
Hint 2
Search the scopes from the last one to the first, and stop at the first match.
Solution
Show one correct solution (try it yourself first)
scopes = [{}]
for k in range(1, int(input()) + 1):
parts = input().split()
if parts == ["{"]:
scopes.append({})
elif parts == ["}"]:
scopes.pop()
elif parts[0] == "let":
name = parts[1]
if name in scopes[-1]:
print(f"line {k}: {name} is already declared in this scope")
else:
scopes[-1][name] = k
else:
name = parts[1]
for scope in reversed(scopes):
if name in scope:
print(f"line {k}: {name} -> line {scope[name]}")
break
else:
print(f"line {k}: {name} is not declared")