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

Question

Математическое выражение обычно выражается в нотации infix. Для целей оценки мы можем изменить его на постфиксную (обратную польский) нотацию (используя алгоритмы, такие как Shunting-Yard), а затем оценить постфиксную нотацию с использованием стека.

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

Answer 1

Чтобы ответить на этот вопрос, давайте сосредоточимся на концепциях, которые вы упомянули, infix notation, Shunting-Yard и evaluation, а затем связать их с компиляцией.

Для начала нам необходимо понять, как компьютер обрабатывает выражение. Выражение преобразуется в значение abstract syntax tree (AST), которое затем используется для создания кода. Процесс преобразования дерева в код меняется, но прогулка по АСТ такая же, как и оценка выражения.

АСТ для 1 + 2:

+ 
/\ 
1 2 

Postfix: 1 2 +

Это оценивается посещение левой ветви, 1,
Визитной правая ветвь, 2,
и затем применяя оператор, +, двум операндам.

АСТ 1 * 2 + 3^4:

 + 
/ \ 
^ * 
/\ /\ 
3 4 1 2 

Postfix: 3 4^1 2 * +

Это оценивается посещения левой ветви 3^4,
затем посетить его левой ветви 3,
затем посетите нужный филиал 4,
затем посещение оператора, ^, и оценки 3^4 и постановив, что в качестве нового левой ветви для `+», то есть 81

затем посетить правую ветвь 1*2,
затем посетить его левую ветвь 1,
затем посетить это правая ветвь 2,
затем посетить оператор, *, и оценки 1*2 и постановив, что в качестве нового правой ветви для `+», то есть 2

затем посетить оператор, +, и оценки 81+2 и возвращение в результате 83

Теперь инфикс обозначения syntactic sugar сделать с помощью выражения легче читать для людей. Чтобы помочь преобразовать инфикс-нотацию в AST, алгоритм преобразования должен знать операторы precedence и associativity. Алгоритм также использует стек, который является одним из основных ключей алгоритма Шунтин-Ярда.Каждое средство, которое я знаю для преобразования infix в стратегию оценки, использует стек каким-то образом.

В то время как компилятор явно не оценивает выражение, которое может быть выполнено с помощью приложения калькулятора, компилятор преобразует хождение по дереву для оценки в код, который будет преформировать оценку.

Примечание: Поскольку я не знаю каждого компилятора для каждого языка, я могу дать вам ответ на основе общих понятий. Нет правила, которое требует, чтобы это соблюдалось, и я не удивлюсь, если некоторые компиляторы пропустит AST и перейдут от кода ввода к скомпилированному коду без использования AST.

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

Теперь, чтобы вернуться на свои вопросы:

Использует ли это сегодняшние современные компиляторы для арифметического выражения оценки?

Я бы специально не использовал алгоритм Шунтин-Ярда, а понятия использования стека, который является одним из ключевых понятий алгоритма, который я буду использовать. Вы можете выбрать для себя, если использование понятий алгоритма такое же, как с использованием алгоритма.

Действительно ли это достаточно эффективно или другие методы (или алгоритмы) являются ?

Надеюсь, к настоящему времени вы знаете ответ на этот вопрос. Важным является не алгоритм Шунтин-Ярда, а концепция использования стека для перевода инфиксной нотации, которая важна, и это то, что используется с компиляторами. Помните, что скомпилированные языки обычно делают больше, чем оценивают выражения, они работают с типами, выражают условное выражение процесса, сохраняют значения и создают более высокие типы, такие как методы/функции, классы и модули.