Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Object Pascal: кроссплатформенные технологии > Проверка соответствия шаблону

Автор: SuicideRash 24.5.2008, 14:21

Нужно написать програму которая обробатывает 2 строки (образец и шаблон) образец состоит из больших латинских букв, шаблон - большие латинские букви плюс "?" и "*" (?-любой символ, *-любоэ количество, возможно и 0!, любых символов), и выводила "YES" если образец подходит под шаблон, "NO" - не подходит.

Подскажите идею, можна и текст программы если не тяжело smile

Автор: volvo877 24.5.2008, 15:57

Поиск по форуму уже не надо использовать?

http://forum.vingrad.ru/index.php?showtopic=37050&view=findpost&p=296681

Автор: SuicideRash 24.5.2008, 19:28

простите я не нашол... smile

Автор: SuicideRash 26.5.2008, 02:50

Предложенная тема volvo877'м довольно старая, предлагаю поднять єтот вопрос снова, так как приведьонные в ней примеры решений мне удалось очень быстро опровергнут такими примерами:
Строка:
ABBCDPCDA
Шаблон:
A*CDA
Ответ:
должно быть да но выдайот нет
Строка:
ABBCDA
Шаблон
A*CDAK
Ответ:
должно быть нет но выдайот да.
(каждая из 3 програм дайот збой на одном из этих примеров).
У ково есть какие идеи?
У меня есть одна, если получица то виложу результат...

Автор: mmvds 26.5.2008, 12:02

Строка:
ABBCDPCDA
Шаблон:
A*CDA
Почему это должно быть да? Еслибы шаблон был A*CD*A тогда да, а так нет

Добавлено, а, все, вижу, в конце CDA

Автор: volvo877 26.5.2008, 13:56

SuicideRash, погоняй-ка вот это:

Код

{$B-}
function Match(s, wildcard: string): boolean;
begin
  if wildcard = '' then Match := (s = '')
  else
    case wildcard[1] of
      '*' :
        Match := Match(s, copy(wildcard, 2, 255)) or
          ((s <> '') and Match(copy(s, 2, 255), wildcard));
      '?' :
        Match := (s <> '') and
          (Match(copy(s, 2, 255), copy(wildcard, 2, 255)));
      else
        Match := (s[1] = wildcard[1]) and
          (Match(copy(s, 2, 255), copy(wildcard, 2, 255)));
    end;
end;

begin
  writeln(Match('ABBCDA', 'A*CDAK'), '--> FALSE');
  writeln(Match('ABBCDPCDA', 'A*CDA'), '--> TRUE');
end.

(работать именно в режиме {$B-}, иначе будет переполнение стека!!!)

Автор: SuicideRash 26.5.2008, 19:29

volvo877 а ти сам её тестировал???
если чесно то я шото не совсем понял как оно проверять будет, а потестировать нет времемни сейчас... как появица обезательно напишу smile

З.Ы. надеюсь она рабочая )

Автор: Filon 26.5.2008, 20:52

Цитата(volvo877 @ 26.5.2008, 11:56)

SuicideRash, погоняй-ка вот это
(работать именно в режиме {$B-}, иначе будет переполнение стека!!!)

Алгоритм правильный, но не лучший в реализации. При длинных исходных строках стек переполняется, даже с {$B-}. Завтра, если будет время, напишу алгоритм без рекурсий.

Автор: volvo877 26.5.2008, 21:01

В заголовке добавляем const

Код


function Match(const s, wildcard: string): boolean;

Цитата(Filon @ 26.5.2008, 20:52

)

При длинных исходных строках стек переполняется, даже с {$B-}.

140 символов - достаточно длинная строка? Переполнения стека на подобных размерах не замечено (стек установлен в 32К по умолчанию, TP 7)

Прежде, чем придумывать самостоятельно - сначала лучше посмотреть то, что есть готовое, ибо изобретение велосипедов - занятие неблагодарное:
http://xoomer.alice.it/acantato/dev/wildcard/wildmatch.html

Автор: Filon 27.5.2008, 08:54

Цитата(volvo877 @ 26.5.2008, 19:01)

140 символов - достаточно длинная строка? Переполнения стека на подобных размерах не замечено (стек установлен в 32К по умолчанию, TP 7)

Боюсь я испоречен олимпиадным программированием smile

Для меня длинная строка - это строка длиной, например, 500 символов smile

Автор: volvo877 27.5.2008, 09:13

Цитата(Filon @ 27.5.2008, 08:54

)

Для меня длинная строка - это строка длиной, например, 500 символов

Тогда, боюсь, в раздел Паскаль тебе лучше не заходить, ибо паскалевский String ограничен всего 255 символами, и если ты этого не знаешь - ...

Автор: Filon 27.5.2008, 15:29

Цитата(volvo877 @ 27.5.2008, 07:13)

Я прекрасно знаю, что String ограничен 255 символами. Но мое понимание термина "строка" шире, чем просто паскалевский тип String. Строка может быть представлена и массивом char`ов.
Вообще, думаю, что это мало относится в теме. Так что предлагаю свернуть наш спор smile