Пример использования рекурсии для проверки правильности записи арифметического выражения
Пусть задан синтаксис арифметического выражения:
Необходимо проверить правильность записи арифметического выражения в соответствии с заданным синтаксисом.
Структура данных:
char ae[80], //арифметическое выражение
* pf ; // указатель на текущую позицию в ae
ЗАМЕЧАНИЯ:
Каждая функция получает указатель на текущую позицию в ae и пытается выделить соответствующий элемент, начиная с этой позиции. После выделения элемента указатель перемещается на следующую позицию после этого элемента.
Каждая функция возвращает значение 0, если элемент выделен, в противном случае возвращается 1.
Каждая функция использует только глобальные переменные, чтобы их значения не копировались при каждом вызове функций.
#include <stdio.h>
#include <conio.h>
#include <ctype.h>
#define ZNAK *pf == '+' || *pf == '-' //макроопределение
//глобальные переменные
char ae[80], *pf;
//прототипы функций
int fae ();
int fslag ();
int fmnog ();
int fper ();
int fid();
int fconst();
void main ()
{
printf ("Введите выражение: \n");
gets (ae); pf=ae;
printf ("выражение: \n %s \n",pf);
if (fae () || *pf ) /* то есть в выражении есть ошибка,
или после нуль-символа есть еще символы, т.е. pf != ‘\0’ (после fae указатель pf должен показывать на конец выражения:‘\0’)*/
printf (" ошибка - %d символ %c \n", pf-ae,*pf);
/* разность указателей pf-ae равна количеству символов, то есть номеру символа. Указатель на char *pf даст
символ, то есть содержимое по адресу */
else printf (" выражение правильно \n");
getch();
}
int fae ()//проверка правильности арифметического выражения
{
if (ZNAK) pf++;//по синтаксису - пропуск возможного знака
while (1) // бесконечный цикл
{
if (fslag()) return (1);// есть ошибка в слагаемом
if (ZNAK) pf++;// пропуск знака в арифм. выражении
else return (0);// конец арифметического выражения
}
}
int fslag ()//проверка правильности слагаемого
{
while (1)
{
if (fmnog()) return (1);//в множителе есть ошибка
if (*pf == '*' || *pf =='/') pf++;
else return (0);// конец арифметического выражения
}
}
int fmnog ()//проверка правильности множителя
{
if (*pf =='(') //выражение в скобках
{
pf++;
//рекурсия
if (fae()) return (1); //есть ошибка в ae
if (*pf != ')' ) return(1);//после ae не скобка
else pf++; // пропуск закрывающейся скобки
}
else
if (fper() && fconst()) return(1);
//если дальше в выражении не переменная и не константа
return (0);
}
int fper ()//проверка правильности переменной
{
if (fid()) return(1); // есть ошибка в идентификаторе
if (*pf =='[')
{ do
{
pf++;
if (fae()) return (1); //есть ошибка в ae
} // пока запятая, проверяется fae в цикле
while (*pf ==',');
if (*pf != ']' ) return(1);
pf++;
}
return (0);
}
int fid()//проверка правильности идентификатора
{
if (isalpha(*pf)==0) return(1);//первый символ - не буква
while (isalpha(*pf) || isdigit(*pf)) pf++;
//пропуск букв и цифр
return(0); // в идентификаторе может быть одна буква
}
int fconst() //проверка правильности константы без знака
{
int flag =1; //флаг определяет наличие цифр в мантиссе
while (isdigit(*pf)) //пока есть цифры
{
flag=0;
pf++; // пропуск цифр в мантиссе
}
if (*pf =='.')
{
pf++;
while(isdigit(*pf)) {pf++; flag=0; }
//если есть цифры, после цикла flag = 0,иначе flag =-1
}
if (flag) return(1); // если нет цифр
if (*pf =='E') // проверка наличия экспоненты
{
pf++;
if(ZNAK) pf++;//пропуск возможного знака
if(!isdigit(*pf)) return(1);
// в порядке должна быть хотя бы одна цифра
while (isdigit(*pf)) pf++;//пропуск цифр
}
return(0);
}