Наивный рекурсивный разбор: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
(Новая страница: « 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++; …»)
 
м (Ctrlalt переименовал страницу Рекурсивный спуск в Наивный рекурсивный разбор)
 
(не показаны 3 промежуточные версии этого же участника)
Строка 1: Строка 1:
Найдём значение выражения, описываемого подстрокой <tt>s[l..r]</tt>. Посмотрим, какая операция должна быть выполнена последней:
* Если подстрока содержит <tt>'+'</tt> или <tt>'-'</tt> вне скобок, то последней выполняется самая правая из этих операций. Пусть это <tt>'+'</tt> на позиции <tt>p1</tt>, тогда результат равен <tt>calc(l, p1 - 1) + calc(p1 + 1, r)</tt>;
* Иначе, если подстрока содержит <tt>'*'</tt> или <tt>'/'</tt> вне скобок, то последней выполняется самая правая из этих операций. Пусть это <tt>'*'</tt> на позиции <tt>p2</tt>, тогда результат равен <tt>calc(l, p2 - 1) * calc(p2 + 1, r)</tt>;
* Аналогично вводятся операции б&oacute;льших приоритетов. Для левоассоциативных операций ищется последнее вхождение, для правоассоциативных &mdash; первое;
* Если операции не были найдены, то подстрока может содержать выражение в скобках. В этом случае результат равен <tt>calc(l + 1, r - 1)</tt>;
* Иначе подстрока может содержать вызов функции. В этом случае следует вычислить аргументы и применить к ним соответствующую функцию;
* Иначе подстрока может содержать переменную или константу.
  double calc(int l, int r, double x) {
  double calc(int l, int r, double x) {
     int d = 0, p1 = -1, p2 = -1, p3 = -1;
     int d = 0, p1 = -1, p2 = -1, p3 = -1;
Строка 46: Строка 54:
     return res;
     return res;
  }
  }
[[Category: Разбор выражений]]

Текущая версия от 11:47, 23 января 2019

Найдём значение выражения, описываемого подстрокой 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;
}