Наивный рекурсивный разбор: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) (Новая страница: « 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 (обсуждение | вклад) м (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>; | |||
* Аналогично вводятся операции бóльших приоритетов. Для левоассоциативных операций ищется последнее вхождение, для правоассоциативных — первое; | |||
* Если операции не были найдены, то подстрока может содержать выражение в скобках. В этом случае результат равен <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;
}