이진 표현 트리 만들기

Question

누군가 이진 표현 트리를 작성하는 방법을 설명 할 수 있습니까?

예를 들어, 문자열이 2*(1+(2*1)); 이진 표현 트리로 변환하는 방법이 있습니다.

* 
| \ 
| \ 
2 + 
    |\ 
    1 * 
     |\ 
     2 1 

Answer 1

접두사 또는 접미사 표기법으로 표현식을 변환하십시오. 거기에서 꽤 간단해야합니다. 알고리즘은 다음 wiki 링크에서 언급됩니다.

http://en.wikipedia.org/wiki/Polish_notation

http://en.wikipedia.org/wiki/Reverse_Polish_notation

Answer 2

에 당신이 필요합니다 :

1. 는
2. 이 문자열
3. 쓰기에서 토큰을 읽는 어휘 분석기 쓰기 언어를 설명하는 문법을 정의 토큰에서 나무를 만드는 파서

예를 들어,이 방법에 대해 살펴 : http://en.wikipedia.org/wiki/Recursive_descent_parser

다른 접미사 나 접두사

Answer 3

변환 중위가

후위 입력은 다음과 같습니다 AB +의 CDE + **

1. 심볼이 아닌 경우 첫 번째 문자를 고려한 다음 노드를 만듭니다. 스택에 추가합니다.
2. chara cter는 심볼이며 심볼 pop 요소가있는 노드를 만들고 심볼의 왼쪽과 오른쪽에 추가합니다.
3. 심볼 노드를 스택에 푸시합니다. 반복자까지
4. 반복 1, 2, 3은 더 이상 요소를

자바 구현이 없습니다

public Tree.TreeNode createExpressionTree(){ 
    Iterator<Character>itr = postOrder.iterator(); 
    Tree tree = new Tree(); 
    NodeStack nodeStack = new NodeStack(); 
    Tree.TreeNode node; 
    while (itr.hasNext()) { 
     Character c = itr.next(); 
     if(!isDigit(c)){ 
      node = tree.createNode(c); 
      node.right = nodeStack.pop(); 
      node.left = nodeStack.pop(); 
      nodeStack.push(node); 
     }else{ 
      node = tree.creteNode(c); 
      nodeStack.push(node); 
     } 
    } 
    node = nodeStack.pop(); 
    return node; 
} 

상세 정보 : http://en.wikipedia.org/wiki/Binary_expression_tree

그것은 두 단계로 나눌 수 있습니다

Answer 4

:

1. 각 토큰의 우선 순위 값을 계산하십시오. 예를 들어

   '+'1 'X'2 번호 : INF, '(',베이스 (10)를 추가 ')')베이스 10 빼기

2. 빌드 Cartesian tree에 기초 스택을 사용하여 우선 순위 (약 5 줄의 코드)

한 번의 스캔으로 처리 할 수 ​​있습니다.