Мы можем значительно упростить программу, написав чистую функцию. Нумерованные комментарии здесь соответствуют номерам исходного кода в программе ниже.
- Если нет операции,
op, мы достигли базового варианта. Если предоставленный аргумент arg является списком, преобразуйте его в выражение или просто верните arg. - . По индукции является операцией,
op. Если предоставленный arg является списком, мы также должны рекурсивно преобразовать его. Вернуть выражение из 3-х частей с expr(*arg), op и рекурсивным результатом expr(*more) - По индукции есть операция, и поставляемое
arg равно , а не список. Вернуть выражение из 3 частей с arg, op и рекурсивным результатом expr(*more)
tree = \
[['B31','+','W311','*',['B21','+','W211','*',['B11','+','W111','*','x'],'+','W221','*',['B12','+','W121','*','x']],'+','W312','*',['B22','+','W212','*',['B11','+','W111','*','x'],'+','W222','*',['B12','+','W121','*','x']]]]
def expr(arg, op = None, *more):
if not op:
return expr(*arg) if isinstance(arg, list) else arg #1
elif isinstance(arg, list):
return [ expr(*arg), op, expr(*more) ] #2
else:
return [ arg, op, expr(*more) ] #3
print(expr(tree))
# ['B31', '+', ['W311', '*', [['B21', '+', ['W211', '*', [['B11', '+', ['W111', '*', 'x']], '+', ['W221', '*', ['B12', '+', ['W121', '*', 'x']]]]]], '+', ['W312', '*', ['B22', '+', ['W212', '*', [['B11', '+', ['W111', '*', 'x']], '+', ['W222', '*', ['B12', '+', ['W121', '*', 'x']]]]]]]]]]
Может быть, мы сможем немного лучше проверить вывод, если преобразуем выражение в строку -
def expr_to_str(expr1, op, expr2):
return \
f"({expr_to_str(*expr1) if isinstance(expr1, list) else expr1} {op} {expr_to_str(*expr2) if isinstance(expr2, list) else expr2})"
print(expr_to_str(*expr(tree)))
# (B31 + (W311 * ((B21 + (W211 * ((B11 + (W111 * x)) + (W221 * (B12 + (W121 * x)))))) + (W312 * (B22 + (W212 * ((B11 + (W111 * x)) + (W222 * (B12 + (W121 * x))))))))))
Вот еще один способ использования class -
class expr:
def __init__(self, x, op = None, *y):
self.op = op
self.x = expr(*x) if isinstance(x, list) else x
self.y = expr(*y) if y else y
def __str__(self):
if not self.op:
return f"{self.x}"
else:
return f"({self.x} {self.op} {self.y})"
print(expr(tree))
# (B31 + (W311 * ((B21 + (W211 * ((B11 + (W111 * x)) + (W221 * (B12 + (W121 * x)))))) + (W312 * (B22 + (W212 * ((B11 + (W111 * x)) + (W222 * (B12 + (W121 * x))))))))))
varaidi c поддержка
В комментарии вы спрашиваете, может ли expr поддерживать 3-элементные результаты и 2-элементные результаты. Вот одна из таких гибких реализаций -
В конструкторе __init__ мы делаем простой анализ случая -
- Если входные данные
a - это список, а список меньше чем 4 элементов, нам не нужно ничего ломать. Просто отобразите expr на каждый элемент a. - По индукции вход
a представляет собой список не менее 4 элементов, поэтому нам нужно разбить его на более мелкие выражения , Создайте выражение первого элемента expr(a[0]), второго элемента expr(a[1]) и рекурсивный результат всех оставшихся элементов expr(a[2::]) - . По индукции входное значение
a равно . не список, ie это один элемент. Установите для данных выражения одноэлементное значение [ a ]
В методе __str__ мы проводим аналогичный анализ для преобразования data нашего выражения в строку -
- Если
self.data пусто, вернуть пустую строку, "" - По индукции
self.data является не пустым. Если оно меньше 2 элементов (синглтон), вернуть результат синглтона: f"{self.data[0]}" - По индукции
self.data равен как минимум 2 или более элементов. вернуть (...) -замкнутую строку, где каждая часть рекурсивно преобразуется в str и соединяется с пробелом, " "
class expr:
def __init__(self, a):
if isinstance(a, list):
if len(a) < 4:
self.data = [ expr(x) for x in a ] #1
else:
self.data = [ expr(a[0]), expr(a[1]), expr(a[2::]) ] #2
else:
self.data = [ a ] #3
def __str__(self):
if not self.data:
return "" #1 empty
elif len(self.data) < 2:
return f"{self.data[0]}" #2 singleton
else:
return "(" + " ".join(str(x) for x in self.data) + ")" #3 variadic
print(expr(tree))
# (B31 + (W311 * ((B21 + (W211 * ((B11 + (W111 * x)) + (W221 * (B12 + (W121 * x)))))) + (W312 * (B22 + (W212 * ((B11 + (W111 * x)) + (W222 * (B12 + (W121 * x))))))))))
print(expr([[ "¬", ["a", "+", "b"]], "and", [["length", "x"], ">", 0]]))
# ((¬ (a + b)) and ((length x) > 0))
, разбивая ее
Разобрав сложную проблему на более мелкие части, легче решить подзадачи, что дает нам больше гибкости и контроля. Что бы это ни стоило, эта техника не использует механизмы Python, определенные c OOP. Это обычные, четко определенные, чистые функции -
def unit(): return ('unit',)
def nullary(op): return ('nullary', op)
def unary(op, a): return ('unary', op, a)
def binary(op, a, b): return ('binary', op, a, b)
Теперь, используя анализ плоского регистра, как мы делали ранее, мы реализуем наш конструктор рекурсивных выражений expr -
- , если вход
a не является списком, это одно значение. построить nullary выражение с a - По индукции вход представляет собой список. Если список пуст, создайте пустой результат, выражение
unit. - По индукции ввод не пустой список. Если он содержит ровно один элемент, создайте выражение
nullary с единственным элементом, expr(a[0]) - По индукции вход содержит как минимум два элемента. Если на входе ровно два элемента, создайте выражение
unary с expr(a[0]) и expr(a[1]) - . По индукции вход содержит как минимум три элемента. Если оператор ввода
is_infix position, преобразовать в префикс позиции. Создайте выражение binary с expr(a[0]) и expr(a[1]) в поменяном положении, и рекурсивный результат expr(a[2::]) - По индукции вход содержит как минимум три элемента, как , а не в инфиксной позиции. Построить обычное (префиксная позиция)
binary выражение expr(a[0]) и expr(a[1]) и рекурсивный результат expr(a[2::])
infix_ops = set([ '+', '-', '*', '/', '>', '<', 'and', 'or' ])
def is_infix (a):
return a[1] in infix_ops
def expr(a):
if not isinstance(a, list):
return nullary(a) #1
elif len(a) == 0:
return unit() #2
elif len(a) == 1:
return nullary(expr(a[0])) #3
elif len(a) == 2:
return unary(expr(a[0]), expr(a[1])) #4
elif is_infix(a):
return binary(expr(a[1]), expr(a[0]), expr(a[2::])) #5
else:
return binary(expr(a[0]), expr(a[1]), expr(a[2::])) #6
Теперь, чтобы увидеть результат -
tree2 = \
[[ "¬", ["a", "+", "b"]], "and", [["length", "x"], ">", 0]]
print(expr(tree2))
# ('binary', ('nullary', 'and'), ('unary', ('nullary', '¬'), ('binary', ('nullary', '+'), ('nullary', 'a'), ('nullary', ('nullary', 'b')))), ('nullary', ('binary', ('nullary', '>'), ('unary', ('nullary', 'length'), ('nullary', 'x')), ('nullary', ('nullary', 0)))))
Это просто одно из возможных представлений наших выражений. Поскольку мы реализовали наши выражения, используя tuple, Python может распечатать их, несмотря на то, что они многословны. В отличие от этого, вот как Python выбирает для представления объектов -
class foo: pass
f = foo()
print(f)
# <__main__.foo object at 0x7f2ba03bc8e0>
Здесь важно то, что наша структура данных выражений четко определена , и мы можем легко выполнить вычисления на ней или представить его другими способами -
def expr_to_str(m):
if not isinstance(m, tuple):
return str(m)
elif m[0] == "unit":
return ""
elif m[0] == "nullary":
return expr_to_str(m[1])
elif m[0] == "unary":
return f"({expr_to_str(m[1])} {expr_to_str(m[2])})"
elif m[0] == "binary":
return f"({expr_to_str(m[1])} {expr_to_str(m[2])} {expr_to_str(m[3])})"
else:
raise TypeError("invalid expression type", m[0])
print(expr_to_str(expr(tree2)))
# (and (¬ (+ a b)) (> (length x) 0))
вычисление выражения
Так что, если мы хотим оценить одно из наших выражений?
m = expr([3, "+", 2, "*", 5, "-", 1])
print(expr_to_str(m))
# (+ 3 (* 2 (- 5 1)))
print(eval_expr(m))
# 11
Вы в нескольких шагах от возможности писать eval_expr -
def eval_expr(m):
if not isinstance(m, tuple):
return m
elif m[0] == "unit":
return None
elif m[0] == "nullary":
return eval0(m[1])
elif m[0] == "unary":
return eval1(m[1], m[2])
elif m[0] == "binary":
return eval2(m[1], m[2], m[3])
else:
raise TypeError("invalid expression type", m[0])
Видите, сложные проблемы легче разбить на мелкие части. Теперь мы просто пишем eval0, eval1 и eval2 -
def eval0(op):
return eval_expr(op)
def eval1(op, a):
if op == expr("not"): # or op == expr("¬") ...
return not eval_expr(a)
elif op == expr("neg"): # or op == expr("~") ...
return -eval_expr(a)
# +, ++, --, etc...
else:
raise ValueError("invalid op", op)
def eval2(op, a, b):
if op == expr("+"):
return eval_expr(a) + eval_expr(b)
elif op == expr("-"):
return eval_expr(a) - eval_expr(b)
elif op == expr("*"):
return eval_expr(a) * eval_expr(b)
elif op == expr("/"):
return eval_expr(a) / eval_expr(b)
elif op == expr("and"):
return eval_expr(a) and eval_expr(b)
# >, <, or, xor, etc...
else:
raise ValueError("invalid op", op)
Давайте теперь посмотрим на смесь выражений -
print(eval_expr(expr([True, 'and', ['not', False]])))
# True
print(eval_expr(expr(['neg', [9, '*', 11]])))
# -99
print(eval_expr(expr(['stay', '+', 'inside'])))
# 'stayinside'
Вы даже можете определить свои собственные функции -
def eval1(op, a):
# ...
elif op == expr('scream'):
return eval_expr(a).upper() # make uppercase!
else:
raise ValueError("invalid op", op)
И использовать их в своих выражениях -
print(eval_expr(expr(["scream", ["stay", "+", "inside"]])))
# 'STAYINSIDE'