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

Question

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

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

Answer 1

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

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

АСТ за 1 + 2:

   + 
  / \ 
 1   2

Postfix: 1 2 +

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

AST для 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

Теперь инфиксная нотация - это синтаксический сахар, облегчающий чтение выражений для людей. Чтобы помочь преобразовать инфиксную нотацию в AST, алгоритм преобразования должен знать приоритет и ассоциативность операторов. Алгоритм также использует стек, который является одним из основных ключей алгоритма Shunting-Yard. Каждое известное мне средство преобразования инфикса в оценочную стратегию каким-то образом использует стек.

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

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

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

Теперь вернемся к вашим вопросам:

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

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

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

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