식 트리의 후위 순회가 주어졌다고 가정합니다. 주어진 후위 순회로부터 표현식 트리를 구축한 다음 표현식을 평가해야 합니다. 표현식 트리의 루트와 트리의 평가 값을 반환합니다.
따라서 입력이 다음과 같으면
그러면 출력은 -7이 됩니다.
트리의 입력으로 주어지는 후위 순서는 ['1', '2', '+', '3', '4', '+', '*']입니다. 식은 평가되면 (1 – 2) * (3 + 4)가 됩니다. 이는 -7과 같습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
왼쪽 =0오른쪽 =1
-
평가() 함수를 정의합니다. 이것은 뿌리를 내릴 것입니다
-
루트 값이 숫자 값이면
-
루트 값의 정수 표현을 반환
-
-
left_val :=평가(루트의 왼쪽)
-
right_val :=평가(루트의 오른쪽)
-
루트 값 ='+'인 경우
-
left_val + right_val 반환
-
-
그렇지 않으면 루트 값이 '-'일 때
-
return left_val - right_val
-
-
그렇지 않으면 root의 값이 '*'인 경우
-
return left_val * right_val
-
-
그렇지 않으면 root의 값이 '/'일 때
-
(left_val / right_val)
의 하한값 반환
-
-
-
buildTree() 함수를 정의합니다. 이것은 접미사가 필요합니다.
-
루트 :=null
-
스택 :=새 목록
-
접미사가 비어 있지 않은 동안 수행
-
curr :=접미사에서 마지막 요소 삭제
-
curr_node :=curr 값을 포함하는 새 노드
-
루트가 비어 있으면
-
루트 :=curr_node
-
-
스택이 비어 있지 않으면
-
부모 :=스택에서 마지막 요소 삭제
-
측면 :=부모
-
면이 LEFT와 같으면
-
부모의 왼쪽 :=curr_node
-
-
그렇지 않으면
-
부모의 오른쪽 :=curr_node
-
-
-
curr이 숫자 값이 아닌 경우
-
스택 끝에 튜플(curr_node, LEFT) 삽입
-
스택 끝에 tuple(curr_node, RIGHT) 삽입
-
-
-
-
루트 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
LEFT = 0 RIGHT = 1 class Node(): def __init__(root, val, left = None, right = None): root.val = val root.left = left root.right = right def evaluate(root): if(root.val.isnumeric()): return int(root.val) left_val = evaluate(root.left) right_val = evaluate(root.right) return ( ( root.val == '+' and left_val + right_val ) or ( root.val == '-' and left_val - right_val ) or ( root.val == '*' and left_val * right_val ) or ( root.val == '/' and left_val // right_val ) ) def buildTree(postfix): root = None stack = [] while(postfix): curr = postfix.pop() curr_node = Node(curr) if(not root): root = curr_node if(stack): parent, side = stack.pop() if(side == LEFT): parent.left = curr_node else: parent.right = curr_node if(not curr.isnumeric()): stack.append((curr_node, LEFT)) stack.append((curr_node, RIGHT)) return root root = buildTree(['1', '2', '+', '3', '4', '+', '*']) print(evaluate(root))
입력
['1', '2', '+', '3', '4', '+', '*']
출력
-7