HOME ПРИМЕРЫ THANKS НОВИЧКАМ ДОКИ LINKS JavaScript Mail


 
В этот день много лет назад...
29 марта. В 1891 году (133 года назад) - Императорский рескрипт, объявляющий о начале строительства Транссибирской магистрали.
 
 

Turbo Pascal Examples. Простейший синтаксический анализатор.

Графика:
Построение графика функции
Прыгающий по экрану мячик.
Качание маятника.
Вложенные цветные круги.
Броуновское движение. Использование объектов.
Матрицы и массивы:
Сортировка элементов массива.
Удаление одинаковых элементов.
Простой пример на поворот матрицы.
Сортировка методом Шелла. +функции измерения временных интервалов.
Проверка выпуклости многоугольника.
Перемоножение матриц
Вычисление определителя матрицы. Рекурсия.
Нахождение обратной матрицы.
Задача об автостоянке.
Рекурсия. Подземелье сокровищ.
Численные методы:
Задачка на определение угла между стрелками часов.
Проверка на принадлежность точки многоугольнику.
Нахождение точки пересечения двух отрезков на плоскости.
Сортировка методом Шелла. +функции измерения временных интервалов.
Сортировка методом "пузырька". Пример на динамические структуры данных. Связанные списки.
Нахождение корня функции методом половинного деления.
Вычисление арккосинуса
Нахождение суммы цифр натурального числа.
Работа с фалами:
Рекурсивное сканирование директорий.
Работа со строками:
Работа со словами в предложении с разделителями.
Простейший синтаксический анализатор для распознавания и вычисления многчлена.
Синтаксический анализатор для распознавания и вычисления многчлена.
Работа со строками: смена кодировки, удаление тегов из HTML текста, обработка
Переименование файлов из кириллицы в латиницу.
Выдача контекстной подсказки.
Частотный словарь символов.
Подсчет повторяющихся символов в строке.
Ссылочные переменные:
Моделирование стека.
Пасьянс "Косынка".
Игры:
Пасьянс "Косынка".
Игра "Питон"
Игра "Анацефал". Пример использования объектов.
Игра "Минное поле"
Большие проекты:
Электронная картотека (без исходника)


 
Простейший синтаксический анализатор.


