Ответ 1

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

Из wiki,

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.

Ответ 2

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

Это Easy-with-a-capital-E для оценки постфиксного выражения.

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

Ответ 3

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

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

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

Вы можете сделать это с помощью Regex или даже .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"

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

Ответ 4

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

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

Ответ 5

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

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

e.l

%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);


%%

e.y

%{
#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();
}

Build

> 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

Ответ 6

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

Пример:

Оценка выражения Postfix.

Ответ 7

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

 number

или формы

 (expression operator expression)

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

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

Ответ 8

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

Ответ 9

Да алгоритм алгоритм Shunting yard, но если вы хотите реализовать, я предлагаю вам 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

Ответ 10

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

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