Рекурсивный оценщик выражений с использованием Java

Question

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

Я считал выражение (это строка)

"(" <expression1> <operator> <expression2> ")"

Вот мой алгоритм

String evaluate( String expression )

   if expression is digit
      return expression

   else if expression is "(" <expression1> <operator> <expression2> ")"
      cut the brackets out of it
      expression1 = evaluate( <expression1> )
      operator = <operator>
      expression2 = evaluate( <expression2> )

   if operator is +
      expression1 + expression2

   else if operator is -
      expression1 - expression2 

Моя проблема - синтаксический анализ <expression1>, <operator> и <expression2> из выражения. Как я могу это сделать?

Примечание: я не прошу код. Все, что мне нужно, это идея сделать это.

Спасибо,

-Ali

Answer 1

Моя проблема в разборе ииз выражения

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

Answer 2

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

Взгляните на алгоритм Shunting Yard для преобразования в postfix / RPN, а затем оцените его, используя стек, используя Postfix Operations .Это быстро (O (n)) и надежно.

HTH

Answer 3

Используйте StringTokenizer, чтобы разбить вашу входную строку на круглые скобки, операторы и числа, затем выполнить итерацию по вашим токенам, делая рекурсивный вызов для каждого open-parens и выходя из вашего метода для каждой закрывающей скобки.

Iзнаю, что вы не запрашивали код, но это работает для правильного ввода:

public static int eval(String expr) {
    StringTokenizer st = new StringTokenizer(expr, "()+- ", true);
    return eval(st);
}

private static int eval(StringTokenizer st) {
    int result = 0;
    String tok;
    boolean addition = true;
    while ((tok = getNextToken(st)) != null) {
        if (")".equals(tok))
            return result;
        else if ("(".equals(tok))
            result = eval(st);
        else if ("+".equals(tok))
            addition = true;
        else if ("-".equals(tok))
            addition = false;
        else if (addition)
            result += Integer.parseInt(tok);
        else
            result -= Integer.parseInt(tok);
    }
    return result;
}

private static String getNextToken(StringTokenizer st) {
    while (st.hasMoreTokens()) {
        String tok = st.nextToken().trim();
        if (tok.length() > 0)
            return tok;
    }
    return null;
}

Требуется лучшая обработка неправильного ввода, но вы понимаете ...

Answer 4

Либо вы используете генератор синтаксического анализатора, такой как JavaCUP или ANTLR . Запишите BNF вашего выражения и сгенерируйте парсер. Вот пример грамматики, с которого можно начать:

Expression ::= Digit
            |  LeftBracket Expression Plus Expression RightBracket
            |  LeftBracket Expression Minus Expression RightBracket
            |  LeftBracket Expression RightBracket

"Хакерский" способ сделать это самому - это найти первый ) возврат к самому близкому ( взгляду на свободное выражение в скобках между ними, просто разделить символы оператора и оценить.

Answer 5

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

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

Answer 6

Возможно создать регулярные выражения для выражения и оператора , а затем использовать сопоставление для идентификации и выделения вашего контента.