Type-check whole expressions with variables, operators and conditionals.
What to build
A program that prints the type of each expression tree, or its first type error.
Requirements
- Literals: whole numbers (int), "strings" (str), true and false (bool). Variables take their declared types. Rules:
+ - *int, int → int;+str, str → str;<int, int → bool;==two of the same type → bool;and,orbool, bool → bool;notbool → bool;(if c a b)needs c bool and a, b of the same type, and has that type. - Errors, checking children left to right:
error: NAME is not declared,error: OP cannot take T1 and T2(fornot, justT),error: if needs a bool condition, not T,error: if branches differ: T1 and T2.
Input
Line 1: d. Then d lines name type. Then a line with m, then m expression trees in prefix form.
Output
m lines.
Constraints
d, m ≤ 20; strings contain no spaces or brackets.
Example
Input:
2
x int
ok bool
3
(+ x 1)
(and ok (< x 10))
(+ x "a")
Output:
int
bool
error: + cannot take int and str
Why it works
Each node's type follows from its children's types and one rule, so a single recursive walk types the whole tree or finds the first mistake.
Examples
Example 1 · Input
2 x int ok bool 3 (+ x 1) (and ok (< x 10)) (+ x "a")
Expected output
int bool error: + cannot take int and str
Example 2 · Input
1 s str 2 (if (== s "hi") 1 0) (if s 1 0)
Expected output
int error: if needs a bool condition, not str
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Read each tree recursively, check the children first, then apply the rule for the operator.
Hint 2
Raise an exception with the message at the first error and catch it once per expression.
Solution
Show one correct solution (try it yourself first)
import re
RULES = {
("+", "int", "int"): "int",
("-", "int", "int"): "int",
("*", "int", "int"): "int",
("+", "str", "str"): "str",
("<", "int", "int"): "bool",
("and", "bool", "bool"): "bool",
("or", "bool", "bool"): "bool",
("not", "bool"): "bool",
}
env = dict(input().split() for _ in range(int(input())))
class TypeCheckError(Exception):
pass
def read(text):
tokens = re.findall(r'\(|\)|"[^"]*"|[^\s()]+', text)
def node():
token = tokens.pop(0)
if token != "(":
return token
items = []
while tokens[0] != ")":
items.append(node())
tokens.pop(0)
return items
return node()
def check(node):
if isinstance(node, str):
if node.isdigit():
return "int"
if node.startswith('"'):
return "str"
if node in ("true", "false"):
return "bool"
if node in env:
return env[node]
raise TypeCheckError(f"{node} is not declared")
op, *args = node
types = [check(arg) for arg in args]
if op == "if":
if types[0] != "bool":
raise TypeCheckError(f"if needs a bool condition, not {types[0]}")
if types[1] != types[2]:
raise TypeCheckError(f"if branches differ: {types[1]} and {types[2]}")
return types[1]
if op == "==" and types[0] == types[1]:
return "bool"
key = (op, *types)
if key not in RULES:
raise TypeCheckError(f"{op} cannot take {' and '.join(types)}")
return RULES[key]
for _ in range(int(input())):
try:
print(check(read(input())))
except TypeCheckError as error:
print(f"error: {error}")