Umu logo Umeå universitet
Teknisk-naturvetenskaplig fakultet
Institutionen för datavetenskap


        


Kurs: Datavetenskap A1-Moment 1
Laboration nr: 0
Namn: Lena Kallin
Användarnamn: kallin
Inlämningsdatum: 95-01-18
Sökväg: ~c97xxx/edu/ml/maze.ml

        



Innehållsförteckning

Åtkomst och användarhandledning
Problemspecifikation
Algoritmbeskrivning
Exempel på hur algoritmen fungerar för några strängar:
Systembeskrivning
Dataflödet
Beskrivning
Problem och reflektioner
Lösningens begränsningar
Testkörningar
Källkod

Åtkomst och användarhandledning

Programmet finns under katalogen ~kallin/pascal/lab1/, programmet är skrivet i Borland Pascal 7.0 under Windows. Den körbara filen heter PARSER.EXE.

När man startar programmet visas texten Skriv sträng: på skärmen. Mata då in den sträng som ska testas. Programmet skriver ut eventuella felmeddelanden och avslutas sedan.


Problemspecifikation

Uppgiften var att skriva en parser som tar en sträng med parenteser av typen (, ), [ eller ] och den skulle sedan kontrollera att strängen följer följande regler:

Det ska finnas lika många höger- som vänsterparenteser av varje slag.

Räknat från vänster får aldrig antalet högerparenteser av någon sort överstiga antalet vänster parenteser av samma sort.

Parenteserna måste vara korrekt nästlade. ( [ ) ] är ett exempel på felaktigt nästlade parenteser.

Om det upptäcks ett fel så ska ett lämpligt felmeddelande skrivas ut.

Jag har utökat uppgiften så att den även klarar av att kontrollera parenteser av typen { }. Dessutom hoppar programmet över alla tecken som inte är parenteser i strängen. Detta medför att det går bra att skriva in uttryck som t ex 3*sin(a(x+c)).


Algoritmbeskrivning

Programmet kontrollerar strängen enligt följande algoritm:

Indata: En sträng med tecken.

Utdata: En stack som ska vara tom om allt gått bra.

1 Börja med en tom stack.
2 Gör följande för alla tecken c i strängen från vänster till höger:
2.1 Om c är en vänsterparentes så lägg c på stacken.
2.2 Annars: Om c är en högerparentes gör följande:
2.2.1 Om stacken är tom:
2.2.1.1 Ge felmeddelandet "Oväntad parentes".
2.2.1.2 Avbryt programmet.
2.2.2 Om den vänsterparentes som ligger överst på stacken inte är av samma typ som högerparentesen c så gör följande:
2.2.2.1 Skriv felmeddelandet " Förväntad x" där x är den högerparentes som svarar mot vänsterparentesen på toppen av stacken.
2.2.2.2 Avbryt programmet.
2.2.3 Tag bort översta elementet från stacken.
3 Om stacken inte är tom skriv felmeddelandet "Förväntad x" där x är den högerparentes som svarar mot vänsterparentesen på toppen av stacken.

Exempel på hur algoritmen fungerar för några strängar:

$ i STACK-kolumnen står för botten på stacken medan det står för slutet på input i INDATA-kolumnen.

