Как написать оценщика для строки типа "(1 + 3 * (5/4)) и получить числовой результат

Это вопрос интервью я запутался в своем решении, я думаю, что мне нужны стеки, чтобы нажимать и вызывать эти операторы и операнды, но мне нужны два стека, один для оператора и один для операндов? или будет только один стек? Я думаю, нам нужны два стека, но есть ли способ решить один стек?

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

предпочтительнее сначала скобки, затем деление, многократное и последнее вычитание, а затем добавление

но как проверить, когда нужно поместить два операнда и выполнить необходимую операцию артрита?

Ответ 1

Взгляните на алгоритм маневрового двора.

Алгоритм маневрового двора представляет собой метод анализа математических уравнений, заданных в инфиксной нотации. Его можно использовать для создания выходных данных в обратной полях (RPN) или в виде абстрактного синтаксического дерева (AST). Алгоритм был изобретен Edsger Dijkstra и назван алгоритмом "шунтирующий двор", потому что его действие напоминает работу железнодорожного шунтирующего двора.

Ответ 2

Вы анализируете выражения с рекурсивно определенной структурой. Простой вариант - написать то, что называется рекурсивным достойным парсером:

См. http://en.wikipedia.org/wiki/Recursive_descent_parser

Это прямо, как только вы поймете, что подпрограмма "выражение разбора" на верхнем уровне должна вызывать себя для анализа его составных выражений, таких как EXPRESSION + EXPRESSION. В результате вы получите дерево узлов-операторов с деревьями выражений для операндов.

Вы также можете использовать такой инструмент, как Bison. Bison - "компилятор компилятора", который строит парсер, ориентированный на таблицу, для языка с учетом грамматики. (Bison - довольно старая школа: найдите "генератор парсера" для получения дополнительной информации.)

Ответ 3

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

Нет. Вероятно, они проверяют вашу способность обрабатывать такие вещи, как строки, проверяя их на такие вещи, как операторы {*,/, +, -}, левые и правые скобки, цифры и т.д. И видя, можете ли вы писать код/псевдокод для оценки выражения выражения они предоставили, а не всепоглощающее, все-танцевальное приложение.

С другой стороны, если вам нужен пример написания оценщика для строк типа "(1 + 3 * (5/4))", который возвращает числовой результат, вот несколько Примеры С++/Java.

Ответ 4

Я реализовал это в очень немногих строках кода, используя парсер boost spirit. Для меня это было очень хорошо в различных контекстах. (http://spirit.sourceforge.net/)

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

Ответ 5

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

в принципе, сделайте список порядков операторов, начните с скобок.

найдите большинство внутренних элементов: найдите первый) [закрыть], затем оттуда найдите назад для первого ([open].

теперь у вас есть внутренняя фраза без скобок. теперь ищите *, например, найдите номер позади и номер после, теперь замените эту фразу (например, 514 * 354,25), ответьте на нее.

это самый примитивный способ сделать это.. просто дал вам начало. для reset у вас, вероятно, нет выбора, используя мозг: P

(если вас интересует проект моего друга, просто скажите)

Ответ 6

Эта проблема называется рекурсивным парсером спуска. Могут быть другие формы канонического решения, я уверен, что есть - может быть, десятки правильных подходов. Дэвид Эк имеет рекурсивный синтаксический анализатор посылок, размещенный в Интернете с исходным кодом и объяснением. Google должен привлечь тысячи полезных ресурсов, и их также следует изучить в dmoz и вашей любимой поисковой системе.