синтаксический анализатор мат.формул

From

George Shuklin (2:5030/744.46)

To

Svirskiy Taras ()

Date

2000-02-26T09:38:56Z

Area

RU.ALGORITHMS

А, это ты Svirskiy! Вот что я тебе сказать хотел...
  В 25 февраля 2000 01:12, Svirskiy Taras решил написать All:
 ST> Может кто-нибудь знает, или писал  алгоритм сабжа,
 ST> или где об этом вообще почитать можно.
 ST> Плиз, пмомогите, сильно надо.
Вот, лови. Не пинать. Писано в свое время для сдачи по ПОВС, посему возможны глюки.

Разбор по бинарному дереву
Принцип разбора

1*(2+3)*5-6*7+8
Наименее приоритетная операция + между 7 и 8
Рекуррентно вызовем себя для 1*(2+3)*5-6*7 и для 8, получившиеся числа сложем.
При вызове с числом просто его же и возвращаем
При бызове для 1*(2+3)*5-6*7 : Наимнее приоритетная оп. '-'
Вызываем себя же для 1*(2+3)*5 и для 6*7. Вычитаем. Возвращаем получившиеся.
далее я думаю понятно...

>> файло всякое начинается
int cmp (char* Line1,char * Line2)
//Проверяет, является ли line2 началом line1, если да, то возвр. 1
{
  while (*Line2)
  {
    if (!*Line1) return 0;
    if (*Line2++!=*Line1++) return 0;
  }
  return 1;
}

int Operator (char Line[],int pos)
{
//Возвращает приоритет операции
 switch (Line[pos])
  {
    case'+': return 1;
    case'-': return 1;
    case'*': return 2;
    case'/': return 2;
  }
  if (cmp (Line+pos,"sin")) return 3;
  if (cmp (Line+pos,"cos")) return 3;
  return 255;
}

/*************************************************/
float Val (char Line[], int Begin, int End,float x)
/************ Основная ф-ция *********************/
//На входе - Line выражение для разбора
//Begin,End - начало/конец строки для разбора
//x - в строке вместо 'x' будет подставлено
//указанное значение
{
 int i;//счетчик
 int deep=0;//глубина вложенности скобок
 int deepest=255;//максимальная достигнутая глубина вложенности
 int priority=255;//приоритет операции
 int lowlest=-1;
 char temp[255];
 for (i=End;i>=Begin;i--)//начинаем разбирать с конча в начало
 {
  if (Line[i]==')'){deep++;continue;}//если скобка - пропускаем
  if (Line[i]=='('){deep--;continue;}
  if (Operator(Line,i)<255)//Если найден оператор
  {
   if (deep<deepest)//если он менее приоритетный
   {
    lowlest=i;
    deepest=deep;
    priority=Operator(Line,i);
    continue;
   }
   if (deep<=deepest&&Operator(Line,i)<priority)
   {
    lowlest=i;
    deepest=deep;
    priority=Operator(Line,i);
    continue;
   }
  }
 }
 if (priority==255)//не неайден ни один оператор - надо вернуть цифру.
 {
  for (i=Begin;i<=End;i++)
  {
   temp[i-Begin]=Line[i];
   if (Line [i]=='x'||Line[i]=='X') return x;
  }
  temp[End-Begin+1]='\0';
  return (float)atof (temp);
 }

 if (deepest!=0)//есть внешние скобки - по крайней мере одна пара.
  return Val (Line,Begin+1,End-1,x);//сужаем размер рассматриваемой строки

 //во всех других случаях имеем полноценное выражение

 switch (Operator (Line,lowlest))
 {
 case 1: switch (Line[lowlest])
   {
   case '+': return Val(Line,Begin,lowlest-1,x)+Val(Line,lowlest+1,End,x);
   case '-': return Val(Line,Begin,lowlest-1,x)-Val(Line,lowlest+1,End,x);
   }
 case 2: switch (Line[lowlest])
   {
   case '*': return Val(Line,Begin,lowlest-1,x)*Val(Line,lowlest+1,End,x);
   case '/': return Val(Line,Begin,lowlest-1,x)/Val(Line,lowlest+1,End,x);
   }
 case 3:
   if (strcmp (Line+lowlest,"sin")>0) return (float)sin (Val(Line,lowlest+4,End,x));
   if (strcmp (Line+lowlest,"cos")>0) return (float)cos (Val(Line,lowlest+4,End,x));

 }
}
>> файло всякое заканчивается

George.

--- GoldED+/W32 1.1.2
 * Origin: time 0:00-8:00 freq time 2:00-8:00 phone 2738633 (2:5030/744.46)