import ast
uttryck = "17 - 120.9 * ( 12 + 12 * 312 ) - 8 / ( 3 + 1 )"
print(ast.dump(ast.parse(uttryck, "", "eval")))
Klicka kör. Om vi snyggar till utskriften ser det ut som nedan. Vad vi ser kallas abstrakt syntax träd (AST). När vi kör pythonkod, så parsar python först koden och bygger ett abstrakt syntax träd (AST). (Därefter skapas objektkod och därefter interpreteras objektkoden, men det är en senare historia.)
Expression(
body= BinOp(
left=BinOp(
left=Constant(value=17),
op=Sub(),
right=BinOp(
left=Constant(value=120.9),
op=Mult(),
right=BinOp(
left=Constant(value=12),
op=Add(),
right=BinOp(
left=Constant(value=12),
op=Mult(),
right=Constant(value=312))
)
)
),
op=Sub(),
right=BinOp(
left=Constant(value=8),
op=Div(),
right=BinOp(
left=Constant(value=3),
op=Add(),
right=Constant(value=1))
)
)
)
Vi kan vidare göra en graf av detta, närmare bestämt nedan abstrakta syntax träd (AST)
Ovan träd är AST -trädet för uttrycket
17 - 120.9 * ( 12 + 12 * 312 ) - 8 / ( 3 + 1 )
Prefix notation
- - 17 * 120.9 + 12 * 12 312 / 8 + 3 1
Jämför nu detta AST med prefix -uttrycket.
Okej, vi vänder nu på allt. Låt säga vi hade prefix -utrycket. Det är enkelt konvertera prefix -uttryck till just ett abstrakt syntax träd.
Vi går igenom prefix -uttrycket token för token.
prefix2ast algoritm
1. Om det är en siffra lägg på stacken.
2. Om är en operator, skapa en ny nod som får värdet av operatorn (value = operatorn). Pop:a samtidigt vänstervärdet, pop:a högervärdet. Lägg den nya nya noden på stacken.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def is_number(n):
try:
float(n)
except:
return False
return True
def construct_tree(prefix_expr):
stack = []
tokens = prefix_expr.split()[::-1]
for token in tokens:
if is_number(token):
stack.append(Node(token))
else:
node = Node(token)
node.left = stack.pop()
node.right = stack.pop()
stack.append(node)
return stack.pop()
def print_tree(node, level=0):
if node is not None:
print_tree(node.right, level + 1)
print(' ' * 4 * level + '->', node.value)
print_tree(node.left, level + 1)
prefix = '- - 17 * 120.9 + 12 * 12 312 / 8 + 3 1'
ast_tree = construct_tree(prefix)
print_tree(ast_tree)
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def is_number(n):
try:
float(n)
except:
return False
return True
def construct_tree(prefix_expr):
stack = []
tokens = prefix_expr.split()[::-1]
for token in tokens:
if is_number(token):
stack.append(Node(token))
else:
node = Node(token)
node.left = stack.pop()
node.right = stack.pop()
stack.append(node)
return stack.pop()
def print_tree(node, level=0):
if node is not None:
print_tree(node.right, level + 1)
print(' ' * 4 * level + '->', node.value)
print_tree(node.left, level + 1)
prefix = '- - 17 * 120.9 + 12 * 12 312 / 8 + 3 1'
ast_tree = construct_tree(prefix)
print_tree(ast_tree)
Evaluera ett ast träd