Как разобрать строку, начинающуюся с конца С++

У меня есть математическое выражение, такое как cos(pi*cos(pi * sin(pi*y))), и я хочу его решить.

Нет, вы хотите оценить его. Решение говорит вам об условиях, при которых что-то верно. Оценка этого просто дает вам результирующее значение.

Я думаю, что лучший способ разобрать его — начать с конца строки.

Традиционный способ разбора подобных выражений — использование рекурсивного спуска. Он более общий и его гораздо проще реализовать. Поток управления выглядит примерно так:

• cos ( A ...

  • где A = pi * cos ( B ...

    • где B = pi * sin ( C ...

      • где C = pi * y

        теперь вы можете вычислить pi * y и вернуть значение C

      ... и теперь у вас есть C, вы можете оценить pi * sin(C) и вернуть значение B

    ... и теперь у вас есть значение B, вы можете оценить pi * cos(B), возвращая значение как A

  ... и теперь у вас есть значение A, вы можете оценить cos(A), и все готово.

Точно так же работает выражение C cos(M_PI * cos(M_PI * sin(M_PI * y))) (предполагая, что π является обычной, но нестандартной константой).

Он вычисляется примерно справа налево (фактически изнутри наружу), но по-прежнему читается слева направо. Мы только что пометили временные значения для ясности.

Этот поток управления часто просто превращается в дерево, подобное

[cos of _]
        |
    [pi * _]
          |
     [cos of _]
             |
         [pi * _]
               |
          [sin of _]
                  |
              [pi * y]

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

...Что вы думаете об этом?

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

cos( sin((pi * x) + y) + sin(y + (pi * x)) )

нельзя просто оценивать справа налево.

Не могли бы вы помочь мне реализовать код?

Отделите обработку строк (токенизацию) от синтаксического анализа и оценки. Гораздо проще рассуждать независимо о вашей обработке строк и вашей математике.

ОТРЕДАКТИРОВАНО: улучшение базового случая.

Это просто какой-то псевдокод, но идея должна работать:

int ParseAndCalculate(string input)
{
    if (input.DoesConvertToSomeIntegerWork())
        return input.ConvertToSomeInteger();

    string actionRequired = GetActionFromString(input, "(");
    int tempIndex = input.LocationOfFirst("(");
    int tempResult = ParseAndCalculate(input, tempIndex, input.Length -1);
    tempResult = PerformRequiredAction(tempResult, actionRequired);

    return tempResult;
}

Не уверен, что вы должны вернуть в базовом случае. Может быть, выяснить, что там на самом деле стоит?

Если вы хотите написать программу на C/C++, которая может анализировать математические выражения, подобные приведенным выше, вы можете сами написать нисходящий синтаксический анализатор на C/C++ или посмотреть на GNU Bison.

Bison — это генератор синтаксических анализаторов, и он поставляется с пример, который очень близок к вашей проблеме.

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

Его также можно использовать для вычисления выражений в «правильном» порядке, поскольку он поддерживает определения приоритета операторов.