Последовательный обход формулы

Question

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

Для данной формулы x y z + a b - c */-

Я придумал

    - 
       / \ 
       * /(divide) 
      /\ /\ 
       x + - c 
       /\ /\ 
       y z a b 

По большей части, это, кажется, соответствует, за исключением * в левом поддереве является джокером в Палуба. В обходном порядке по порядку последний символ является верхним узлом дерева, все остальное ветвится вниз. Теперь я беру операторы/и *, чтобы они означали, что они должны находиться на противоположных узлах. Однако при пересечении дерева все подходит, кроме *, так как левое поддерево должно работать до узла до корня, а затем переключиться на правое поддерево.

Подсказка в правильном направлении оценивается.

Answer 1

Перейти в порядке. Во-первых, выписывать весь стек снова:

х у г + а Ь - с */-

Теперь, начиная с левой, обратите внимание на первый оператор. Замените это и предыдущие два операнда, прямо в стеке, с немногими упорядоченными:

х (у + г) абы - с */-

Переходите к следующему оператору:

х (у + г) (а - б) с */-

Тогда следующий:

х (у + Z) ((а - Ь) * с)/-

x ((y + z)/((a - b) * c)) -

х - ((у + г)/((а - Ь) * с))

Теперь, чтобы сделать это дерево, просто начать в середине (которые вы уже знаете, как это последний элемент в исходном стеке) и вывешивать из него подвыражения в скобках, вне дома.

Answer 2

На самом деле проще написать программу, которая анализирует выражение пост-порядка, чем одно, которое анализирует его в порядке, потому что вам не нужно проверять приоритеты операций.

Попробуйте сделать следующее: создайте стек и добавьте к нему операнды, как вы их найдете (слева направо). Когда вы найдете операцию, извлеките количество операндов, которые она ожидает из стека, и верните небольшое дерево. Когда вы закончите, у вас будет только один результат в стеке: окончательный график.

Ex:

x y z + -> x + 
      /\ 
       y z