Трансформисање стрингова¶

Пример - Приказивање садржаја књиге¶

Дати су називи поглавља књиге у облику низа стрингова, и почетне странице тих поглавља као низ целих бројева. Приказати садржај те књиге, тако да је у сваком реду приказан наслов једног поглавља и почетна страница, са тачкицама између. Између наслова и тачкица треба да постоји један размак, а између тачкица и броја странице ниједан.

Да не бисмо повећавали програм разним детаљима познатим од раније, овде ћемо да издвојимо само начин приказивања садржаја (прескочили смо учитавање, одређивање укупне дужине приказа и сличне споредне детаље).

Тачкице можемо да убацимо испред броја претварањем, тј. конверзијом броја у стринг (метод ToString) и допуњавањем добијеног стринга слева (метод PadLeft).

Програм исписује

Уводно поглавље ...........................................11
Поглавље са примерима .....................................17
Поглавље са задацима са вежбу .............................25

Пример - Анализа садржаја књиге¶

Дат је низ стрингова у коме се налази садржај књиге, попут оног исписаног у претходом примеру. Сваки стринг садржи редом наслов поглавља, тачкице и назив стране на којој поглавље почиње. Између наслова и тачкица се налази један размак, а између тачкица и броја странице ниједан.

Издвојити називе поглавља и почетне странице, а затим за свако поглавље осим последњег исписати колико има страница.

У овом примеру радимо обрнуто, тј. из формираног садржаја издвајамо делове који га чине. Поново ћемо изоставити учитавање и друге од раније познате детаље, да би фокус био на трансформисању стрингова. Методом LastIndexOf можемо да добијемо позицију последњег размака у стрингу, а то је онај који претходи тачкицама. Знајући ту позицију, методом Substring лако издвајамо део до ње и део од ње. На крају из дела од последњег размака од краја стринга уклањамо тачкице методом TrimStart, а оно што преостане конвертујемо у број.

Програм исписује

Уводно поглавље има 6 страница.
Поглавље са примерима има 8 страница.

Можемо да приметимо да су неки од ових метода једни другима у неком смислу инверзни. На пример, метод PadLeft дописује потребан број пута задати знак на почетак полазног стринга, а метод TrimStart уклања сва појављивања задатог знака са почетка полазног стринга. Методи PadRight и TrimEnd су у истом међусобном односу, само се код њих ради о дописивању и уклањању на крају, а не на почетку стринга. Слично томе:

• метод Insert убацује нови део у полазни стринг, а метод Remove избацује део из њега

• метод ToLower конвертује стринг у мала, а метод ToUpper у велика слова

• метод Split користи дати раздвајач да од једног стринга направи низ стрингова, а метод Join обрнуто, спаја низ стрингова у један стринг, убацујући дати раздвајач између делова

Ако захтеви задатка допуштају, боље је да уместо позива метода Remove и Insert једног за другим на истој позицији, користимо метод Replace, нарочито ако је исту замену потребно извршити више пута. На пример, ако су вредности стрингова

string s = "Janko voli da programira, a Vasa voli da idejno resava zadatke.";
string nadji = "voli da";
string zameni = "rado";

онда је уместо

while (s.Contains(nadji))
{
    int p = s.IndexOf(nadji);
    s = s.Remove(p, nadji.Length);
    s = s.Insert(p, zameni);
}

знато боље (краће и ефикасније)

s = s.Replace(nadji, zameni);

Методе Insert и Remove свакако можемо да користимо када су нам потребни независно један од другог. Ови методи су врло удобни за једнократне (или малобројне) употребе, као и за употребе на кратким стринговима, какви се често срећу у разним примењеним програмима. Ипак, треба имати на уму да њихова вишеструка примена на стрингу велике дужине може да буде прилично спора, јер се сваки пут формира нови стринг. У таквим, алгоритамски оријентисаним задацима, поступак у неким случајевима може значајно да се убрза ако стринг конвертујемо у низ карактера и на датом низу изведемо потребне трансформације у месту (енгл. in place), тј. не заузимајући нову меморију. Наравно, треба водити рачуна и о укупном броју операција.

Пример - Парна и непарна појављивања¶

Трансформисати дати стринг тако да се непарна појављивања цртице (минуса) у њему замењују доњом цртом, а парна појављивања плусом.

На пример, за дати стринг 1-2-abc-xyz-...- добија се резултат 1_2+abc_xyz+..._.

Задатак може да се реши помоћу метода IndexOf, Remove и Insert, али то решење би могло да буде неефикасно. У овом случају, решење помоћу низа карактера је једноставно јер су стринг који тражимо и обе замене исте дужине (овде дужине 1).

Програм исписује

neki_dugacak+tekst_sa+mnogo_crtica

Пример - Замене различите дужине¶

Трансформисати дати стринг тако да се непарна појављивања цртице (минуса) у њему замењују двема доњим цртaма, а парна појављивања плусом.

У овом случају је једна од замена дужа него стринг који тражимо. Без обзира на то, задатак и у овом случају може да се реши ефикасно (у линеарном времену), и то чак на различине начине.

Једно решење се заснива на употреби објекта StringBuilder (градитељ стринга). Овај објекат је помињан и коришћен и у курсу за први разред. Подсетимо се, градитељ стринга се користи када желимо да избегнемо вишеструко понављање наредбе облика s += s1;. При сваком извршавању ове наредбе се преписује садржај оба стринга, што значи да је време њеног извршавања сразмерно збиру дужина стрингова s и s1. Како стринг s постаје све дужи, долази до вишестуког преписивања његовог почетка и због тога је вишеструко понављање наредбе облика s += s1; потенцијално веома споро. Конкретније, ако претпоставимо да се стринг s1 састоји од само једног знака, али се наредба s += s1; извршава \(n\) пута, укупно време свих извршавања те наредбе је сразмерно са \(n^2\).

Употебом градитеља стринга, наредба s += s1; се замењује наредбом sb.Append(s1);. Ова наредба не захтева преписивање садржаја sb сваки пут, већ само када простор резервисан у градитељу стринга није довољан за дописивање стринга s1, то је врло ретко. Захваљујући томе, у претходно описаном случају укупно време извршавања наредбе sb.Append(s1); би било сразмерно са \(n\) (а не са \(n^2\)).

Ево како би изгледало описано решење:

Замените наредбу

string s = "neki-dugacak-tekst-sa-mnogo-crtica";

наредбом

string s = new string('-', 500000);

а затим упоредите време извршавања тако добијеног програма са програмом који не користи градитељ стринга, већ дописује садржај у променљиву типа стринг. Колика времена извршавања сте добили?

Комплетности ради, напомињемо да задатак може да се реши ефикасно и без употребе градитеља стринга. Такво решење захтева да се прво одреди дужина резултујућег стринга и да се алоцира низ карактера те дужине. Ово може да се ефикасно обави вишеструком применом метода IndexOf. Након тога, уместо да дописујемо садржај у градитељ стринга, можемо истим садржајем да попуњавамо алоцирани низ карактера. Овај низ након попуњавања претварамо у стринг. Ево како би у овом случају изгледала функција Zameni.

Уверите се анализом алгоритма или мерењем времена да је и код овог решења време извршавања линеарно, тј. сразмерно дужини резултујућег стринга.

Више задатака можете да нађете на страници Стрингови и регуларни изрази - задаци, после лекција о регуларним изразима.