Создание двоичного дерева выражений

Question

Может ли кто-нибудь объяснить, как построить двоичное дерево выражений.

Например, у меня есть строка 2*(1+(2*1)); Как преобразовать это в двоичное дерево выражений.

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

Answer 1

Преобразование выражения в префикс или постфиксное обозначение. Оттуда это должно быть довольно просто. Алгоритмы упоминаются в следующих вики-ссылках.

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

Преобразовать инфикс к постфикса или префиксом

Входной постфикса является: аб + CDE + **

1. Рассмотрим первый символ, если он не является символом, а затем создайте узел, чтобы добавить его в стек
2. Если chara cter - это символ, затем создайте узел с символами поп-элементов и добавьте влево и вправо от символа
3. Нажмите узел символа в стек.
4. Repeat 1, 2 и 3 до итератора больше не имеет элементы реализации

Java

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, 'х': 2, номер: инф, '(': добавить 10 к основанию, ')': вычесть 10 из базы)

2. Построить Cartesian tree на основе приоритет с использованием стека (приблизительно 5 строк кода)

Вы можете сделать это одним сканированием.