% -*- coding: iso-8859-2 -*-
\documentclass[a4paper]{article}
\usepackage{progm}
\analpacks
\analoldal{3. feladatsor, 14-15. feladat, adatabsztarkcióval}
\begin{document}
\noindent

\emph{Feladat:} Adott egy szöveg, ami mondatokból áll, és a mondatok
végén pont van. Módosítsuk a szöveget úgy, hogy minden mondat végét
jelző pontot pontosvesszőre cserélünk!  A mondatokban lehetnek
idézetek, és az idézetek is tartalmazhatnak idézeteket tetszőleges
mélységben (az idézetet egy kezdőidézőjel vezeti be és egy
záróidézőjel jelzi a végét). Azok a pontok, amelyek egy idézet
belsejében vannak, nem jelentik a mondat végét! Feltesszük, hogy a
szövegben az idézőjelek kiegyensúlyozottak.

\emph{Feladat:} Adott az $x$ sorozat, ami egy szöveget
tartalmaz. Másoljuk át $x$-et a $z$ sorozatba úgy, hogy a kerek
zárójelek közé írt szöveget elhagyjuk! (A zárójelekkel együtt.)
Feltesszük, hogy a szövegben a zárójelek kiegyensúlyozottak.

\emph{Megoldás:} A két feladathoz megpróbálunk egy olyan közös
absztrakt teret keresni, ami fölött megoldhatók.  Ehhez előszöris
tekintsünk el attól a lényegtelen különbségtől, hogy az első feladat
idézőjelekről beszél.  A megoldásban mindenhol zárójeleket használunk
majd és természetesen kicserélhető ez bármilyen nyitó- és zárójelre,
amit éppen a feladatunk megkíván.  Másodszor pedig az absztrakciót egy
$sx,dx,x:\Read$ művelettel olvasott konkrét file felé készítjük el,
hiszen az $x$ sorozat a read definiciójának a segítségével tekinthető
ilyennek.

$\alatt{F}{x} = \file(Ch)$\\
$\alatt{F'}{t} = \file((b:Ch, d:N_0))$

Tehát a $t$ absztrakt file-ban karakter--természetes rekordok sorozata
szerepel, nem csak karakterek.  Minden természetes szám azt
tartalmazza, hogy annak a karakternek a feldolgozása után
zárójelezettség tekintetében a szövegnek milyen a ``mélysége''.
Például az $<a,b,(,c,d,(,),e,)>$ konkrét file-hoz a $t$ file a $<a0,
b0, (1, c1, d1, (2, )1, e1, )0>$.  Formálisan:

$dom(t)=dom(x) \es \forall i\in[1, dom(t)]: t_i:=(x_i, t_{i-1}+\chi(x_i=\text{,,}(\text{''})-\chi(x_i=\text{,,})\text{''}))$

Az alábbi open$(t)$-vel és read-del érhető el ez az absztrakció:
\begin{center}
\begin{tabular}{ccc}
\parbox{3cm}{
\begin{stukibox*}[3cm]{open($t$)}
  \stm{sx,dx,x:\Read}
  \stm{dt.d:=0}
\end{stukibox*} \vspace{5cm}} & \hbox{\hspace{2cm}} &
\begin{stukibox*}[8cm]{$st,dt,t:$read}
  \begin{IF}[70]{7}{\stm{sx=\norm}}
    \stm{st:=\norm}
    \stm{dt.b:=dx}
    \begin{IF}{1}{\stm{dt.b=\text{,,}(\text{''}}}
      \stm{dt.d:=dt.d+1}
      \ELSE
      \SKIP
    \end{IF}
    \begin{IF}{1}{\stm{dt.b=\text{,,})\text{''}}}
      \stm{dt.d:=dt.d-1}
      \ELSE
      \SKIP
    \end{IF}
    \stm{sx,dx,x:\Read}
    \ELSE
    \stm{st:=\abnorm}
  \end{IF}
\end{stukibox*}
\end{tabular}
\end{center}
\vspace{-3cm}

Ezen az állapottéren az első feladat megoldása az elemenkénti feldolgozásra vezethető vissza.

$A = \alatt{\F'}{y} \times \alatt{\F}{y}$\\
$B = \alatt{\F'}{y'}$\\
$Q = ( t=t' )$\\
$R = ( y=f(t'))$, ahol $f$ egy elemet feldolgozó változata:
$\Tilde f(\{e\}):=\begin{cases}
  \{e.b\} & \text{, ha } e.b\ne\text{,,}.\text{''} \vagy e.d\ne 0\\
  \{\text{,,};\text{''}\} & \text{, ha } e.d = 0  \es e.b= \text{,,}.\text{''}
\end{cases}$

\begin{stuki}[6cm]
  \stm{y:=<>}
  \stm{st,dt,t:\Read}
  \begin{WHILE}{3}{\stm{st}}
    \begin{IF}{1}{\stm{dt.b\ne\text{,,}.\text{''} \vagy dt.d\ne 0}}
      \stm{y:\hiext(dt.b)}
      \ELSE
      \stm{y:\hiext(\text{,,};\text{''})}
    \end{IF}
    \stm{dt,dt,t:\Read}
  \end{WHILE}
\end{stuki}

A második feladat ugyanígy elemenkénti feldolgozás:

$A = \alatt{\F'}{y} \times \alatt{\F}{y}$\\
$B = \alatt{\F'}{y'}$\\
$Q = ( t=t' )$\\
$R = ( y=f(t'))$, ahol $f$ egy elemet feldolgozó változata:
$\Tilde f(\{e\}):=\begin{cases}
  \{e.b\} & \text{, ha } e.d=0 \es e.b\ne \text{,,})\text{''}\\
  \varnothing & \text{, ha } e.d\ne0 \vagy e.b=\text{,,})\text{''}\\
\end{cases}$

Vegyük észre, hogy a zárójel bezárása után a számláló már 0, de mi azt
a zárójelet mégsem akarjuk már kiírni, ezért kell ezt a feltételt is
belevenni a feldolgozásba.

\begin{stuki}[6cm]
  \stm{y:=<>}
  \stm{st,dt,t:\Read}
  \begin{WHILE}{3}{\stm{st}}
    \begin{IF}{1}{\stm{dt.d\ne 0 \vagy dt.b=\text{,,})\text{''}}}
      \SKIP
      \ELSE
      \stm{y:\hiext(dt.b)}
    \end{IF}
    \stm{dt,dt,t:\Read}
  \end{WHILE}
\end{stuki}

Ezzel az absztrakcióval könnyen megoldható az a feladat is, ami
megállapítja, hogy egy szövegben a zárójelezés egyensúlyozott-e.
Lineárisan keresni kell az első olyan értéket, ahol a $d$ komponens
negatív.  Ha találunk ilyet, akkor nem kiegyensúlyozott.  Ha a keresés
végén a $d$ érték 0, akkor kiegyensúlyozott.
\end{document}