Как разобрать математические выражения в скобках

Question

Это не школьное задание или что-то еще, но я понимаю, что это в основном академический вопрос. Но я изо всех сил пытался разобрать «математический» текст и найти ответ.

Например - я могу понять, как анализировать '5 + 5' или '3 * 5' - но у меня не получается, когда я пытаюсь правильно объединить операции в цепочку.

(5 + 5) * 3

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

EDIT Спасибо за все быстрые ответы. Извините, я не справился лучше.

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

Второе. То, что я пытался сделать (возможно, неправильно), но сначала я считал «(» и «)» и оценивал самые глубокие предметы. В простых примерах это сработало; но мой код не красивый и более сложные вещи вылетает. Когда я «вычислил» самый низкий уровень, я модифицировал строку.

Итак ... (5 + 5) * 3

Превратится в 10 * 3

Который затем оценил бы 30

Но это было просто «неправильно».

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

Answer 1

Давным-давно, работая над простым графическим приложением, я использовал этот алгоритм (который достаточно прост для понимания и прекрасно работает для простых математических выражений, подобных этим), чтобы сначала превратить выражение в RPN и затем вычислили результат. RPN хорошо и быстро выполнялся для разных значений переменных.

Конечно, разбор языка - очень широкая тема, и есть много других способов сделать это (и готовые инструменты для этого тоже)

Answer 2

@ Восходящая звезда [Я надеялся добавить это как комментарий, но форматирование не удалось]

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

Пример:

((3 + 4 - 1) * 5 + 6 * -7) / 2

                  '/'
                /     \
              +        2
           /     \
         *         *
       /   \     /   \
      -     5   6     -7
    /   \
   +     1
 /   \
3     4

В приведенном выше случае сканер был запрограммирован на чтение «-», за которым следуют последовательность цифр как одно число, поэтому «-7» возвращается как компонент значения токена «число». '-' с последующим пробелом восстанавливается как знак "минус". Это делает синтаксический анализатор несколько легче для написания. Сбой в случае, когда вы хотите «- (x * y)», но вы можете легко изменить выражение на «0 - exp»

Answer 3

Вот простая грамматика (наивный операторный приоритет) для того, что вы хотите.

expression = 
    term
    | expression "+" term
    | expression "-" term .
term = 
    factor
    | term "*" factor
    | term "/" factor .
factor = 
    number
    | "(" expression ")" .

