Формула содержит: вещественные константы, переменную x и операции «+», «–», «*», «/».
#define NO_OPERATION -1
#define ADD 0
#define SUB 1
#define MUL 2
#define DIV 3
#include … // подключение заголовочных файлов
float parsing (char *str, float x);
void main()
{
char *str=» 2+2‑x-x»;
printf («%f», parsing (str, 3)); // -2
}
float parsing (char * str, float x)
// функция разделения строки на две части
{
char * substr1 = NULL, * substr2 = NULL;
// substr1 – левая часть строки перед знаком
// substr2 – правая часть после знака
char * ptr = NULL;
float y, z;
// y – промежуточная переменная для хранения левого операнда,
// z – для правого, x и y рекурсивно вызывают parsing
char op = NO_OPERATION;
// op – операция (+, -, *, /)
// поиск первого появления знака ‘+’ и перевод указателя на этот знак
if ((ptr = strchr (str, '+'))!= NULL)
op = ADD; // 0
// аналогичный поиск знака ‘–’, ‘*’, ‘/’ но с конца строки
else if ((ptr = strrchr (str, '-'))!= NULL)
op = SUB; // 1
else if ((ptr = strchr (str, '*'))!= NULL)
op = MUL; // 2
else if ((ptr = strchr (str, '/'))!= NULL)
op = DIV; // 3
if (op!= NO_OPERATION)
{
substr1 = (char *) malloc ((int) (ptr – str) + 1);
// память под левую подстроку плюс один знак для конца строки
if (substr1 == NULL)
{
printf («\nERROR: No memory.\n»);
exit (1);
}
substr2 = (char *) malloc (strlen(str) – (int) (ptr-str));
// память под правую подстроку
if (substr2 == NULL)
{
free (substr1);
printf («ERROR: No memory.\n»);
exit (1);
}
// запись в substr1 первых ptr-str символов…
// …строки str и конца строки
strncpy (substr1, str, (int) (ptr-str));
substr1 [(int) (ptr-str)] = '\0';
// запись в substr2, начиная с ptr+1 до конца строки str
strcpy (substr2, ptr+1);
y = parsing (substr1, x);
// вычисляем формулу левой подстроки
z = parsing (substr2, x);
// вычисляем формулу правой подстроки
switch (op)
{
case ADD: y += z;
break;
case SUB: y -= z;
break;
case MUL: y *= z;
break;
case DIV: if (z == 0)
{
printf («\nДеление на ноль»);
exit(1);
}
y /= z;
break;
}
free (substr1);
free (substr2);
return y;
} // if op
else if (! strcmp (str, «x»))
// str совпадает с «x», возвращаем x
return x;
else
// str содержит только вещественную константу
return atof (str);
}
Схема стека вызовов представлена на рис. 8. Первые четыре креста – условия на выход из parsing, пятый крест – совпадение строки с «x» и return x, третий крест – совпадение строки с вещественной константой и return atof(str). Первый круг – y, второй – z. Между ними операция. Глубина стека равна n, где n+1 – количество операций.
Рис. 8. Схема стека
Таким образом, имеем явную двукратную рекурсию.
Недостатки рассмотренной функции parsing.
- Для некоторых строк двукратная рекурсия вырождается в однократную. Например, для строки «x+x+x+x+x+x+x+x» схема стека вызовов будет иметь глубину 7, а ширину всегда 2. В результате будет забиваться стек. Лучше искать среднюю операцию. Тогда бинарное дерево стека вызовов будет сбалансированным.
- Функция parsing для каждого х будет создавать бинарное дерево стека вызовов. Это может привести к замедлению счета, например при построении графиков. Лучше один раз рекурсивным способом построить промежуточную строку, содержащую польскую запись формулы. Затем формула будет вычисляться по промежуточной строке для каждого х не рекурсивно.
Пример. (Салфетка Серпинского)
Реализовать «салфетку Серпинского» (геометрический фрактал). Как она образуется? Рисуется треугольник и в нем средние линии. В образованных при углах исходного треугольника новых треугольниках опять рисуются средние линии и так далее до заданного порядка вложенности рекурсии.
Рис. 9. Салфетка Серпинского