Автор Тема: Сопоставление с образцом (Прочитано 42922 раз)

Kemet · « **Ответ #60 :** Сентябрь 22, 2012, 07:31:56 pm »

Косметика + условие для учета '?' + дополнительные тесты на прохождение '?':

MODULE Match;
IMPORT Log := KernelLog, Strings;

PROCEDURE MatchIt( CONST text, pattern : ARRAY OF CHAR;
                         posT, posP    : LONGINT;
                         lenT, lenP    : LONGINT ): BOOLEAN;

VAR
  chT, chP: CHAR;
  iT,  iP : LONGINT;

  PROCEDURE NoMoreCharInPattern(): BOOLEAN;
  BEGIN
    WHILE ( posP # lenP ) & ( pattern[ posP ] = '*' ) DO
      INC( posP );
    END;
    RETURN posP = lenP;
  END NoMoreCharInPattern;

  PROCEDURE FindCharInText( ch: CHAR; pos: LONGINT ): BOOLEAN;
  BEGIN
    WHILE pos # lenT DO
      IF ( text[ pos ] = ch ) OR ( ch = '?' ) THEN posT := pos; RETURN TRUE END;
      INC ( pos );
    END;
    RETURN FALSE;
  END FindCharInText;

  PROCEDURE Retry;
  BEGIN
    posP := iP;
    INC( posP );
    INC( posT );
    iT := posT;
  END Retry;

BEGIN
  iT := lenT;
  iP := lenP;
  LOOP
    IF posT = lenT THEN
      RETURN NoMoreCharInPattern();
    ELSIF posP = lenP THEN
      IF ( iP # lenP ) & FindCharInText( pattern[iP] , iT ) THEN
        Retry
      ELSE
        RETURN FALSE;
      END;
    ELSE
      chT := text[ posT ];
      chP := pattern[ posP ];
      IF chP = '*' THEN
        INC( posP );
        IF NoMoreCharInPattern() THEN RETURN TRUE END;
        chP := pattern[ posP ];
        IF FindCharInText( chP, posT ) THEN
          iP := posP;
          INC( posP );
          INC( posT );
          iT := posT;
        ELSE
          RETURN FALSE;
        END;
      ELSIF ( chP = chT ) OR ( chP = '?' ) THEN
        INC( posP );
        INC( posT );
      ELSE
        IF ( iP # lenP ) & FindCharInText( pattern[iP] , iT ) THEN
          Retry;
        ELSE
          RETURN FALSE;
        END;
      END;
    END;
  END;
END MatchIt;

PROCEDURE DoMatch*( CONST text, pattern: ARRAY OF CHAR ): BOOLEAN;
BEGIN
  RETURN MatchIt( text, pattern, 0, 0, Strings.Length( text ), Strings.Length( pattern ));
END DoMatch;

  PROCEDURE Test;
  BEGIN
    Log.String( "=========================================" ); Log.Ln;

    Log.String(         " 1)'' $ '' = " );
      Log.Boolean( DoMatch( '' , '' ));
    Log.Ln;

    Log.String(         " 2)'' $ 'a' = " );
      Log.Boolean( DoMatch( '' , 'a' ));
    Log.Ln;

    Log.String(         " 3)'' $ '*' = " );
      Log.Boolean( DoMatch( '' , '*' ));
    Log.Ln;

    Log.String(         " 4)'a' $ '' = " );
      Log.Boolean( DoMatch( 'a' , '' ));
    Log.Ln;

    Log.String(         " 5)'abcxyz' $ '*' = " );
      Log.Boolean( DoMatch( 'abcxyz' , '*' ));
    Log.Ln;

    Log.String(         " 6)'abcxyz' $ 'ab*' = " );
      Log.Boolean( DoMatch( 'abcxyz' , 'ab*' ));
    Log.Ln;

    Log.String(         " 7)'abcxyz' $ '*ab' = " );
      Log.Boolean( DoMatch( 'abcxyz' , '*ab' ));
    Log.Ln;

    Log.String(         " 8)'abcxyz' $ '*yz' = " );
      Log.Boolean( DoMatch( 'abcxyz' , '*yz' ));
    Log.Ln;

    Log.String(         " 9)'abcxyz' $ '*yz*' = " );
      Log.Boolean( DoMatch( 'abcxyz' , '*yz*' ));
    Log.Ln;

    Log.String(         "10)'abcxyz' $ 'ab*yz' = " );
      Log.Boolean( DoMatch( 'abcxyz' , 'ab*yz' ));
    Log.Ln;

    Log.String(         "11)'abcxyz' $ '*cx*' = " );
      Log.Boolean( DoMatch( 'abcxyz' , '*cx*' ));
    Log.Ln;

    Log.String(         "12)'abcxyz' $ '*a*c*y*' = " );
      Log.Boolean( DoMatch( 'abcxyz' , '*a*c*y*' ));
    Log.Ln;

    Log.String(         "13)'abcxyz' $ 'a*b***c*z' ) = " );
      Log.Boolean( DoMatch( 'abcxyz' , 'a*b***c*z' ));
    Log.Ln;

    Log.String(         "14)'abcxyz' $ '**a*b***y*z**' ) = " );
      Log.Boolean( DoMatch( 'abcxyz' , '**a*b***y*z**' ));
    Log.Ln;

    Log.String(         "15)'abcxyz' $ 'ab*x*c*yz' ) = " );
      Log.Boolean( DoMatch( 'abcxyz' , 'ab*x*c*yz' ));
    Log.Ln;

    Log.String(         "16)'abcxyz' $ '*cx' ) = " );
      Log.Boolean( DoMatch( 'abcxyz' , '*cx' ));
    Log.Ln;

    Log.String(         "17)'abcxyxyz' $ '*xyz' ) = " );
      Log.Boolean( DoMatch( 'abcxyxyz' , '*xyz' ));
    Log.Ln;

    Log.String(         "18)'abcxyzxy' $ '*xyz' ) = " );
      Log.Boolean( DoMatch( 'abcxyzxy' , '*xyz' ));
    Log.Ln;

    Log.String(         "19)'abcxyzxyz' $ '*xyz' ) = " );
      Log.Boolean( DoMatch( 'abcxyzxyz' , '*xyz' ));
    Log.Ln;

    Log.String(         "20)'abcxyzxyz' $ '*xyz*xyz' ) = " );
      Log.Boolean( DoMatch( 'abcxyzxyz' , '*xyz*xyz' ));
    Log.Ln;

    Log.String(         "21)'' $ '?' ) = " );
      Log.Boolean( DoMatch( '' , '?' ));
    Log.Ln;

    Log.String(         "22)'a' $ '?' ) = " );
      Log.Boolean( DoMatch( 'a' , '?' ));
    Log.Ln;

    Log.String(         "23)'az' $ '?' ) = " );
      Log.Boolean( DoMatch( 'az' , '?' ));
    Log.Ln;

    Log.String(         "24)'az' $ '??' ) = " );
      Log.Boolean( DoMatch( 'az' , '??' ));
    Log.Ln;

    Log.String(         "25)'az' $ '?*?' ) = " );
      Log.Boolean( DoMatch( 'az' , '?*?' ));
    Log.Ln;

    Log.String(         "26)'abyz' $ '?*?' ) = " );
      Log.Boolean( DoMatch( 'abyz' , '?*?' ));
    Log.Ln;

    Log.String(         "27)'abyz' $ '?*?*' ) = " );
      Log.Boolean( DoMatch( 'abyz' , '?*?*' ));
    Log.Ln;

    Log.String(         "28)'abcxyzxyz' $ '*?*' ) = " );
      Log.Boolean( DoMatch( 'abcxyzxyz' , '*?*' ));
    Log.Ln;

    Log.String(         "29)'abcxyzxyz' $ '*xyz*?yz' ) = " );
      Log.Boolean( DoMatch( 'abcxyzxyz' , '*xyz*?yz' ));
    Log.Ln;

    Log.String(         "30)'abcxyzxyz' $ '*?xyz*?yz' ) = " );
      Log.Boolean( DoMatch( 'abcxyzxyz' , '*?xyz*?yz' ));
    Log.Ln;

    Log.String(         "31)'abcxyzxyz' $ '?*xyz*y?' ) = " );
      Log.Boolean( DoMatch( 'abcxyzxyz' , '?*xyz*y?' ));
    Log.Ln;

    Log.String(         "32)'abcxyzxyz' $ '*x?z' ) = " );
      Log.Boolean( DoMatch( 'abcxyzxyz' , '*x?z' ));
    Log.Ln;

    Log.String(         "33)'abcxyzxyz' $ '*xyz*x?z' ) = " );
      Log.Boolean( DoMatch( 'abcxyzxyz' , '*xyz*x?z' ));
    Log.Ln;

    Log.String(         "34)'abcxyzxyz' $ '*x?z*x?z' ) = " );
      Log.Boolean( DoMatch( 'abcxyzxyz' , '*x?z*x?z' ));
    Log.Ln;

    Log.String(         "35)'abcxyzxyz' $ '*??x?z*x?z' ) = " );
      Log.Boolean( DoMatch( 'abcxyzxyz' , '*??x?z*x?z' ));
    Log.Ln;

    Log.String(         "36)'abcxyzxyz' $ '*??x?0z*x?z' ) = " );
      Log.Boolean( DoMatch( 'abcxyzxyz' , '*??x?0z*x?z' ));
    Log.Ln;

    Log.String(         "37)'abcxyzxyz' $ '*??x?z?*x?z' ) = " );
      Log.Boolean( DoMatch( 'abcxyzxyz' , '*??x?z?*x?z' ));
    Log.Ln;

    Log.String(         "38)'abcxyzxyz' $ '*??x?z?*?z' ) = " );
      Log.Boolean( DoMatch( 'abcxyzxyz' , '*??x?z?*?z' ));
    Log.Ln;

    Log.String(         "39)'abcxyz0xyz' $ '*??x?z?*x?z' ) = " );
      Log.Boolean( DoMatch( 'abcxyz0xyz' , '*??x?z?*x?z' ));
    Log.Ln;

    Log.String( "=========================================" ); Log.Ln;
  END Test;


PROCEDURE Do*;
BEGIN
  Test;
END Do;

END Match.

SystemTools.Free Match ~

Match.Do~

Результаты тестов:

Код: [Выделить]

 1)'' $ '' = TRUE
 2)'' $ 'a' = FALSE
 3)'' $ '*' = TRUE
 4)'a' $ '' = FALSE
 5)'abcxyz' $ '*' = TRUE
 6)'abcxyz' $ 'ab*' = TRUE
 7)'abcxyz' $ '*ab' = FALSE
 8)'abcxyz' $ '*yz' = TRUE
 9)'abcxyz' $ '*yz*' = TRUE
