Наивный рекурсивный разбор

Материал из Олимпиадное программирование в УлГТУ
Перейти к: навигация, поиск

Найдём значение выражения, описываемого подстрокой s[l..r]. Посмотрим, какая операция должна быть выполнена последней:

  • Если подстрока содержит '+' или '-' вне скобок, то последней выполняется самая правая из этих операций. Пусть это '+' на позиции p1, тогда результат равен calc(l, p1 - 1) + calc(p1 + 1, r);
  • Иначе, если подстрока содержит '*' или '/' вне скобок, то последней выполняется самая правая из этих операций. Пусть это '*' на позиции p2, тогда результат равен calc(l, p2 - 1) * calc(p2 + 1, r);
  • Аналогично вводятся операции бóльших приоритетов. Для левоассоциативных операций ищется последнее вхождение, для правоассоциативных — первое;
  • Если операции не были найдены, то подстрока может содержать выражение в скобках. В этом случае результат равен calc(l + 1, r - 1);
  • Иначе подстрока может содержать вызов функции. В этом случае следует вычислить аргументы и применить к ним соответствующую функцию;
  • Иначе подстрока может содержать переменную или константу.
double calc(int l, int r, double x) {
    int d = 0, p1 = -1, p2 = -1, p3 = -1;
    for (int i = l; i <= r; i++) {
        if (s[i] == '(')
            d++;
        if (s[i] == ')')
            d--;
        if (!d) {
            if (s[i] == '+' || s[i] == '-')
                p1 = i;
            if (s[i] == '*' || s[i] == '/')
                p2 = i;
            if (s[i] == '^' && p3 == -1)
                p3 = i;
        }
    }
    if (p1 != -1) {
        if (s[p1] == '+')
            return calc(l, p1 - 1, x) + calc(p1 + 1, r, x);
        else
            return calc(l, p1 - 1, x) - calc(p1 + 1, r, x);
    }
    if (p2 != -1) {
        if (s[p2] == '*')
            return calc(l, p2 - 1, x) * calc(p2 + 1, r, x);
        else
            return calc(l, p2 - 1, x) / calc(p2 + 1, r, x);
    }
    if (p3 != -1)
        return pow(calc(l, p3 - 1, x), calc(p3 + 1, r, x));
    if (s[l] == '(' && s[r] == ')')
        return calc(l + 1, r - 1, x);
    if (s[l] == 'c')
        return cos(calc(l + 4, r - 1, x));
    if (s[l] == 's' && s[l + 1] == 'i')
        return sin(calc(l + 4, r - 1, x));
    if (s[l] == 's' && s[l + 1] == 'q')
        return sqrt(calc(l + 5, r - 1, x));
    if (s[l] == 'x')
        return x;
    double res;
    char tmp = s[r + 1];
    s[r + 1] = 0;
    sscanf(s + l, "%lf", &res);
    s[r + 1] = tmp;
    return res;
}