Проблемы с пониманием того, что делать с выводом алгоритма маневровой станции

Я просматривал вики-страницу: http://en.wikipedia.org/wiki/Shunting-yard_algorithm

Я использовал пример кода для создания первой части, в основном я могу включить:

3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 в 3 4 2 * 1 5 − 2 3 ^ ^ / +

Но я не знаю, как потом использовать 3 4 2 * 1 5 − 2 3 ^ ^ / + для получения 3.00012207

И пример кода и объяснение на вики не имеют для меня никакого смысла.

Может кто-нибудь объяснить, как оценить 3 4 2 * 1 5 − 2 3 ^ ^ / + и дать ответ. Заранее спасибо. Мне не нужен пример кода, просто хорошее объяснение или разбивка примера.

Не то чтобы это имело значение, но я работаю с .net С#.


algorithm postfix-notation shunting-yard
person Patrick Lorio    schedule 01.12.2011    source источник

Ответы (4)


arrow_upward
9
arrow_downward

Цель алгоритма маневровой станции состоит в том, что его выходные данные представлены в обратной польской нотации, которую легко оценить:

  • создать стек для хранения значений
  • while there is reverse polish notation input left:
    • read an item of input
    • если это значение, поместите его в стек
    • в противном случае это операция; извлекать значения из стека, выполнять операцию над этими значениями, возвращать результат обратно
  • когда не осталось входных данных, если выражение было правильно сформировано, в стеке должно быть ровно одно значение; это оцениваемый результат.
person moonshadow    schedule 01.12.2011
comment
Стек — это правильная структура данных для достижения этой цели, какую коллекцию вы бы предложили использовать в Java (если вы ее знаете)? LinkedList или Deque? Я знаю, что в Java есть класс Stack‹E›, но я читал, что его нецелесообразно использовать из-за синхронизации. - person tonix; 19.06.2014

arrow_upward
8
arrow_downward

Обозначение после исправления — это то, как вы выполняете математику, скажем, в калькуляторе HP.

Сохраняйте стек, всякий раз, когда вы получаете число, добавляйте его наверх. Всякий раз, когда вы получаете оператор, потребляйте входные данные сверху, а затем добавляйте результат сверху

token stack
      *empty*
 3    3         //push numbers...
 4    3 4
 2    3 4 2
 *    3 8       //remove 4 and 2, add 4*2=8
 1    3 8 1
 5    3 8 1 5
 -    3 8 -4
 2    3 8 -4 2
 3    3 8 -4 2 3
 ^    3 8 -4 8
 ...    ...
person hugomg    schedule 01.12.2011

arrow_upward
2
arrow_downward

Обработайте элементы 3 4 2 * 1 5 − 2 3 ^ ^ / + слева направо следующим образом:

  1. Инициализировать стек для хранения чисел.
  2. Если элемент является числом, поместите его в стек.
  3. если элемент является оператором, удалите два верхних элемента из стека, примените оператор к этим двум элементам и поместите результат в стек.

Когда вы дойдете до конца, в стеке должен быть один элемент, который и будет результатом.

person Ted Hopp    schedule 01.12.2011

arrow_upward
2
arrow_downward

Вижу, я немного опаздываю на вечеринку.

Я увидел вопрос и пошел по касательной, написав пару задач для Rosetta Code. Так уж получилось, что эта задача может быть тем, что вам нужно. Он дает аннотированную таблицу того, что происходит при вычислении значения выражения RPN, токен за токеном.

Вот пример его вывода:

For RPN expression: '3 4 2 * 1 5 - 2 3 ^ ^ / +'

TOKEN           ACTION                 STACK      
3     Push num onto top of stack 3                
4     Push num onto top of stack 3 4              
2     Push num onto top of stack 3 4 2            
*     Apply op to top of stack   3 8              
1     Push num onto top of stack 3 8 1            
5     Push num onto top of stack 3 8 1 5          
-     Apply op to top of stack   3 8 -4           
2     Push num onto top of stack 3 8 -4 2         
3     Push num onto top of stack 3 8 -4 2 3       
^     Apply op to top of stack   3 8 -4 8         
^     Apply op to top of stack   3 8 65536        
/     Apply op to top of stack   3 0.0001220703125
+     Apply op to top of stack   3.0001220703125  

 The final output value is: '3.0001220703125'
person Paddy3118    schedule 03.12.2011