10)'abcxyz' $ 'ab*yz' = TRUE
11)'abcxyz' $ '*cx*' = TRUE
12)'abcxyz' $ '*a*c*y*' = TRUE
13)'abcxyz' $ 'a*b***c*z' ) = TRUE
14)'abcxyz' $ '**a*b***y*z**' ) = TRUE
15)'abcxyz' $ 'ab*x*c*yz' ) = FALSE
16)'abcxyz' $ '*cx' ) = FALSE
17)'abcxyxyz' $ '*xyz' ) = TRUE
18)'abcxyzxy' $ '*xyz' ) = FALSE
19)'abcxyzxyz' $ '*xyz' ) = TRUE
20)'abcxyzxyz' $ '*xyz*xyz' ) = TRUE
21)'' $ '?' ) = FALSE
22)'a' $ '?' ) = TRUE
23)'az' $ '?' ) = FALSE
24)'az' $ '??' ) = TRUE
25)'az' $ '?*?' ) = TRUE
26)'abyz' $ '?*?' ) = TRUE
27)'abyz' $ '?*?*' ) = TRUE
28)'abcxyzxyz' $ '*?*' ) = TRUE
29)'abcxyzxyz' $ '*xyz*?yz' ) = TRUE
30)'abcxyzxyz' $ '*?xyz*?yz' ) = TRUE
31)'abcxyzxyz' $ '?*xyz*y?' ) = TRUE
32)'abcxyzxyz' $ '*x?z' ) = TRUE
33)'abcxyzxyz' $ '*xyz*x?z' ) = TRUE
34)'abcxyzxyz' $ '*x?z*x?z' ) = TRUE
35)'abcxyzxyz' $ '*??x?z*x?z' ) = TRUE
36)'abcxyzxyz' $ '*??x?0z*x?z' ) = FALSE
37)'abcxyzxyz' $ '*??x?z?*x?z' ) = FALSE
38)'abcxyzxyz' $ '*??x?z?*?z' ) = TRUE
39)'abcxyz0xyz' $ '*??x?z?*x?z' ) = TRUE

