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

Question

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

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

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

Evaluate("3 * 5")

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

Evaluate("2 + 15")

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

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

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

Answer 1

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

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

Вот пример того, как это можно сделать - рассмотрим пример «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. Если вы столкнетесь и операнд (число), вставьте его в операндstack
3. Как только вы нашли достаточно операндов для самого верхнего оператора (в большинстве случаев два), посмотрите на оператор и выполните эту операцию над двумя операндами.
4. Нажмите результат шага #3 на стек операндов.

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

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

Answer 2

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

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

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

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

например. очень простой пример с '+' и '*'

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

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

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

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

Answer 3

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

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

Answer 4

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

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