Проблема понимание того, что делать с выводом алгоритма шунтирующего двора
-
27-10-2019 - |
Вопрос
Я смотрел на страницу вики: 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#.
Решение
Цель алгоритма шунтирующего двора состоит в том, что его вывод находится в Обратная польская нотация, что является простым для оценки:
- Создайте стек для сохранения значений
- В то время как вход вновь обратной польской записи остался:
- Прочитайте элемент ввода
- Если это значение, нажмите на стек
- В противном случае это операция; Значения POP из стека выполните операцию на этих значениях, нажмите результат обратно
- Когда ввода не осталось, если выражение было хорошо сформировано, в стеке должно быть точно одно значение; Это оцененный результат.
Другие советы
Обозначение после фиксирования-это то, как вы делаете математику, скажем, калькулятор 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
... ...
Обрабатывать элементы 3 4 2 * 1 5 − 2 3 ^ ^ / +
слева направо следующим образом:
- Инициализируйте стек для хранения чисел.
- Если элемент является числом, нажмите его на стек.
- Если элемент является оператором, удалите два верхних элемента из стека, примените оператор к этим двум элементам и нажмите результат на стек.
Когда вы дойдете до конца, стек должен иметь один элемент, который будет результатом.
Я вижу, я немного опоздал на вечеринку.
Я увидел этот вопрос и ушел на касательном написании нескольких задач по коду Розетты. Так получилось, что эта задача Может быть, то, что вы хотите. Он дает аннотт -таблицу того, что происходит при расчете значения выражения 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'