KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum

Rendelje meg a KöMaL-t!

ELTE

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

I. 238. Parentheses are used to change the priority of operations. Your program i238 should find unmatched parentheses or missing characters in an expression. Expressions can consist of three different types of parentheses, digits and arithmetic operations. (Checking other aspects of syntactic correctness is not to be considered now.)

Parenthetically correct expressions (,,szabályosan zárójelezett kifejezések'' in the example) are defined recursively:

- if string s is parenthetically correct (\(\displaystyle s\) may be empty as well), then so are (s), [s] and {s};

- if strings s and p are parenthetically correct expressions, then so is their concatenation sp.

Any other types of expression should be considered as incorrect (,,szabálytalanok'' in the example).

The first command line argument of your program is the name of a file containing several test expressions. The first line of the file contains an integer \(\displaystyle N\) (\(\displaystyle 1\le N\le 100\)), the number of test expressions, while the following \(\displaystyle N\) lines contain the expressions, each with length between 1 and 255.

The second command line argument of your program is the name of the output file, containing N lines, each having a single integer, specifying the position of the first incorrect or missing character in the corresponding line.

In the example, ,,Bemenet'' is input, while ,,Kimenet'' is output.

The source code (i238.pas, i238.cpp, ...) together with a short documentation (i238.txt, i238.pdf, ...) -- also describing which developer environment to use for compiling, further a brief description of your solution -- should be submitted in a compressed file (i238.zip).

(10 points)

Deadline expired on 10 May 2010.


Google Translation (Sorry, the solution is published in Hungarian only.)

Megoldásokról

A feladat a megoldóknak könnyűnek számított, ennek ellenére kevés program érkezett.

Szabó Attila (Pécs, Leőwey Klára Gimnázium) 9. osztályos tanuló megoldása alapján

A zárójelezés helyességének definícióját úgy fogalmazom át, hogy minden nyitó zárójelhez egy hozzátartozó záró zárójel tartozik.

Ennek ellenőrzésére egy verem adatszerkezet használok. A karakterverembe minden nyitó zárójelet beteszek. A kifejezés feldolgozása során amikor záró zárójelhez érek, a veremből kivett nyitó zárójelet vizsgálom. Ha a két zárójel összeillik, akkor azok megfelelő zárójelpárt határoznak meg, különben, ha a verem üres, vagy az első hibás karakter az éppen feldolgozott pozíción van és a feldolgozás véget ér.

Ha végigérünk a feldolgozáson (nincs rossz bezáró zárójel), akkor még megnézem a verem tartalmát. Amennyiben a verem üres, minden zárójel bezáródott, így a zárójelezés helyes, a kimenet 0, különben van még be nem zárt zárójel, és így a string aktuális hosszánál eggyel nagyobb pozícióról hiányzik egy karakter. Ennek megfelelően a kimenetnek a string hossza+1-nek kell lennie.

Mintamegoldás: i238.pas

Tesztállomány: zarojel1.be


Statistics on problem I. 238.
5 students sent a solution.
10 points:Balla Attila, Pap 999 Dávid, Szabó 928 Attila.
9 points:Barta 111 János.
7 points:1 student.


  • Problems in Information Technology of KöMaL, April 2010

  • Támogatóink:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
    MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley