Разобрать стек в двоичное дерево?

Question

Я создаю программу, в задачу которой входит преобразование математического выражения, такого как (2+4)*(4/3), в двоичное дерево, а затем манипулирование им.

Во-первых, при разборе я превратил строку в два стека, операнды и операторы.Как я могу определить, каким должен быть корень, учитывая, что в моем примере выше дерево должно выглядеть так:

     *
    / \
   +   /
   /\  /\
  2 4  4 3

Обратите внимание, что корнем является *, который является самым внешним операндом.Но в моем стеке операндов это выглядит так:

/
*
+

И могут быть случаи, например (2+4+3)*4 или 2*((4+1)/3).

Как определить, какой операнд должен быть корнеммое двоичное дерево?

Answer 1

Преобразование вашего выражения инфикса в префиксную или постфиксную нотацию.Вы не можете получить правильный стек операторов без этого.

В постфиксной нотации выражение (2+4)*(4/3) будет выглядеть так:конец, который можно вставить в дерево в качестве его корня.Оценить выражение postfix гораздо проще для компьютера, поскольку группировка не требуется.

Answer 2

Вы не можете просто поместить операторы в ваш стек в том порядке, в котором они появляются в вашем выражении. Как только вы это сделаете, вы потеряете способность устранять неоднозначность, как вы определили.

Смотри, например, http://en.wikipedia.org/wiki/Shunting_yard_algorithm для алгоритма синтаксического анализа инфиксной записи.

Answer 3

Вы можете использовать стек для реализации дерева инфиксных и двоичных выражений. Эта ссылка имеет реализацию C ++:

Инфикс для синтаксического анализатора бинарного выражения, который использует два стека

один для операторов и другой для операндов, которые все являются производными от класса базового узла.