STACK	INDATA
$	(($
$(	 ($
$((	  $
Felmeddelande: Förväntad ). Strängen tog slut men stacken var inte tom.

STACK	INDATA
$	()$
$(	 )$
$	  $
(Inget meddelande eftersom strängen var korrekt.)

STACK	INDATA
$	())$
$(	 ))$
$	  )$
Felmeddelande: Oväntad parentes. Högerparentes hittas då stacken är tom.

Systembeskrivning

Jag har skapat en abstrakt datatyp Stack som ser ut så här:


Stack = record
            elem     : ARRAY[1..StackSize] OF Char;
            topIndex : Integer;
        end;

StackSize är storleken på stacken som kan förändras, man måste dock kompilera om koden efter man gjort förändringen. Anledningen till att jag skapade en stack är att det är en bra datatyp när man ska gå igenom en text och vill kunna titta tillbaka på det senaste tecknet.

Den abstrakta datatypens operationer har jag samlat i en unit som heter StackADT, lösningen av problemet ligger i ett program som heter Parser.


Dataflödet



Beskrivning

StackADT

procedure Empty(var s:Stack)
Syfte: Skapar en tom stack eller tömmer en redan skapad stack.
Parametrar:s är den stack som ska skapas eller tömmas.

function IsEmpty(s:Stack):Boolean
Syfte: Avgör om en stack är tom eller inte. Returnerar true om stacken är tom annars false.
Parametrar:s är den stack som ska testas.

procedure Push(c:Char; var s:Stack)
Syfte: Lägger in ett nytt tecken överst i en stack.
Krav: Då rutinen anropas måste stacken innehålla färre än StackSize element. StackSize är en konstant som definieras i uniten StackADT.)
Parametrar:c är tecknet som ska läggas på stacken.
s är den stack som tecknet ska läggas på.

function Top(s:Stack):Char
Syfte: Ger det översta elementet i en stack. Stacken förändras inte.
Krav: Stacken får inte vara tom när funktionen anropas.
Parametrar: s är den stack som tecknet ska hämtas från.

procedure Pop(var s:Stack)
Syfte: Tar bort det översta elementet i en stack.
Krav: Stacken får inte vara tom när funktionen anropas.
Parametrar: s är den stack som ska ändras.


Parser

procedure Error(x: Integer; message: String)
Syfte: Skriver ut ett felmeddelande på aktuell rad på skärmen. Avbryter sedan exekveringen.
Parametrar:x är den x-koordinat på aktuell rad där meddelandet ska skrivas.
message är det felmeddelande som ska skrivas ut.

function Match(left:Char):Char
Syfte: Ger den högerparentes som hör ihop med en speciell typ av vänsterparentes.
Parametrar: left kan antingen vara `(`, `{` eller `[` och anger vilken typ av vänsterparentes som önskas.

procedure Parse(s: String)
Syfte: Undersöker om en textsträng innehåller parenteser på godkänd form (enligt problemspecifikationen). Om så inte är fallet ska ett felmeddelande visas och programmet avbrytas.
Parametrar: s är den sträng som ska testas.


Problem och reflektioner

Det första problemet som jag stötte på var vilken datatyp jag skulle välja men efter att ha gjort flera exempel på papper så insåg jag att en stack var en lyckad lösning. Jag ville göra så allmänna funktioner och procedurer som möjligt så därför skrev jag en procedur som tog en x-koordinat och en text och som sedan skrev ut texten på den aktuella raden med start på den angivna positionen. Denna procedur kan man säkert använda i flera program. Stacken kan man också använda i alla program där man behöver en stack av tecken.

Uppgiften var rolig och det var ett bra exempel på vad man kan använda en stack till.

Lösningens begränsningar

Jag valde att implementera stacken som en array och det medför att man inför en begränsning på hur djupt parenteserna kan vara nästlade. Jag tror dock att det är ovanligt med uttryck som har fler än 20 nästlingar och anser att begränsningen inte är så allvarlig. Om man istället implementerade stacken som en enkellänkad lista så skulle begränsningen undvikas.

Om man matar in uttryck som är längre än en rad på skärmen så kan felmeddelanderna som skrivs ut hamna på fel ställe. Det är inte så bra men jag har inte kommit på hur man ska kunna lösa det ännu.

Ett alternativt sätt att lösa problemet på hade varit att använda rekursion istället för att skriva en egen stack.

Testkörningar

(([]])
    ^ Förväntad )        
(([]([))))
      ^ Förväntad ]
([])(([])))
          ^ Oväntad parentes
(()
   ^ Förväntad parentes
)))
^ Oväntad parentes
3 sin(4x+5(x+k)
               ^ Förväntad )

Källkod

StackADT:
unit StackADT;

{Unit för stackar som innehåller tecken}