Berserker · « **Ответ #61 :** Сентябрь 22, 2012, 07:39:59 pm »

Жаль, нельзя проверить. Раз там Оберон, может быть Оберон-07М от Рефата подошёл бы для несложного примера? Правда от возвратов с середины пришлось бы отказаться.

Kemet · « **Ответ #62 :** Сентябрь 23, 2012, 09:08:15 am »

Цитата: Berserker от Сентябрь 22, 2012, 07:39:59 pm

Жаль, нельзя проверить. Раз там Оберон, может быть Оберон-07М от Рефата подошёл бы для несложного примера? Правда от возвратов с середины пришлось бы отказаться.

Не знаю, что за 07M такой, но вроде в самом поиске-сравнении ничего сверх Оберона нет, Strings.Length можно в нужный модуль перенести или, если сравниваемые строки указаны прямо в тексте программы (как у меня в тесте), можно и просто LEN( string ), а вместо KernelLog может какой-нибудь Out пойдет. В принципе можно перевести и на Паскаль для сравнения, если будет время - займусь.
Проблему с возвратами с середины не понял.

К тому-же изначально я всё-таки делал поиск а не сравнение, а потом, преобразовал в сравнение, добавив еще один откат(если его убрать, то поиск и останется). Поэтому правильно написанному сравнению алгоритм проиграет в эффективности.

