Java: оценка постфиксного выражения

Это теоретическое:

Мне нужно вычислить выражение, которое я уже преобразовал из infix в postfix. Постфикс сохраняется внутри Queue, так как я хотел избежать работы с String. Таким образом, я знаю, где находятся различия между числами, и я могу получить к ним доступ в «правильном» порядке.

Это выглядит так:

// Original expression: 2+(3+1)-(5-3)^2*3-1
Queue: [2.0, 3.0, 1.0, +, +, 5.0, 3.0, -, 2.0, ^, 3.0, *, -,1.0, -]

Теперь я подумал, используя два стека:

  • исходный стек (который был предварительно заполнен содержимым очереди)
  • и целевой стек

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

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

Я спрашиваю себя сейчас:

  • Это хороший подход или лучше попытаться обнаружить все шаблоны типа NumberNumberOperator и обработать их за один раз?
  • И если второй вариант подходит, как это можно сделать?

java stack postfix-notation
person loxosceles    schedule 08.04.2014    source источник
comment
Звучит сложно. Почему не один стек для чисел. Если вы читаете число из своей очереди, поместите его в стек. Если вы читаете оператор, извлекаете его операнды из стека, выполняете операцию, возвращаете результат. Если операндов нет, то сгенерировать исключение.   -  person Solomon Slow    schedule 08.04.2014
comment
Хорошо, читая википедию, я понимаю. Удалил мой комментарий.   -  person Marco Acierno    schedule 08.04.2014

Ответы (1)


arrow_upward
1
arrow_downward

Нет. Вам нужен только один стек, и когда вы закончите, не останется ничего, с чего можно было бы «начать все сначала».

Когда вы удаляете число из очереди, поместите его: когда вы удаляете оператор из очереди, извлеките два значения, оцените оператор с этими двумя операндами и поместите результат. Когда вы дойдете до конца ввода, в стеке должно быть ровно одно значение — результат. В противном случае ввод был неправильно сформирован.

person user207421    schedule 08.04.2014