Математическое выражение обычно выражается в инфиксной нотации. В целях оценки мы можем изменить его на постфиксную (обратную шлифовку) нотацию (используя такие алгоритмы, как Shunting-Yard), а затем оценить постфиксную нотацию, используя стек.
Я узнал, что калькуляторы используют эту технику, но используют ли ее современные компиляторы для вычисления арифметических выражений? Достаточно ли он эффективен или используются другие методы (или алгоритмы)?
Чтобы ответить на этот вопрос, давайте сосредоточимся на концепциях, которые вы упомянули, infix notation, Shunting-Yard и evaluation, а затем свяжем их с компиляцией.
Для начала нам нужно понять, обычно как компьютер обрабатывает выражение. Выражение преобразуется в абстрактное синтаксическое дерево (AST), которое затем используется для создания кода. Процесс преобразования дерева в код различается, но обход AST такой же, как и вычисление выражения.
АСТ для 1+2:
+
/ \
1 2
Постфикс: 1 2 +
Это оценивается путем посещения левой ветви, 1,
и посещения правой ветви, 2,
, а затем применения оператора + к двум операндам.
АСТ для 1*2+3^4:
+
/ \
^ *
/ \ / \
3 4 1 2
Постфикс: 3 4 ^ 1 2 * +
Это оценивается путем посещения левой ветви 3^4,
затем посещения ее левой ветви 3,
затем посещения ее правой ветви 4,
затем посещения оператора ^, оценки 3^4 и удержания его в качестве нового левого ветвь для `+', т.е. 81
затем посещаем правую ветвь 1*2,
затем посещаем ее левую ветвь 1,
затем посещаем ее правую ветвь 2,
затем посещаем оператор * и оцениваем 1*2 и сохраняем его как новую правую ветвь для ` +', т.е. 2
затем посещаем оператора + и оцениваем 81+2 и возвращаем его как результат 83
Теперь инфиксная нотация — это синтаксический сахар, чтобы сделать использование выражений более понятным для людей. Чтобы помочь преобразовать инфиксную нотацию в AST, алгоритм преобразования должен знать приоритет и ассоциативность операторов. Алгоритм также использует стек, который является одним из основных ключей к алгоритму Shunting-Dard. Все известные мне средства преобразования инфикса в стратегию оценки так или иначе используют стек.
Хотя компилятор не выполняет явное вычисление выражения, как это может быть сделано с помощью приложения-калькулятора, компилятор преобразует обход дерева для вычисления в код, который будет выполнять предварительное вычисление.
Примечание. Поскольку я не знаю каждого компилятора для каждого языка, я могу дать вам ответ только на основе общих понятий. Не существует правила, требующего их соблюдения, и я не удивлюсь, если некоторые компиляторы пропустят AST и перейдут от входного кода к скомпилированному коду без использования AST.
Кроме того, поскольку вы упомянули компилятор, я говорил только о скомпилированном коде и не касался языков сценариев.
Теперь вернемся к вашим вопросам:
Используют ли современные компиляторы это для вычисления арифметических выражений?
Я бы не использовал конкретно алгоритм Shunting-Dard, а использовал концепцию использования стека, которая является одной из ключевых концепций алгоритма, который я буду использовать. Вы можете выбрать для себя, является ли использование понятий алгоритма таким же, как использование алгоритма.
Достаточно ли он эффективен или используются другие методы (или алгоритмы)?
Надеюсь, теперь вы знаете ответ на этот вопрос. Важен не алгоритм Shunting-Yard, а концепция использования стека для перевода инфиксной нотации, которая используется в компиляторах. Помните, что скомпилированные языки обычно делают больше, чем оценивают выражения, они работают с типами, обрабатывают условные выражения, сохраняют значения и создают более высокие типы, такие как методы/функции, классы и модули.