Kemet · « **Ответ #63 :** Сентябрь 24, 2012, 05:44:13 am »

Обнаружил в модуле Strings от A2 процедуру Match

Код: [Выделить]

(** Simple pattern matching with support for "*" and "?" wildcards  - returns TRUE if name matches mask. Patent pending ;-) *)
PROCEDURE Match*(CONST mask, name: ARRAY OF CHAR): BOOLEAN;
VAR m,n, om, on: LONGINT; f: BOOLEAN;
BEGIN
  m := 0; n := 0; om := -1;
  f := TRUE;
  LOOP
    IF (mask[m] = "*") THEN
      om := m; INC(m);
      WHILE (name[n] # 0X) & (name[n] # mask[m]) DO INC(n) END;
      on := n
    ELSIF (mask[m] = "?") THEN
      IF (name[n] = 0X) THEN f := FALSE; EXIT END;
      INC(m); INC(n)
    ELSE
      IF (mask[m] # name[n]) THEN
        IF (om = -1) THEN f := FALSE; EXIT
        ELSIF (name[n] # 0X) THEN (* try the next position *)
          m := om; n := on + 1;
          IF (name[n] = 0X) THEN f := FALSE; EXIT END
        ELSE
          f := FALSE; EXIT
        END
      ELSE INC(m); INC(n)
      END
    END;
    IF (mask[m] = 0X) & ((name[n] = 0X) OR (om=-1)) THEN EXIT END
  END;
  RETURN f & (name[n] = 0X)
END Match;

Результаты тестов (расхождения помечены "-" в последнем столбце).

Код: [Выделить]

 строка         шаблон             мойвар    A2    *
======================================================
 1)''           $ ''              = TRUE    ASSERT
 2)''           $ 'a'             = FALSE   FALSE
 3)''           $ '*'             = TRUE    TRUE
 4)'a'          $ ''              = FALSE   FALSE
 5)'abcxyz'     $ '*'             = TRUE    TRUE
 6)'abcxyz'     $ 'ab*'           = TRUE    TRUE
 7)'abcxyz'     $ '*ab'           = FALSE   FALSE
 8)'abcxyz'     $ '*yz'           = TRUE    TRUE
 9)'abcxyz'     $ '*yz*'          = TRUE    TRUE