Когда вы обрабатываете «фактор», вы просто проверяете, является ли следующий токен числом или «(», если это «(», то вы снова анализируете «выражение», когда выражение возвращает вам проверку, если следующий токен - ")". Вы можете получить значение [рассчитано | прочитано] до родительского уровня с помощью параметров out или ref или построить дерево выражений.

Вот то же самое в EBNF:

expression = 
    term
    { "+" term | "-" term  } .

term = 
    factor
    { "*" factor | "/" factor }.

factor = 
    number
    | "(" expression ")" .

Answer 4

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

Одна из тех, что я написал несколько лет назад на Java, поддерживает арифметические операции, решение уравнений, дифференциальное исчисление, интегральное исчисление, базовую статистику, определение функции / формулы, построение графиков и т. Д.

Это называется ParserNG и его бесплатно.

Оценить выражение так же просто, как:

    MathExpression expr = new MathExpression("(34+32)-44/(8+9(3+2))-22"); 
    System.out.println("result: " + expr.solve());

    result: 43.16981132075472

Или используя переменные и вычисляя простые выражения:

 MathExpression expr = new MathExpression("r=3;P=2*pi*r;"); 
System.out.println("result: " + expr.getValue("P"));

Или используя функции:

MathExpression expr = new MathExpression("f(x)=39*sin(x^2)+x^3*cos(x);f(3)"); 
System.out.println("result: " + expr.solve());

result: -10.65717648378352

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

MathExpression expr = new MathExpression("f(x)=x^3*ln(x); diff(f,3,1)"); 
System.out.println("result: " + expr.solve());

 result: 38.66253179403897

Что отличает x^3 * ln(x) один раз при x = 3. Количество раз, которое вы можете различить, пока равно 1.

или для числовой интеграции:

MathExpression expr = new MathExpression("f(x)=2*x; intg(f,1,3)"); 
System.out.println("result: " + expr.solve());

result: 7.999999999998261... approx: 8

Этот парсер работает довольно быстро и обладает множеством других функций.

ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ: ParserNG создан мной.

Answer 5

Как уже было сказано во многих ответах, проблема в том, что вам нужно recursive parser с associativity rules, потому что вы можете получить такие выражения, как:

val = (2-(2+4+(3-2)))/(2+1)*(2-1)

и ваш парсер должен знать, что:

1. круглые выражения оцениваются изнутри
2. Деление имеет приоритет над умножением (сначала делите, а затем умножайте результат)
3. Умножение имеет приоритет над сложением / вычитанием

Как вы можете себе представить, написание (хорошего) парсера - это искусство. Хорошо, что есть несколько инструментов, называемых parser generators, которые позволяют вам легко определять грамматику вашего языка и правила синтаксического анализа . Вы можете проверить записи в Википедии на BNF , чтобы вы могли увидеть, как определяется грамматика.

Наконец, если вы делаете это для обучения, продолжайте. Если это для производственного кода, не изобретайте колесо и найдите существующую библиотеку, в противном случае вы рискуете потратить 1000 строк кода, чтобы добавить 2 + 2.

Answer 6

Выберите, Code Golf: средство оценки математических выражений (с учетом PEMDAS)

Answer 7

Когда я захотел проанализировать что-то, я решил использовать GOLD Parser:

• Автономная документация (для ее понимания не нужна книга)
• Различные движки времени выполнения, на разных языках программирования, включая тот, который я хотел.

Анализатор включает выборочных грамматик , включая, например, один для оператора prcedence.

---

Помимо GOLD есть и другие более известные парсеры, например ANTLR , который я не использовал.

Answer 8

В прошлом году я написал базовый математический оценщик по причинам, которые я не могу вспомнить. Это никоим образом не является «правильным» парсером в любом смысле слова, и… как и весь старый код, я не очень горжусь этим сейчас.

Но вы можете взглянуть и посмотреть, поможет ли это вам.

Вы запускаете некоторые входные тесты, запуская автономное Java-приложение

Answer 9

Вы когда-нибудь посещали занятия по формальным языкам в школе? Для эффективного анализа вам нужна грамматика.

РЕДАКТИРОВАТЬ: О дерьмо, Википедия говорит, что я не прав, но теперь я забыл правильное имя :( http://en.wikipedia.org/wiki/Formal_grammar

Answer 10

Всегда есть возможность использовать библиотеку математического анализатора, например mXparser . Вы можете:

1 - Проверить синтаксис выражения

import org.mariuszgromada.math.mxparser.*;
...
...
Expression e = new Expression("2+3-");
e.checkSyntax();
mXparser.consolePrintln(e.getErrorMessage());

Результат:

[mXparser-v.4.0.0] [2+3-] checking ...
[2+3-] lexical error 

Encountered "<EOF>" at line 1, column 4.
Was expecting one of:
    "(" ...
    "+" ...
    "-" ...
    <UNIT> ...
    "~" ...
    "@~" ...
    <NUMBER_CONSTANT> ...
    <IDENTIFIER> ...
    <FUNCTION> ...
    "[" ...

[2+3-] errors were found.

[mXparser-v.4.0.0]

2 - вычислить выражение

import org.mariuszgromada.math.mxparser.*;
...
...
Expression e = new Expression("2+3-(10+2)");
mXparser.consolePrintln(e.getExpressionString() + " = " + e.calculate());

Результат:

[mXparser-v.4.0.0] 2+3-(10+2) = -7.0

3 - использовать встроенные функции, константы, операторы и т. Д.

import org.mariuszgromada.math.mxparser.*;
...
...
Expression e = new Expression("sin(pi)+e");
mXparser.consolePrintln(e.getExpressionString() + " = " + e.calculate());

Результат:

[mXparser-v.4.0.0] sin(pi)+e = 2.718281828459045

4 - Определите свои собственные функции, аргументы и константы

import org.mariuszgromada.math.mxparser.*;
...
...
Argument z = new Argument("z = 10");
Constant a = new Constant("b = 2");
Function p = new Function("p(a,h) = a*h/2");
Expression e = new Expression("p(10, 2)-z*b/2", p, z, a);
mXparser.consolePrintln(e.getExpressionString() + " = " + e.calculate());

Результат:

[mXparser-v.4.0.0] p(10, 2)-z*b/2 = 0.0

5 - токенизировать строку выражения и играть с токенами выражения

import org.mariuszgromada.math.mxparser.*;
...
...
Argument x = new Argument("x");
Argument y = new Argument("y");
Expression e = new Expression("2*sin(x)+(3/cos(y)-e^(sin(x)+y))+10", x, y);
mXparser.consolePrintTokens( e.getCopyOfInitialTokens() );

Результат:

[mXparser-v.4.0.0]  --------------------
[mXparser-v.4.0.0] | Expression tokens: |
[mXparser-v.4.0.0]  ---------------------------------------------------------------------------------------------------------------
[mXparser-v.4.0.0] |    TokenIdx |       Token |        KeyW |     TokenId | TokenTypeId |  TokenLevel |  TokenValue |   LooksLike |
[mXparser-v.4.0.0]  ---------------------------------------------------------------------------------------------------------------
[mXparser-v.4.0.0] |           0 |           2 |       _num_ |           1 |           0 |           0 |         2.0 |             |
[mXparser-v.4.0.0] |           1 |           * |           * |           3 |           1 |           0 |         NaN |             |
[mXparser-v.4.0.0] |           2 |         sin |         sin |           1 |           4 |           1 |         NaN |             |
[mXparser-v.4.0.0] |           3 |           ( |           ( |           1 |          20 |           2 |         NaN |             |
[mXparser-v.4.0.0] |           4 |           x |           x |           0 |         101 |           2 |         NaN |             |
[mXparser-v.4.0.0] |           5 |           ) |           ) |           2 |          20 |           2 |         NaN |             |
[mXparser-v.4.0.0] |           6 |           + |           + |           1 |           1 |           0 |         NaN |             |
[mXparser-v.4.0.0] |           7 |           ( |           ( |           1 |          20 |           1 |         NaN |             |
[mXparser-v.4.0.0] |           8 |           3 |       _num_ |           1 |           0 |           1 |         3.0 |             |
[mXparser-v.4.0.0] |           9 |           / |           / |           4 |           1 |           1 |         NaN |             |
[mXparser-v.4.0.0] |          10 |         cos |         cos |           2 |           4 |           2 |         NaN |             |
[mXparser-v.4.0.0] |          11 |           ( |           ( |           1 |          20 |           3 |         NaN |             |
[mXparser-v.4.0.0] |          12 |           y |           y |           1 |         101 |           3 |         NaN |             |
[mXparser-v.4.0.0] |          13 |           ) |           ) |           2 |          20 |           3 |         NaN |             |
[mXparser-v.4.0.0] |          14 |           - |           - |           2 |           1 |           1 |         NaN |             |
[mXparser-v.4.0.0] |          15 |           e |           e |           2 |           9 |           1 |         NaN |             |
[mXparser-v.4.0.0] |          16 |           ^ |           ^ |           5 |           1 |           1 |         NaN |             |
[mXparser-v.4.0.0] |          17 |           ( |           ( |           1 |          20 |           2 |         NaN |             |
[mXparser-v.4.0.0] |          18 |         sin |         sin |           1 |           4 |           3 |         NaN |             |
[mXparser-v.4.0.0] |          19 |           ( |           ( |           1 |          20 |           4 |         NaN |             |
[mXparser-v.4.0.0] |          20 |           x |           x |           0 |         101 |           4 |         NaN |             |
[mXparser-v.4.0.0] |          21 |           ) |           ) |           2 |          20 |           4 |         NaN |             |
[mXparser-v.4.0.0] |          22 |           + |           + |           1 |           1 |           2 |         NaN |             |
[mXparser-v.4.0.0] |          23 |           y |           y |           1 |         101 |           2 |         NaN |             |
[mXparser-v.4.0.0] |          24 |           ) |           ) |           2 |          20 |           2 |         NaN |             |
[mXparser-v.4.0.0] |          25 |           ) |           ) |           2 |          20 |           1 |         NaN |             |
[mXparser-v.4.0.0] |          26 |           + |           + |           1 |           1 |           0 |         NaN |             |
[mXparser-v.4.0.0] |          27 |          10 |       _num_ |           1 |           0 |           0 |        10.0 |             |
[mXparser-v.4.0.0]  ---------------------------------------------------------------------------------------------------------------

6 - Вы можете найти гораздо больше в учебнике mXparser , mXparser math collection и Определение API mXparser .

7 - mXparser поддерживает:

• JAVA
• .NET / MONO
• .NET Core
• .NET Standard
• .NET PCL
• Xamarin.Android
• Xamarin.iOS

С наилучшими пожеланиями