python build expression tree from prefix code example
Example: python build expression tree from prefix
class TreeNode:
"""Class for binary tree nodes."""
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def build_expression_tree_from_prefix(data):
"""
Returns the root of an expression tree built from 'Polish notation' (prefix).
### Parameters
- data (list) - a list of strings split from prefix expression.
"""
# Examples
# * * - 3 4 5 + 1 2
#
# *
# / \
# / \
# / \
# * +
# / \ / \
# - 5 1 2
# / \
# 3 4
# empty list check
if not data:
return
stack = []
# set primary root
root = TreeNode(data[0])
# add root to stack twice
stack.append(root) # * for final retrieval
stack.append(root) # for use
for val in data[1:]:
curr = TreeNode(val) # set current node
# attach current node to root as new branch
if not root.left:
root.left = curr
else:
root.right = curr
# set current node as new root
root = curr
# add operators to stack (See 'Polish notation')
if root.val in '+-*/':
stack.append(root)
else:
root = stack.pop()
return root # * last retrieved node is primary root