Rešitev: Ujemanje niza z vzorcem (Mathematica)

Iz MaFiRaWiki

Naloga: Ujemanje niza z vzorcem


Clear[ujemanje]

ujemanje::usage =
 "Funkcija ujemanje[Niz,Vzorec,s,v] vrne True, če se del niza Niz od položaja s naprej 
  ujema z delom vzorca Vzorec od položaja v naprej. Sicer vrne False. 
  V vzorcu lahko nastopata še posebna simbola :
     *, ki se lahko ujema s poljubnim zaporedjem nič ali več znakov v nizu, in 
     ?, ki se lahko ujema s poljubnim posamičnim znakom v nizu.";

  Iščemo ujemanje[Niz, Vzorec, 1, 1], ki nam pove ali se niz ujema z vzorcem. 


    1. Prišli smo do konca vzorca. Če smo prišli tudi do konca niza vrnemo True, sicer False. 

   
    ujemanje[Niz_String, Vzorec_String, s_Integer, v_Integer] /; v > StringLength[Vzorec] :=
          ujemanje[Niz, Vzorec, s, v] /; v > StringLength[Vzorec] = s > StringLength[Niz]


    2. V vzorcu naletimo na "*". Poskusimo z "*" pokriti 0, 1, 2, ... 
       znakov niza in zato preverimo vse možnosti. 
       Če ena od možnosti vrne True, se ok nastavi na True, zanka se prekine in vrnemo True.
       Če pa v nobeni od možnosti ne dobimo True,  enkrat pridemo čez cel niz in zato se zanka prekine.
       Nato vrnemo False. (ok je bil namreč pred zanko nastavljen na False in se v zanki ni nikoli popravil). 
        
        
    ujemanje[Niz_String, Vzorec_String, s_Integer, v_Integer] /;StringTake[Vzorec, {v}] == "*" :=
          ujemanje[Niz, Vzorec, s, v] /; StringTake[Vzorec, {v}] == "*" = 
                       Module[{ss, ok},
                       ss = s - 1;
                       ok = False;
                       While[Not[ok] && (ss ≤ StringLength[Niz]),
                       ss = ss + 1;
                       ok = ujemanje[Niz, Vzorec, ss, v + 1]
                         ];
                  Return[ok]
               ]


    3. Če se znaka na položajih s v nizu in v vzorcu ujemata ali če v vzorcu naletimo na "?", 
       se niz in vzorec doslej ujemata in zato se lahko pomaknemo za eno mesto  naprej.
        
        
    ujemanje[Niz_String, Vzorec_String, s_Integer,v_Integer] /; 
             s ≤ StringLength[Niz] && 
             ((StringTake[Vzorec, {v}] == "?") ||
              (StringTake[Vzorec, {v}] == StringTake[Niz, {s}])) :=
                   ujemanje[Niz, Vzorec, s, v] /;
                    s ≤ StringLength[Niz] &&((StringTake[Vzorec, {v}] == "?") || 
                   (StringTake[Vzorec, {v}] == StringTake[Niz, {s}])) = 
                   ujemanje[Niz, Vzorec, s + 1, v + 1]


    4. Nobena od dopustnih možnosti se ne zgodi, torej vrnemo False. 
     
    ujemanje[Niz_String, Vzorec_String, s_Integer, v_Integer] := ujemanje[Niz, Vzorec, s, v] = False

Primeri

Clear[Niz, Vzorec1]
Niz = "abcde";
Vzorec1 = "ab*e";
ujemanje[Niz, Vzorec1, 1, 1] ... Vrne rešitev True
Clear[Vzorec2]
Vzorec2 = "*c*d*e";
ujemanje[Niz, Vzorec2, 1, 1] ... Vrne rešitev True
Clear[Vzorec3]
Vzorec3 = "a?c*";
ujemanje[Niz, Vzorec3, 1, 1] ... Vrne rešitev True
Clear[Vzorec4]
Vzorec4 = "*??b*";
ujemanje[Niz, Vzorec4, 1, 1] ... Vrne rešitev False
Osebna orodja