Трудно понять, что делать с выводом алгоритма маневрового двора - PullRequest
Новая
       56

Трудно понять, что делать с выводом алгоритма маневрового двора

5 голосов
/ 01 декабря 2011

Я смотрю на вики-странице: 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 C #.

Ответы [ 4 ]

9 голосов
/ 01 декабря 2011

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

  • создать стек для хранения значений
  • пока есть входные данные обратной польской записи:
    • прочитать элемент ввода
    • , если это значение, поместить его в стек
    • , иначе этоОперация;вытолкнуть значения из стека, выполнить операцию с этими значениями, вернуть результат обратно
  • , когда не осталось ввода, если выражение было правильно сформировано, должно быть ровно одно значение настек;это оценочный результат.
8 голосов
/ 01 декабря 2011

Запись после исправления - это то, как вы выполняете математику, скажем, в калькуляторе 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
 ...    ...
2 голосов
/ 03 декабря 2011

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

Я увидел вопрос и приступил к написанию нескольких заданий для 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'
2 голосов
/ 01 декабря 2011

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

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

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

...