10)'abcxyz'     $ 'ab*yz'         = TRUE    TRUE
11)'abcxyz'     $ '*cx*'          = TRUE    TRUE
12)'abcxyz'     $ '*a*c*y*'       = TRUE    TRUE
13)'abcxyz'     $ 'a*b***c*z'     = TRUE    FALSE -
14)'abcxyz'     $ '**a*b***y*z**' = TRUE    FALSE -
15)'abcxyz'     $ 'ab*x*c*yz'     = FALSE   FALSE
16)'abcxyz'     $ '*cx'           = FALSE   FALSE
17)'abcxyxyz'   $ '*xyz'          = TRUE    TRUE
18)'abcxyzxy'   $ '*xyz'          = FALSE   FALSE
19)'abcxyzxyz'  $ '*xyz'          = TRUE    TRUE
20)'abcxyzxyz'  $ '*xyz*xyz'      = TRUE    TRUE
21)''           $ '?'             = FALSE   FALSE
22)'a'          $ '?'             = TRUE    TRUE
23)'az'         $ '?'             = FALSE   FALSE
24)'az'         $ '??'            = TRUE    TRUE
25)'az'         $ '?*?'           = TRUE    FALSE -
26)'abyz'       $ '?*?'           = TRUE    FALSE -
27)'abyz'       $ '?*?*'          = TRUE    FALSE -
28)'abcxyzxyz'  $ '*?*'           = TRUE    FALSE -
29)'abcxyzxyz'  $ '*xyz*?yz'      = TRUE    FALSE -
30)'abcxyzxyz'  $ '*?xyz*?yz'     = TRUE    FALSE -
31)'abcxyzxyz'  $ '?*xyz*y?'      = TRUE    TRUE
32)'abcxyzxyz'  $ '*x?z'          = TRUE    TRUE
33)'abcxyzxyz'  $ '*xyz*x?z'      = TRUE    TRUE
34)'abcxyzxyz'  $ '*x?z*x?z'      = TRUE    TRUE
35)'abcxyzxyz'  $ '*??x?z*x?z'    = TRUE    FALSE -
36)'abcxyzxyz'  $ '*??x?0z*x?z'   = FALSE   FALSE
37)'abcxyzxyz'  $ '*??x?z?*x?z'   = FALSE   FALSE
38)'abcxyzxyz'  $ '*??x?z?*?z'    = TRUE    FALSE -
39)'abcxyz0xyz' $ '*??x?z?*x?z'   = TRUE    FALSE -

Berserker · « **Ответ #64 :** Сентябрь 24, 2012, 09:49:04 am »

Не совсем тривиальная задача, выходит.

ilovb · « **Ответ #65 :** Сентябрь 24, 2012, 10:35:26 am »

Щас набежит info21 и назовет разработчиков A2 мейнстримщиками, а Active Oberon неправильным обероном.

Ведь у правильных оберонщиков все работает правильно "сразу и без отладки"

Valery Solovey · « **Ответ #66 :** Сентябрь 24, 2012, 12:13:30 pm »

А вот он возьмёт и не набежит. Не будет ли стыдно предсказателю за очередное несбывшееся предсказание?

ilovb · « **Ответ #67 :** Сентябрь 24, 2012, 02:01:43 pm »

Не понял вашего негодования.

Нет, стыдно не будет. Это была шутка.

ps На каком основании вы мне клеймо "предсказателя" вешаете?
Да еще и "очередное несбывшееся"... Чем я вам насолил?

