표현식 트리는 리프 노드에 연산할 값이 있고 내부 노드에는 리프 노드가 수행될 연산자가 포함되어 있습니다.
예:4 + ((7 + 9) * 2) -
와 같은 표현식 트리가 있습니다.
이 문제를 해결하기 위한 접근 방식
주어진 표현식에 대한 표현식 트리를 구성하기 위해 일반적으로 스택 데이터 구조를 사용합니다. 처음에 우리는 주어진 접미사 표현식을 반복하고 아래와 같이 단계를 따릅니다 -
- 주어진 표현식에서 피연산자를 얻으면 스택에 푸시합니다. 표현 나무의 루트가 됩니다.
- 연산자가 표현식에서 두 개의 값을 얻으면 표현식 트리를 자식으로 추가하고 현재 노드에 푸시합니다.
- 주어진 표현이 완성되지 않을 때까지 1단계와 2단계를 반복합니다.
예시
class stack: def __init__(self): self.arr = [] def push(self, data): self.arr.append(data) def pop(self): try: return self.arr.pop(-1) except: pass def top(self): try: return self.arr[-1] except: pass def size(self): return len(self.arr) # node class for expression tree class node: def __init__(self, data): self.data = data self.left = None self.right = None # expression tree class class exp_tree: def __init__(self, postfix_exp): self.exp = postfix_exp self.root = None self.createTree(self.exp) def isOperator(self, char): optr = [" ", "-", "*", "/", "^"] if char in optr: # if given char is operator return True # then return true return False # else return false def createTree(self, exp): s = stack() # store those operator node whose any child node is NULL self.root = node(exp[-1]) # last character of postfix expression is always an operator s.push(self.root) # travel on rest of the postfix expression for i in "".join(reversed(exp[:-1])): curr_node = s.top() if not curr_node.right: # if right node of current node is NULL temp = node(i) curr_node.right = temp if self.isOperator(i): s.push(temp) else: # if left node of current node is NULL temp = node(i) curr_node.left = temp # if no child node of current node is NULL s.pop() # pop current from stack if self.isOperator(i): s.push(temp) def inorder(self, head): # inorder traversal of expression tree # inorder traversal = > left, root, right if head.left: self.inorder(head.left) print(head.data, end=" ") if head.right: self.inorder(head.right) def infixExp(self): # inorder traversal of expression tree give infix expression self.inorder(self.root) print() if __name__ == "__main__": postfixExp = "ab ef*g*-" et = exp_tree(postfixExp) et.infixExp()
위의 코드를 실행하면 다음과 같이 출력이 생성됩니다.
출력
(a + b - e * f * g)
설명:
주어진 표현식에서 트리를 구성하면 피연산자가 노드의 루트가 되고 나머지 숫자가 표현식 트리의 자식 노드가 되도록 출력이 생성됩니다.