Обращение по формуле после заказа - PullRequest
Новая
       6

Обращение по формуле после заказа

2 голосов
/ 14 октября 2010

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

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

Я придумал 

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

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

Ценность в правильном направлении приветствуется.

Ответы [ 2 ]

3 голосов
/ 14 октября 2010

Перейти в порядок. Сначала снова запишите весь стек:

x y z + a b - c * / -

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

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

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

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

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

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

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

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

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

0 голосов
/ 14 октября 2010

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

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

Ex: 

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