Написание простого парсера уравнений

Question

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

((5 + (3 + (7 * 2))) - (8 * 9)) / 72

Скажем, кто-то написал это, как я могу справиться с таким количеством вложенных скобок?

Answer 1

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

из вики,

While there are tokens to be read:

    Read a token.
    If the token is a number, then add it to the output queue.
    If the token is a function token, then push it onto the stack.
    If the token is a function argument separator (e.g., a comma):

        Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue. If no left parentheses are encountered, either the separator was misplaced or parentheses were mismatched.

    If the token is an operator, o1, then:

        while there is an operator token, o2, at the top of the stack, and

                either o1 is left-associative and its precedence is less than or equal to that of o2,
                or o1 is right-associative and its precedence is less than that of o2,

            pop o2 off the stack, onto the output queue;

        push o1 onto the stack.

    If the token is a left parenthesis, then push it onto the stack.
    If the token is a right parenthesis:

        Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue.
        Pop the left parenthesis from the stack, but not onto the output queue.
        If the token at the top of the stack is a function token, pop it onto the output queue.
        If the stack runs out without finding a left parenthesis, then there are mismatched parentheses.

When there are no more tokens to read:

    While there are still operator tokens in the stack:

        If the operator token on the top of the stack is a parenthesis, then there are mismatched parentheses.
        Pop the operator onto the output queue.

Exit.

Answer 2

Самый простой способ решить эту проблему - реализовать алгоритм Shunting Yard для преобразования выражения из инфиксной нотации в постфиксную нотацию.

Это легко с капиталом E для вычисления выражения постфикса.1003 *

Алгоритм Shunting Yard может быть реализован в менее чем 30 строках кода.Вам также понадобится токенизировать ввод (преобразовать строку символов в последовательность операндов, операторов и знаков пунктуации), но написать простой конечный автомат, чтобы сделать это просто.

Answer 3

Джеймс дал хороший ответ. В Википедии тоже есть хорошая статья.

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

разбор до первого ")". Затем проанализируйте предыдущий "(". Оцените, что находится внутри, и замените весь набор значением. Затем повторите рекурсивно, пока не закончите.

Итак, в этом примере вы сначала проанализируете "(7 * 2)" и замените его на 14. Тогда вы получите (3 + 14) и замените его на 17. И так далее.

Вы можете сделать это с помощью регулярных выражений или даже .IndexOf и .Substring.

Я собираюсь проверить мой синтаксис здесь, но что-то вроде этого:

int y = string.IndexOf(")");  
int x = string.Substring(0,y).LastIndexOf("(");  
string z = string.Substring(x+1,y-x-1) // This should result in "7 * 2"

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

Answer 4

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

Итак, используя lex (flex) / yacc (бизон) Я бы сделал:

эл

%option noyywrap

Number      [0-9]+
WhiteSpace  [ \t\v\r]+
NewLine     \n
%{
#include <stdio.h>
%}

%%

\(              return '(';
\)              return ')';
\+              return '+';
\-              return '-';
\*              return '*';
\/              return '/';

{Number}        return 'N';
{NewLine}       return '\n';
{WhiteSpace}    /* Ignore */

.               fprintf(stdout,"Error\n");exit(1);


%%

эй

%{
#include <stdio.h>
    typedef double (*Operator)(double,double);
    double mulOp(double l,double r)  {return l*r;}
    double divOp(double l,double r)  {return l/r;}
    double addOp(double l,double r)  {return l+r;}
    double subOp(double l,double r)  {return l-r;}
extern char* yytext;
extern void yyerror(char const * msg);
%}

%union          
{
    Operator        op;
    double          value;
}

%type   <op>        MultOp AddOp
%type   <value>     Expression MultExpr AddExpr BraceExpr

%%

Value:          Expression '\n'   { fprintf(stdout, "Result: %le\n", $1);return 0; }

Expression:     AddExpr                          { $$ = $1;}

AddExpr:        MultExpr                         { $$ = $1;}
            |   AddExpr   AddOp  MultExpr        { $$ = ($2)($1, $3);}

MultExpr:       BraceExpr                        { $$ = $1;}
            |   MultExpr  MultOp BraceExpr       { $$ = ($2)($1, $3);}

BraceExpr:      '(' Expression ')'               { $$ = $2;}
            |   'N'                              { sscanf(yytext,"%le", &$$);}

MultOp:         '*'                              { $$ = &mulOp;}
            |   '/'                              { $$ = &divOp;}
AddOp:          '+'                              { $$ = &addOp;}
            |   '-'                              { $$ = &subOp;}
%%

void yyerror(char const * msg)
{
    fprintf(stdout,"Error: %s", msg);
}

int main()
{
    yyparse();
}

Сборка

> flex e.l
> bison e.y
> gcc *.c
> ./a.out
((5 + (3 + (7 * 2))) - (8 * 9)) / 72
Result: -6.944444e-01
>

Выше также обрабатываетобычные правила приоритета операторов:
Не из-за того, что я сделал, но кто-то умный разработал это давным-давно, и теперь вы можете легко получить грамматические правила для разбора выражений (просто google C Grammer и извлеките нужную часть).

> ./a.out
2 + 3 * 4
Result: 1.400000e+01

Answer 5

Вы можете использовать либо анализатор конечного автомата (yacc LALR и т. Д.), Либо анализатор рекурсивного спуска.

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

Answer 6

Или вы можете просто сделать это в одной строке в R:

> eval(parse(text = '((5 + (3 + (7*2))) - (8 * 9))/72' ))
[1] -0.6944444

Answer 7

Да, алгоритм Алгоритм маневрового двора , но если вы хотите реализовать, я предлагаю вам python и его пакет компилятора

import compiler
equation = "((5 + (3 + (7 * 2))) - (8 * 9)) / 72"
parsed = compiler.parse( equation )

print parsed

Вы также можете оценить этовыражение с помощью встроенного метода eval ()

print eval("5 + (4./3) * 9") // 17

Answer 8

Что? Нееет. Если это не домашнее задание, не пишите парсер , а не . Там есть сотня парсеров, и у всех них есть одно преимущество перед всеми предложениями здесь: они уже там. Вам не нужно их писать.

Answer 9

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

 number

или формы

 (expression operator expression)

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

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

Answer 10

Сначала преобразуйте выражение в префиксную или постфиксную форму. Тогда его очень легко оценить!

Пример:

Оценка выражения в постфиксе.