Algorytmy i Struktury Danych - Dzielenie łańcucha na słowa

Operacja podziału łańcucha znaków na zawarte w nim słowa (ang. splitting into words) jest często wykonywana jako wstęp do różnych algorytmów tekstowych.

W naszym prostym algorytmie w pętli będą wydobywane kolejne słowa z łańcucha s. Słowa te mogą być następnie odpowiednio przetworzone przez inny algorytm. Zasada pracy jest następująca:

Tworzymy pusty łańcuch ss, w którym będą gromadzone znaki wydobywanego słowa. Na końcu łańcucha s umieszczamy wartownika – dowolny znak nie będący literą ani cyfrą – może to być np. spacja. Wartownik zagwarantuje nam przetworzenie wszystkich słów łańcucha s. Następnie przeglądamy kolejne znaki łańcucha s. Jeśli przeglądany znak jest literą lub cyfrą, to dołączamy go do łańcucha ss. W przeciwnym razie, jeśli łańcuch ss zawiera znaki, przetwarzamy je jako słowo, po czym łańcuch ss zerujemy – będzie on gotowy na przyjęcie nowych znaków dla kolejnego słowa.

Algorytm podziału łańcucha na słowa

Wejście:

s – łańcuch tekstowy.

Wyjście:

kolejne słowa zawarte w łańcuchu s.

Zmienne pomocnicze:

i	–	indeks znaków w łańcuchu s, i ∈ N
ss	–	łańcuch zawierający kolejne słowa z łańcucha s

Lista kroków:

K01:	ss ← ""	zerujemy łańcuch słowa
K02:	s ← s + wartownik	na końcu łańcucha s umieszczamy wartownika
K03:	Dla i = 0, 1, ..., \| s \| - 1: wykonuj kroki K04...K09	przeglądamy kolejne znaki łańcucha s
K04:	Jeśli s [ i ] = cyfra_lub_litera, to idź do kroku K09	litery i cyfry dołączamy do łańcucha ss
K05:	Jeśli ss = "", to następny obieg pętli K03	sprawdzamy, czy ss zawiera jakieś słowo
K06:	Przetwarzaj ss	przetwarzamy wydobyte słowo
K07:	ss ← ""	zerujemy ss dla następnego słowa
K08:	Następny obieg pętli K03
K09:	ss ← ss + s [ i ]	dołączamy znak s [ i ] do łańcucha ss
K10:	Zakończ

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program odczytuje wiersz znaków i wypisuje zawarte w nim słowa w klamerkach.

Pascal

// Podział łańcucha tekstowego na słowa
// Data:  6.07.2008
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------

program prg;

var
  s, ss : ansistring;
  i : integer;

begin
  readln ( s );
  ss := '';
  s := s + ' '; // dodajemy wartownika
  for i := 1 to length ( s ) do
    if s [ i ] in [ '0'..'9', '_', '-', 
                'A'..'Z', 'a'..'z', 
                'Ą', 'ą', 'Ć', 'ć', 'Ę', 'ę', 
                'Ł', 'ł', 'Ń', 'ń', 'Ó', 'ó', 
                'Ś', 'ś', 'Ź', 'ź', 'Ż', 'ż' ] then
      ss := ss + s [ i ] 
    else if ss <> '' then
    begin
      writeln ( ' [ ', ss, ' ] ' ); ss := '';
    end;
  writeln;
end.

C++

// Podział łańcucha tekstowego na słowa
// Data:  6.07.2008
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <string>

using namespace std;

int main( )
{
  string s, ss;
  int i, n;
  unsigned char c;

  getline ( cin, s );
  ss = "";
  s += " "; // dodajemy wartownika
  n = s.length( );
  for( i = 0; i < n; i++ )
  {
    c = s [ i ];
    if( ( ( c >= '0' ) && ( c <= '9' ) ) ||
          ( c == '_' ) || ( c == '-' )   ||
        ( ( c >= 'A' ) && ( c <= 'Z' ) ) ||
        ( ( c >= 'a' ) && ( c <= 'z' ) ) ||
          ( c == 164 ) || ( c == 165 )   ||
          ( c == 143 ) || ( c == 134 )   ||
          ( c == 168 ) || ( c == 169 )   ||
          ( c == 157 ) || ( c == 136 )   ||
          ( c == 227 ) || ( c == 228 )   ||
          ( c == 224 ) || ( c == 162 )   ||
          ( c == 151 ) || ( c == 152 )   ||
          ( c == 141 ) || ( c == 171 )   ||
          ( c == 189 ) || ( c == 190 ) )
      ss += c;
    else if( ss != "" )
    {
      cout << " [ " << ss << " ] \n";
      ss = "";
    }
  }
  return 0;
}

Basic

' Podział łańcucha tekstowego na słowa
' Data:  6.07.2008
' (C)2020 mgr Jerzy Wałaszek
'-----------------------------

Dim As String s, ss
Dim As Uinteger i, n, c

Line Input s
ss = ""
s += " " 'dodajemy wartownika
n = Len ( s )
For i = 1 To n
  c = Asc ( Mid ( s, i, 1 ) )
  if( ( ( c >= Asc ( "0" ) ) And ( c <= Asc ( "9" ) ) ) Or ( c = Asc ( "_" ) )  Or ( c = Asc ( "-" ) )        Or _
      ( ( c >= Asc ( "A" ) ) And ( c <= Asc ( "Z" ) ) ) Or ( ( c >= Asc ( "a" ) ) And ( c <= Asc ( "z" ) ) )  Or _
        ( c = 164 ) Or ( c = 165 )  Or ( c = 143 ) Or ( c = 134 )  Or ( c = 168 ) Or ( c = 169 )  Or _
        ( c = 157 ) Or ( c = 136 )  Or ( c = 227 ) Or ( c = 228 )  Or ( c = 224 ) Or ( c = 162 )  Or _
        ( c = 151 ) Or ( c = 152 )  Or ( c = 141 ) Or ( c = 171 )  Or ( c = 189 ) Or ( c = 190 ) ) Then
    ss += Chr ( c )
  Elseif ss <> "" Then
    Print " [ ";ss;" ] "
    ss = ""
  End If
Next
Print
End

Wynik:

Człowiek nie lubi pracować, bo i po co miałby to robić?
[ Człowiek ]
[ nie ]
[ lubi ]
[ pracować ]
[ bo ]
[ i ]
[ po ]
[ co ]
[ miałby ]
[ to ]
[ robić ]

Na początek: podrozdziału strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Dzielenie łańcucha tekstowego na słowa