Valery Solovey · « **Ответ #68 :** Сентябрь 24, 2012, 02:32:54 pm »

Да в общем-то, никаких бурных эмоций я не испытывал при прочтении сообщения. Поэтому, нет никакого негодование, я спокоен.

Однако, если это шутка, то она не вызывает положительных эмоций.

И клейма я не ставил. Предсказание - это рассказ о том, что в будущем. Если Вам не нравится это слово, то его можно заменить на "прогноз".

ilovb · « **Ответ #69 :** Сентябрь 24, 2012, 02:57:04 pm »

Ладно. Проехали.

Geniepro · « **Ответ #70 :** Сентябрь 24, 2012, 04:35:30 pm »

До полнолуния ещё далеко, запаситесь терпением так что... ))

Илья Ермаков · « **Ответ #71 :** Сентябрь 24, 2012, 07:55:33 pm »

Цитата: ilovb от Сентябрь 24, 2012, 10:35:26 am

Щас набежит info21 и назовет разработчиков A2 мейнстримщиками, а Active Oberon неправильным обероном.

Ведь у правильных оберонщиков все работает правильно "сразу и без отладки"

Уже горел народ на том, что брал из А2 "глючащие" алгоритмы. Что-то было то ли сетевое, то ли PNG, то ли сжатие... Глючило как раз из такого многоэтажного ужаса с выходами из середины. Когда перепроектировали цикл как положено, всё стало нормально.

ilovb · « **Ответ #72 :** Сентябрь 24, 2012, 08:13:30 pm »

Мне вот любопытно. А существует ли система, которая написана грамотно? Где посмотреть на это чудо?

Ну т.е. циклы "построенные под доказательство" и все такое...

Я вот давно уже сам для себя пытаюсь понять к чему ближе программирование... к формальным методам или к производству.

То, что я каждый день наблюдаю пока много ближе именно к производству.
А как сказал один мой товарищ (бизнесмен): "Всегда будь готов к 20% брака в любом производстве".

vlad · « **Ответ #73 :** Сентябрь 24, 2012, 08:35:03 pm »

Цитата: ilovb от Сентябрь 24, 2012, 08:13:30 pm

Мне вот любопытно. А существует ли система, которая написана грамотно? Где посмотреть на это чудо?

Ну т.е. циклы "построенные под доказательство" и все такое...

Это такой тонкий троллинг?

Конечно есть!!! Оберон ОС же ш!!! И ББ же ш!!!

ilovb · « **Ответ #74 :** Сентябрь 24, 2012, 08:50:20 pm »

В чЁрной коробке говнокода хватает.

А Оберон.... ну может быть.... но есть много оговорок:
1. Система слишком маленькая, чтобы там явно выделился человеческий фактор
2. Разработчик и постановщик задачи одно лицо. Когда тебе ставит задачу другой человек (обычно не знающий программирования), то сложность возрастает на порядки.
3. Практически отсутствует сопротивление среды (требования не меняются каждый день; нет нужды реагировать на вопли пользователей)
4. и т.д.

т.е. Оберон не считается, т.к. это тепличное растение.

Oberon space

Новости:

Автор Тема: Сопоставление с образцом (Прочитано 42922 раз)

Kemet

Re: Сопоставление с образцом

Berserker

Re: Сопоставление с образцом

Kemet

Re: Сопоставление с образцом

Kemet

Re: Сопоставление с образцом

Berserker

Re: Сопоставление с образцом

ilovb

Re: Сопоставление с образцом

Valery Solovey

Re: Сопоставление с образцом

ilovb

Re: Сопоставление с образцом

Valery Solovey

Re: Сопоставление с образцом

ilovb

Re: Сопоставление с образцом

Geniepro

Re: Сопоставление с образцом

Илья Ермаков

Re: Сопоставление с образцом

ilovb

Re: Сопоставление с образцом

vlad

Re: Сопоставление с образцом

ilovb

Re: Сопоставление с образцом