102 lines
2.4 KiB
Text
102 lines
2.4 KiB
Text
MODULE BalancedBrackets;
|
|
IMPORT
|
|
Object,
|
|
Object:Boxed,
|
|
ADT:LinkedList,
|
|
ADT:Storable,
|
|
IO,
|
|
Out := NPCT:Console;
|
|
|
|
TYPE
|
|
(* CHAR is not boxed in the standard lib *)
|
|
(* so make a boxed char *)
|
|
Character* = POINTER TO CharacterDesc;
|
|
CharacterDesc* = RECORD
|
|
(Boxed.ObjectDesc)
|
|
c: CHAR;
|
|
END;
|
|
|
|
(* Method for a boxed char *)
|
|
PROCEDURE (c: Character) INIT*(x: CHAR);
|
|
BEGIN
|
|
c.c := x;
|
|
END INIT;
|
|
|
|
PROCEDURE NewCharacter*(c: CHAR): Character;
|
|
VAR
|
|
x: Character;
|
|
BEGIN
|
|
NEW(x);x.INIT(c);RETURN x
|
|
END NewCharacter;
|
|
|
|
PROCEDURE (c: Character) ToString*(): STRING;
|
|
BEGIN
|
|
RETURN Object.NewLatin1Char(c.c);
|
|
END ToString;
|
|
|
|
PROCEDURE (c: Character) Load*(r: Storable.Reader) RAISES IO.Error;
|
|
BEGIN
|
|
r.ReadChar(c.c);
|
|
END Load;
|
|
|
|
PROCEDURE (c: Character) Store*(w: Storable.Writer) RAISES IO.Error;
|
|
BEGIN
|
|
w.WriteChar(c.c);
|
|
END Store;
|
|
|
|
PROCEDURE (c: Character) Cmp*(o: Object.Object): LONGINT;
|
|
BEGIN
|
|
IF c.c < o(Character).c THEN RETURN -1
|
|
ELSIF c.c = o(Character).c THEN RETURN 0
|
|
ELSE RETURN 1
|
|
END
|
|
END Cmp;
|
|
(* end of methods for a boxed char *)
|
|
|
|
PROCEDURE CheckBalance(str: STRING): BOOLEAN;
|
|
VAR
|
|
s: LinkedList.LinkedList(Character);
|
|
chars: Object.CharsLatin1;
|
|
n, x: Boxed.Object;
|
|
i,len: LONGINT;
|
|
BEGIN
|
|
i := 0;
|
|
chars := str(Object.String8).CharsLatin1();
|
|
len := str.length;
|
|
s := NEW(LinkedList.LinkedList(Character));
|
|
WHILE (i < len) & (chars[i] # 0X) DO
|
|
IF s.IsEmpty() THEN
|
|
s.Append(NewCharacter(chars[i])) (* Push character *)
|
|
ELSE
|
|
n := s.GetLast(); (* top character *)
|
|
WITH
|
|
n: Character DO
|
|
IF (chars[i] = ']') & (n.c = '[') THEN
|
|
x := s.RemoveLast(); (* Pop character *)
|
|
x := NIL
|
|
ELSE
|
|
s.Append(NewCharacter(chars[i]))
|
|
END
|
|
ELSE RETURN FALSE
|
|
END (* WITH *)
|
|
END;
|
|
INC(i)
|
|
END;
|
|
RETURN s.IsEmpty()
|
|
END CheckBalance;
|
|
|
|
PROCEDURE Do;
|
|
VAR
|
|
str: STRING;
|
|
BEGIN
|
|
str := "[]";Out.String(str + ":> "); Out.Bool(CheckBalance(str));Out.Ln;
|
|
str := "[][]";Out.String(str + ":> ");Out.Bool(CheckBalance(str));Out.Ln;
|
|
str := "[[][]]";Out.String(str + ":> ");Out.Bool(CheckBalance(str));Out.Ln;
|
|
str := "][";Out.String(str + ":> ");Out.Bool(CheckBalance(str));Out.Ln;
|
|
str := "][][";Out.String(str + ":> ");Out.Bool(CheckBalance(str));Out.Ln;
|
|
str := "[]][[]";Out.String(str + ":> ");Out.Bool(CheckBalance(str));Out.Ln;
|
|
END Do;
|
|
|
|
BEGIN
|
|
Do
|
|
END BalancedBrackets.
|