Построить двоичное дерево выражений

Question

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

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

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

Answer 1

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

Ввод постфикса: ab + cde + **

1. Рассмотрим первый символ, если он не является символом, затем создайте узел и добавьте его в стек
2. Если символ является символом, создайте узел с поп-элементами символа и добавьте слева и справа от символа
3. Вставьте узел символа в стек.
4. Повторите 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 2

вам нужно будет:

1. определить грамматику, которая описывает ваш язык
2. написать лексический анализатор, который считывает токены из вашей строки
3. написать парсер, который строит дерево из токенов

например, взгляните на этот подход: http://en.wikipedia.org/wiki/Recursive_descent_parser

есть другие

Answer 3

Его можно разделить на два этапа:

1. Рассчитать значение приоритета для каждого токена.

   Например: '+': 1, 'x': 2, число: inf, '(': добавить 10 в базу, ')': вычесть 10 из базы)

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

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

Answer 4

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

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

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