Yesterday, megeve rewrote a large part of his assembler. Unfortunately, he introduced quite a few bugs this way. As the second round of the MindCoding National Contest is today. megeve is now frantically working to fix the bugs.
One of the most problematic sections of the assembler is the syntax checker. Today, you will help megeve by writing a program that checks if a given memory address is valid.
A memory address in x86 assembly is a mathematical expression containing registers, variables, constants and operators which follows these rules:
- There are two kinds of registers: base registers and index registers
- The base registers are
BXandBP(case-insensitive). There may be no more than one base register in an address. - The index registers are
SIandDI(case-insensitive). There may be no more than one index register in an address. - Variables are represented by one lowercase letter of the Latin alphabet. There may be no more than one variable in an address.
- Constants are nonnegative integers.
- The operators are
+,-, and[]. The last operator is special — anywhere in the expression,[subexpression]is equivalent to+subexpression. Thus,a[DI+3]is equivalent toa+DI+3 - An expression can contain any number of consecutive
+and-operators. Thus,a+++++3,BX+-+-+-+5[a],[a++++++++----------+-+---+++----+3]anda[[[3]]](which is equivalent toa+++3) are all valid. - A (sub)expression may not start or end with a
+or a-operator. Thus,+3,a[+5],5+BX-,a[BX-]are invalid. - An expression may not contain any characters other than
+, -, [, ], a-z, 0-9, BDIPSX. Any other character renders the expression invalid.
[BX]+[SI]+4 [BX+5]+v [BX+SI] [bP+3+2+1+0+1+2] [Bp+dI] v[BX][SI] [si][bx] [a] a[2]Examples of invalid addresses:
V[4] ; Variables are lowercase a[2*2] ; There is no * operator [a+2*2] ; Same here v[AX] ; AX can't appear in an offset speciffication [BX][BP] ; BX and BP can't appear at the same time [BX+BP] ; Same here [BX+BX] ; The registers or variables can't appear more than once [a+b] ; Same here [ a ] ; Spaces are disallowed (1) ; The ( and ) characters are also disallowed
Input
Each line of the input contains a memory address. Each line is at most 100 characters long. The file contains at most 100 lines, and the file ends with a newline character.Output
For each address printOK if it is valid or ERROR if it isn't. Sample
| Input | Output |
|---|---|
| [BX]+[SI]+4 [BX][BP] | OK ERROR |
O greseala pe care au facut-o multi participanti a fost citirea incorecta. Regulamentul olimpiadei spune ca fisierele se termine cu un caracter newline, lucru pe care multi participanti nu l-au luat in considerare, tratand si ultima "linie" (goala) ca o expresie.
Intrucat operatorii + si - sunt echivalenti, incepem prin a inlocui + cu - (1). Apoi verificam daca sirul incepe cu -, se termina cu -, sau contine subsirurile [- sau -], caz in care returnam ERROR (2). Continuam prin inlocuirea subsirurilor de forma [ceva] cu +ceva (3).
Acum avem o expresie delimitata de caracterul -. Consideram separat fiecare token (4):
- Daca e egal cu
bxsaubp(case-insensitive), incrementam numarul de base registers (5) - Daca e egal cu
sisaudi(case-insensitive), incrementam numarul de index registers (6) - Daca e egal cu o litera lowercase, incrementam numarul de variabile (7)
- Daca e numar, trecem mai departe (8)
- Daca nu e niciuna din cele de mai sus, returnam ERROR (9)
Sursa oficiala:
1 #!/usr/bin/perl -w 2 use v5.14; 3 no if $] >= 5.017011, warnings => 'experimental::smartmatch'; 4 5 sub ok{ 6 chomp; # Remove the final newline 7 y/+/-/; # (1) Replace + with - 8 return if /^-|-$|\[-|-\]/; # (2) ERROR if the string starts/ends with a - or if it contains [- or -] 9 1 while s/\[([^[\]]+)]/-$1/; # (3) Replace [...] with -... 10 my ($base, $index, $vars) = (0, 0, 0); 11 for (split '-'){ # (4) Tokenize the expression, using '-' as the delimiter 12 $base++ when m/^bx$|^bp$/i; # (5) If the current token is bx or bp, increment $base 13 $index++ when m/^si$|^di$/i; # (6) If the current token is si or di, increment $index 14 $vars++ when m/^[a-z]$/; # (7) If the current token is a lowercase letter, increment $vars 15 1 when m/^\d*$/i; # (8) If the current token is a number, do nothing 16 default { return } # (9) Otherwise ERROR 17 } 18 19 $base < 2 && $index < 2 && $vars < 2 # (10) 20 } 21 22 say ok() ? 'OK' : 'ERROR' while <>;
