Блог

У меня есть проблема, назначенная для школы, которая действительно меня смущает. В основном, на занятиях мы изучаем рекурсию. В качестве домашнего задания и введения во взаимную рекурсию мы должны написать вычислитель математических выражений, который использует взаимную рекурсию. Три метода, getExpressionValue, getTermValue и getFactorValue, должны вызывать друг друга, чтобы получить результат. Предполагается, что мы поддерживаем сложение, вычитание, умножение, деление и выражения в скобках. В поисках идей о том, как это сделать, я продолжаю сталкиваться с рекурсивным синтаксическим анализом, но я не уверен, подходит ли эта идея для этой проблемы.

Если бы кто-нибудь мог дать мне рекомендации или, возможно, ссылку на статью, в которой объясняется, как выполнить подобный синтаксический анализ, я был бы очень признателен. Спасибо.

Рекурсивный синтаксический анализ спуска действительно подходит для этого. Статья в Википедии на эту тему содержит хороший пример на C, который очень похож на то, что вы хотите сделать.

Основная идея заключается в следующем: если вы предполагаете, что полученный вами текст является допустимым выражением, он должен начинаться либо с левой круглой скобки, либо с числа. Итак, взглянув на первый символ, вы узнаете, является ли это выражением в скобках или нет. Если это не так, текст должен представлять собой последовательность из одного или нескольких терминов, разделенных или — . Итак, затем вы начинаете рассматривать начало текста как термин. Что такое термин? Это последовательность одного или нескольких факторов, разделенных * или / . Итак, вы начинаете рассматривать начало текста как фактор. Что такое фактор? Это либо число, либо выражение, заключенное в скобки, и, посмотрев на первый символ, вы можете определить, что это такое. Если это цифра, вы используете все последующие цифры, чтобы узнать, что это за число. Теперь метод, который пытался выяснить, каким было значение фактора, может вернуть это число методу, который пытается выяснить, каково значение термина. Теперь этот метод знает, что такое первое число, и может проверить следующий символ, чтобы узнать, является ли он * или a / (редактировать: это также может быть правая скобка, a или a -, что будет означать, что этот термин состоит только из одного числа), затем запроситьследующий фактор, который нужно извлечь, и так далее.

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

Рекурсия выглядит примерно так:

 double getValue(expression){

    if(expression.isBasic)
        return expression.LHS   expression.RHS 
    else
        return getValue(expression.LHS)   getValue(expression.RHS)
}
  

Изюминка вашей проблемы заключается в том, что вместо одной функции, вызывающей саму себя, у вас, вероятно, будет 4 или 5, которые вызывают друг друга. Какая вызываемая функция будет зависеть от того, какую операцию вы в данный момент обрабатываете в своем выражении: сложение, умножение, деление и т.д.