Problema pentru saptamana aceasta nu este deosebit de grea, dar trebuie
programata cu atentie. Am considerat ca merita propusa pentru ca atinge un
domeniu inca netratat pe lista. Succes!
PROBLEMA 18: SBASIC (Slow Basic)
DEADLINE: Luni, 10 mai 1999
DOMENIU: Scrierea unui mini-interpretor
TIMP DE IMPLEMENTARE: 2h 30min
PUNCTAJ: 65 dexteri
Fiind nemultumit de mediul (dez)integrat QBasic, doriti sa va scrieti
propriul interpretor al limbajului BASIC. Pentru a defini sintaxa acestui
limbaj, vom introduce urmatoarele notiuni:
1. Nu se face distinctie intre literele mari si cele mici.
2. Numerele sunt intotdeauna intregi, cuprinse intre -32768 si 32767.
3. Expresiile aritmetice se compun din numere, operatorii +, -, *, /
si paranteze. Operatorul / are semnificatia impartirii intregi, de
exemplu 7/3=2, (-7)/3=-2.
4. Variabilele sunt intotdeauna de tip intreg. Daca se acceseaza o
variabila care nu a fost anterior initializata, valoarea ei se presupune
a fi 0. Numele de variabile incep cu o litera si continua cu litere sau
cifre. Numai primele 8 caractere ale unui nume de variabila sunt
semnificative, de exemplu variabila AnaAreMere este confundata cu
variabila AnaAreMeningita.
5. O "valoare" poate fi o variabila, o expresie aritmetica sau un numar.
6. Expresiile logice au numai forma
valoare operator valoare
unde operator poate fi =, <>, >, <, <=, >=. Nu exista variabile sau
constante de tip logic (boolean).
7. Instructiunile se scriu cate una pe linie. Instructiunile care trebuie
recunoscute de interpretorul vostru sunt:
a) PRINT valoare
Tipareste valoarea (numar, expresie sau variabila) specificata,
apoi o "linie noua".
b) INPUT variabila
Citeste o valoare pentru variabila specificata
c) LET variabila = valoare
Atribuie variabilei o valoare
d) GO TO valoare (GO separat de TO !)
Continua executia programului de la linia cu eticheta specificata
(cititi mai jos despre etichete). Daca nu exista nici o linie cu
eticheta specificata, programul continua de la linia cu eticheta cu
valoare cat mai mica, dar mai mare decat cea specificata. Daca nu
exista nici o eticheta mai mare sau egala cu cea specificata,
programul se opreste.
e) IF expresie_logica THEN instructiune1 ELSE instructiune2
Executa prima instructiune daca este indeplinita conditia logica,
sau pe a doua in caz contrar. Instructiunea IF are intotdeauna doua
ramuri. Se permite imbiricarea instructiunilor IF.
f) STOP
Opreste imediat programul. Un program se mai poate termina si dupa
ce ultima linie de program a fost executata.
Semnul '=' de la instructiunea LET poate fi lipit de variabila si de
valoare, sau poate fi separat prin spatii. Numarul de spatii dintre doua
cuvinte, de la inceputul unei linii si/sau de la sfarsitul unei linii
poate fi oricat de mare.
8. O linie de program poate fi goala sau poate avea una din formele:
eticheta instructiune
sau
instructiune
Etichetele sunt numere cuprinse intre 1 si 32767. Ele apar in program
in ordine strict crescatoare.
9. Un program se opreste in patru cazuri:
a) La intalnirea instructiunii STOP
b) La intalnirea instructiunii GO TO valoare, daca valoarea este mai mare
decat cea mai mare eticheta existenta in program.
c) Dupa executarea ultimei instructiuni din program.
d) La intalnirea unei erori de calcul (Overflow, Division by zero). Exemple:
LET X=3 sau: LET X=-10000
LET Y=7/(X-3) GO TO X-30000
In cazul expresiilor aritmetice, se genereaza overflow numai daca
rezultatul final este in afara domeniului -32768..32767. De exemplu,
expresia (20000+20000)/10000 are valoarea 4 si nu genereaza overflow.
Vi se cere sa rulati un program si sa spuneti ce rezultate ar afisa acest
program in urma instructiunilor PRINT executate.
DATE DE INTRARE: Fisierul PROGRAM.IN contine textul programului. Programul
este corect si se garanteaza ca el nu cicleaza intrinsec (adica exista
seturi de date de intrare pentru care el nu cicleaza).
Fisierul DATE.IN contine datele trimise programului, cate un numar pe
linie, in ordinea in care ar fi ele introduse la fiecare cerere efectuata
de o instructiune INPUT. Datele de intrare sunt corecte si suficiente
(exista atatea numere cate cere programul). Se garanteaza ca programul nu
cicleaza datorita datelor introduse.
DATE DE IESIRE: Fisierul DATE.OUT trebuie sa contina numerele afisate de
instructiunile PRINT, in ordinea in care aceste instructiuni sunt
executate.
EXEMPLE:
Un program care tipareste Un program care intoarce pe
restul impartirii la 10 a unui dos cifrele unui numar
numar citit:
PROGRAM.IN PROGRAM.IN
1 INPUT Numar INPUT N
10 Ultima=N-N/10*10
M=M*10+Ultima
2 PrINt NuMar-NumaR /10* 10 N=N/10
IF N>0 THEN GO TO 5 ELSE PRINT M
DATE.IN DATE.IN
229 17345
DATE.OUT DATE.OUT
9 (Nu se tipareste nimic. Programul
e corect, dar M ar trebui sa fie
54371 si se produce depasire).
Timp de rulare pe test: De cel mult doua ori mai lent decat sursa comisiei,
care nu va fi prea optimizata :) Nu putem preciza un timp fix, pentru ca
el depinde de natura programelor specificate.
|
|
