Python의 표현식 트리

AnExpression tree은 연산자가 내부 노드에 저장되고 피연산자가 리프인 외부 노드에 저장되는 이진 트리입니다. 식 트리를 사용하여 식을 평가하거나 infix 식을 prefix 또는 postfix 표기법으로 변환할 수 있습니다.

Infix: An expression where the operator is placed in between the operands. \
Ex: (A+B) * (C-D) \
Prefix: An expression where the operator is in the expression before the operands. \
Ex: *+AB-CD

표현식 트리 구조는 평가되는 연산자의 순서에 따라 다릅니다. 모든 내부 노드의 연산자는 각 왼쪽 및 오른쪽 하위 트리가 평가될 때 평가됩니다. 이러한 방식으로 하위 연산자가 하위 트리에 있을수록 우선적으로 평가됩니다. 루트 노드에는
평가할 연산자입니다.

구현:

표현식 트리를 구축하기 위해 스택 데이터 구조를 사용합니다. 후위 문자열 표현식이 전달될 때 각 문자를 반복하고 스택에 푸시할지 여부를 결정합니다.

1. 문자가 피연산자이면 스택에 푸시합니다.\
2. 캐릭터가 연산자인 경우 스택에서 두 요소를 팝하고 캐릭터의 왼쪽 및 오른쪽 노드 자식으로 만들고 시퀀스를 다시 스택으로 푸시합니다.

Note: Repeat the above steps until end of Prefix expression.

전:
접미사 식을 전달합시다“xy-”\
첫 번째 문자는 x 입니다. 스택에 푸시합니다. 다음 문자는 y 입니다. 또한 스택에 푸시합니다. 마지막 문자는 ‘-’ 연산자입니다. x 및 y를 팝하고 ‘-’의 왼쪽 및 오른쪽 자식으로 만듭니다. 따라서 중위 표현식으로 x - y로 끝납니다.

표현식 트리 프로그램:

# Python program for expression tree
# create a class for an expression tree node
class Expression_tree: 
    # Constructor to create a node
    def __init__(self , value):
        self.value = value
        self.left = None
        self.right = None
# function to check if 'c' is an operator
def isOperator(c):
    if (c == '+' or c == '-' or c == '*'
        or c == '/' or c == '^'):
        return True
    else:
        return False
# function to do inorder traversal
# Process all nodes of a tree by recursively processing the left subtree, the root, and finally the right subtree.
def inorder(t):
    if t is not None:
        inorder(t.left)
        print (t.value, end=" ")
        inorder(t.right)
# Returns root of constructed tree for given postfix expression
def constructTree(postfix):
    stack = []

    # Traverse through every character of input expression
    # Traverse - process every character in a string, from left end to right end. 
    for char in postfix :
       # if operand, push into stack
        if not isOperator(char):
            t = Expression_tree(char)
            stack.append(t)

        # Operator
        else:
            # Pop two top nodes
            t = Expression_tree(char)
            t1 = stack.pop()
            t2 = stack.pop()

            # make them left and right children
            t.right = t1
            t.left = t2

            # Add this subexpression to stack
            stack.append(t)

    # Only element  will be the root of expression tree
    t = stack.pop()

    return t
# Driver program to test above
postfix = "ab*ef-g+i-"
r = constructTree(postfix)
print ("Infix expression: ")
inorder(r)