Problem I. 238. (April 2010)

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 pont)

Deadline expired on May 10, 2010.

Sorry, the solution is available only in Hungarian. Google translation

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:

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