interface

const StackSize = 20 {Maximala antalet tecken i stacken}

type Stack = record
              elem  : ARRAY[1..StackSize] OF Char;
              topIndex  : Integer;
              end;

procedure Empty(var s:Stack)
{Skapar en tom stack  s eller tömmer en redan skapad stack s}

function IsEmpty(s:Stack):Boolean
{Returnerar true om stacken s är tom annars false}

procedure Push(c:Char; var s:Stack)
{ Lägger in teckenet c överst i stacken s. Då rutinen anropas
måste stacken innehålla färre än StackSize element. }

function Top(s:Stack):Char
{Returnerar det översta elementet i en stack. Stacken får inte vara
tom när funktionen anropas.}

procedure Pop(var s:Stack)
{Tar bort det översta elementet från stacken s. Stacken får
inte vara tom när funktionen anropas.}

implementation

procedure Empty(var s:Stack)
{Skapar en tom stack  s eller tömmer en redan skapad stack s}
begin
  s.topIndex:= 0;
end;

function IsEmpty(s:Stack):Boolean
{Returnerar true om stacken s är tom annars false}
begin
  IsEmpty:= s.topIndex < 1;
end;

procedure Push(c:Char; var s:Stack)
{ Lägger in teckenet c överst i stacken s. Då rutinen anropas
måste stacken innehålla färre än StackSize element. }
begin
  {Öka antalet element i stacken}
  s.topIndex:= s.topIndex + 1;
  {Kontrollera att stacken inte är full}  
  if s.topIndex in [1..StackSize] then
    s.elem[s.topIndex]:= c; {Lägg in elementet}
end;

function Top(s:Stack):Char
{Returnerar det översta elementet i en stack. Stacken får inte vara
tom när funktionen anropas.}
begin
  Top:= s.elem[s.topIndex];
end;

procedure Pop(var s:Stack)
{Tar bort det översta elementet från stacken s. Stacken får
inte vara tom när funktionen anropas.}
begin
  {Minska antalet element i stacken}
  s.topIndex:= s.topIndex - 1;
end;

end. 

Parser

program parser;
{Kontrollerar att en sträng med parenteser är på en given
form.}

uses WinCrt, StackADT;

procedure Error(x: Integer; message: String)
{Skriver ut felmeddelandet message på x-koordinaten x på aktuell
rad. Avbryter sedan exekveringen.}
begin 
  GotoXY(X, WhereY);   {Flytta markören till rätt position}
  writeln(message);
  Halt;    {Avbryt programmet}
end;

function Match(left:Char):Char
{Givet en vänsterparentes left returnera den högerparentes som
hör passar.}
begin
  case left of
    `(`: Match := `)';
    `[`: Match := `]';
    `{`: Match := `}';
  else Match := ` `; {Om det ej är någon parentes returnera blank} 
  end;
end;

procedure Parse(s: String)
{Undersöker om en textsträng innehåller parenteser på
godkänd form}
var   chStack  : Stack;
      i    : integer; {i står för aktuell position i strängen}
begin
  Empty(chStack);            {Skapa en tom stack}
  for i:= 1 to length(s) do {Gå igenom strängen tecken för
tecken}
    case s[i] of
      `(`, `[`, `{` : Push(s[i],chStack); {Lägg dem på stacken}
      `)`, `]`, `}` : If IsEmpty(chStack) then 
        	              {Högerparentes och tom stack}
	                      Error(i, `^ Oväntad parentes') 
                      else if s[i] <> Match(Top(chStack)) then 
                	      {Felaktig högerparentes}
                      	      Error(i, `^ Förväntad' + Match(Top(chStack)))
                    	   else Pop(chStack); {Korrekt högerparentes}
     end;
  if not IsEmpty(chStack) then    {Strängen är slut men stacken är inte tom}
    Error(length(s)+1, `^ Förväntad' + Match(Top(chStack)))
end;
  
var str:String;

begin
  writeln(`Skriv sträng');
  readln(s);
  Parse(s);
end.