Xây dựng cây biểu thức nhị phân

Question

Ai đó có thể giải thích cách xây dựng một cây biểu thức nhị phân.

Ví dụ: Tôi có một chuỗi 2*(1+(2*1)); Cách chuyển đổi thành cây biểu thức nhị phân.

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

Answer 1

Chuyển đổi biểu thức sang tiền tố hoặc ký hiệu postfix. Từ đó nó phải khá đơn giản. Các thuật toán được đề cập trong các liên kết wiki sau đây.

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

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

Answer 2

bạn sẽ cần phải:

1. định nghĩa một ngữ pháp mô tả ngôn ngữ của bạn
2. viết một phân tích từ vựng mà đọc các thẻ từ chuỗi của bạn
3. ghi một trình phân tích cú pháp tạo một cây từ các mã thông báo

ví dụ, hãy nhìn vào cách tiếp cận này: http://en.wikipedia.org/wiki/Recursive_descent_parser

có những người khác

Answer 3

Chuyển đổi ghi vào để postfix hoặc tiền tố

Các đầu vào postfix là: ab + CDE + **

1. Hãy xem xét ký tự đầu tiên nếu nó không phải là biểu tượng, sau đó tạo nút thêm ký tự đó vào ngăn xếp
2. Nếu chara cter là biểu tượng, sau đó tạo nút với các phần tử pop biểu tượng và thêm vào bên trái và bên phải của biểu tượng
3. Nút biểu tượng đẩy vào ngăn xếp.
4. Lặp lại 1, 2 và 3 cho đến iterator không có nhiều yếu tố

Java thực hiện

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; 
} 

Thông tin thêm: http://en.wikipedia.org/wiki/Binary_expression_tree

Answer 4

Nó có thể được chia thành hai bước:

1. Tính giá trị ưu tiên cho mỗi mã thông báo.

   Ví dụ: '+': 1, 'x': 2, số: inf, '(': thêm 10 đến cơ sở, ')': trừ 10 từ cơ sở)

2. Build Cartesian tree dựa trên mức độ ưu tiên bằng cách sử dụng ngăn xếp (khoảng 5 dòng mã)

Bạn có thể thực hiện nó trong một lần quét.