Выражение оценки

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

Evaluate("2 + (3 * 5)")

перезвоню себе так:

Evaluate("3 * 5")

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

Evaluate("2 + 15")

Хорошо, возвращаемое значение равно 17, как и ожидалось. Но если я позвоню Evaluate("2 + 3 * 5") результат:

Evaluate("2 + 3 * 5")
Evaluate("5 * 5")

Что явно не так.
В основном я решаю операции слева направо. Как я могу выбрать операции, которые должны быть выполнены в первую очередь? Я думал добавить пару скобок вокруг каждой операции, но это выглядит не так хорошо.
Итак, мне нужно сначала проанализировать все выражение или есть другой способ?

Источник

4 ответа

Решение

Найдите свой оператор с наивысшим приоритетом и сделайте это сначала, а затем продолжайте. Поэтому, если у вас есть только + и *, найдите экземпляры * и замените подстроку aaaa * bbbb значением aaaa * bbbb. Если таких экземпляров не осталось, работайте на +.

Если порядок внутри данного оператора имеет значение (например, если вы включаете ^), вам придется решить, с чего начать с этими операторами.

Источник

Что может помочь, так это использование польской нотации: http://en.wikipedia.org/wiki/Polish_notation. Это обозначение позволяет вам не требовать скобки и помогает вам с порядком операций.

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

Вот пример того, как это можно сделать - давайте возьмем ваш пример "2 + 3 * 5":

2 + 3 * 5
b = 3 * 5
    -convert b-
b = * 3 5
2 + b
    -convert expression-
+ 2 b
    -expand b-
+ 2 * 3 5

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

Большим преимуществом этого преобразования является то, что можно оценить модифицированное выражение слева направо. Алгоритм работает примерно так:

Поддерживайте два стека - один для операторов и один для операндов. Оценка слева направо:

  1. Если вы столкнетесь с оператором, поместите его в стек оператора
  2. Если вы столкнетесь и операнд (число) поместите его в стек операндов
  3. Как только вы нашли достаточно операндов для самого верхнего оператора (два в большинстве случаев), посмотрите на оператора и выполните эту операцию над двумя операндами.
  4. Вставьте результат шага № 3 в стек операндов.

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

Надеюсь, что это помогает и удачи:)

Источник

Вот хорошая статья, показывающая, как это сделать, используя Antlr с.net.

http://www.codeproject.com/KB/recipes/sota_expression_evaluator.aspx

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

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

Например, очень простой пример с "+" и "*"

additiveExpression: multiplicativeExpression '+' multiplicativeExpression
multiplicativeExpression: number '*' number

Ваш рукописный анализатор рекурсивного спуска начинается с верхнего правила и работает вниз.

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

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

Источник

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

2 + 3 * 5 на самом деле 2 + (3 * 5).

Источник
Другие вопросы по тегам