Задана функция F(x) в виде строки. Написать программу разбора и последующего вычисления значения фукции для простейшего случая, когда функция представляет из себя многочлен (функцию одной переменной х), то есть:
F(x) = a0 x N + a 1 x N–1 + ... + a N–2 x 2 + a N–1 x + a N
где a i - вещественные числа для всех i = 1,N; N - натуральное число.
В программе используются два объекта. Объект component, предсавляющий один член многочлена a i x N–i и объект mnogochlen представляющий совокупность (массив) объектов component.
Как обычно в языках программирования, будем предполагать, что a x N записано в формате: a * x ** N
Алгоритм таков. Разбиваем строку на кусочки, содержащие отдельные слагаемые, затем разбираем каждое из слагаемых и записываем все полученные данные в объект mnogochlen. После этого вычисляем многочлен.
Для работы со строками написаны вспомогательные процедуры:

  • explode - Разбить строку s на кусочки заданной подстрокой sep и записать результат в массив
  • strReplace - контекстный поиск и замена в строке
  • strToInt и strToReal - преобразовать строку в число
    Также написана процедура xPowerN вычисления степенной функции x N
    Смотри также комментарии в самой программе.


    const maxN = 20;
          arrStrN = 40;
    type
       component = object
       { a component of mnogochlen: an*x**n}
         a:real;
         n:integer;
         function value(x:real):real;
         end;
       mnogochlen = object
         n:byte;
         c:array[1..maxN] of component;
         function value(x:real):real;
         end;
       str_arr = array [1..arrStrN] of string;
    {*****************************************}
    function xPowerN(x:real;n:byte):real;
    { Возвращает х в степени n }
    const eps = 1e-8; { полагаем число нулем, если меньше eps }
    var z:shortint;
        r:real;
      begin
      if n=0 then xPowerN := 1 { любое число в нулевой степени = 1 }
      else if abs(x)<eps
        then xPowerN := 0 { 0 в любой положительной степени = 0 }
        else
          begin
          r := exp(n*ln(abs(x)));
          z := 1; if (x<0) then z := -1;
          if n mod 2 = 0
            then xPowerN := r      { четная степень всегда положительна }
            else xPowerN := z * r  { нечетная сохраняет знак }
          end;
      end;
    {*****************************************}
    function component.value(x:real):real;
    { Вычисление значения одной компоненты при заданном х }
      begin
      value:=a*xPowerN(x,n);
      end;
    function mnogochlen.value(x:real):real;
    { Вычисление значения многочлена при заданном х }
    var s:real;
        i:byte;
      begin
      for i:=1 to n do
        s:=s+c[i].value(x);
      value:=s;
      end;
    {*****************************************}
    { String functions }
    function explode(sep,s:string;var a:str_arr):integer;
    { Разбить строку s на кусочки подстрокой sep и записать результат
      в строковый массив str_arr. Сама функция вернет число кусочков
      Например:
        explode('mp','This is an simple example',a)
          вернет число 3, и строки в массиве a:
          a[1]='This is an si'; a[2]='le exa'; a[3]='le';
        explode(' ','This is an simple example',a) - вернет 5 и отдельные
          слова в массиве a 'This','is','an','simple','example' }
    var L:byte absolute s;
        i,n,k,d:byte;
      begin
      n:=0;
      for i:=1 to arrStrN do
        a[i]:='';
      k:=Pos(sep,s);
      d:=length(sep)-1;
      while (L*k>0) do
        begin
        inc(n);
        a[n]:=copy(s,1,k-1);
        delete(s,1,k+d);
        k:=Pos(sep,s);
        end;
      inc(n);
      a[n]:=s;
      explode:=n;
      end;
    function strReplace(findWhat,replaceTo,inString:string):string;
    { В строке inString заменить все вхождения подстроки findWhat
      на подстроку replaceTo }
    var sa:str_arr;
        n,i:byte;
        res:string;
      begin
      n:=explode(findWhat,inString,sa);
      res:=sa[1];
      for i:=2 to n do
        res:=res+replaceTo+sa[i];
      strReplace:=res;
      end;
    function strToInt(s:string):integer;
    { Преобразовать строку к целому числу. }
    var i, code: Integer;
      begin
      val(s, i, code);
      if code <> 0 then
        begin
        WriteLn('strToInt. Error at position: ', code,
          ' in line ', s, '. Program halted');
        halt
        end
      else
        strToInt := i;
      end;
    function strToReal(s:string):real;
    { Преобразовать строку к вещественному числу. }
    var code: Integer;
        r: real;
      begin
      val(s, r, code);
      if code <> 0 then
        begin
        WriteLn('strToReal. Error at position: ', code,
          ' in line ', s, '. Program halted');
        halt
        end
      else
        strToReal := r;
      end;
    {*****************************************}

    var s1,xPower:string;
        nParts:integer;
        b,sc:str_arr;
        mn:mnogochlen;
        i,t1,t2:byte;
        x:real;
    function F(x:real):real;
    { Для проверки }
      begin
      F:=3+4*x+6.5*x*x-2.6*x*x*x*x;
      end;
    begin
    { F(x) }
    s1:='3+4*x+6.5*x**2-2.6*x**4';
    writeln('F(x)=',s1);

    s1:=strReplace('-','+-',s1);
    nParts:=explode('+',s1,b);
    { Разбили на слагаемые }
    mn.n:=nParts;
    for i:=1 to nParts do
      begin
      { b[i] - член многочлена, имеет вид a*x**n
        если n >= 2 то просто выделяем степень. Частные случаи,
        когда n=1 член имеет вид a*x, n=0 - просто a }
      t1:=explode('**',b[i],sc);
      { Здесь: sc[1] - a*x; sc[2] - n }
      xPower := sc[2];
      t2:=explode('*',sc[1],sc);
      { Теперь уже sc[1] - a; sc[2] - x}
      mn.c[i].a:=strToReal(sc[1]);
      if t1>1
        then mn.c[i].n:=strToInt(xPower)   { n >= 2 }
        else if t2>1
          then mn.c[i].n:=1
          else mn.c[i].n:=0; { если была только одна компонента,
                               то значит это просто константа }
      end;
    randomize;
    x:=5-random(1000)/100;
    writeln(' x=',x:8:3,' F(x)=',mn.value(x):8:3, ' Check: ',F(x):8:3);
    end.

     

     

     

     

     

     

     


  • HOME