Python construye un árbol de expresión a partir del ejemplo de código de prefijo

Ejemplo: Python construye un árbol de expresión a partir del prefijo

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

---

---

Utiliza Nuestro Buscador