5-th Bulgarian National Olympiad in Informatics

April 22, 1989

Selection round

First day

Let us consider a binary tree. Each leaf of this tree contains a character string. Any such string has at most 8 characters. Among these characters, the signs "+", "-", "(" and ")" are not present. The non-terminal nodes of the tree contain only a "+" or "-" sign. Each of them has two descenders: left-hand and right-hand subtrees. We will use the following operations: Having a "+" sign in a node, we can link together the strings belonging to the left-hand and to the right-hand subtrees, whereas having a "-" sign, we can do the same, but in a reverse order: first, we put the string from the right-hand side and afterward, we link it to the left-hand string.

Write a program for solving the following problems:

Problem 1.

Compute an expression represented linearly by means of the operations "+" and "-", brackets "(" and ")" and containing also other characters. This expression will be entered by the keyboard during the run time of your program.

An example:

Taking as input ((A+B)-C)+((D-E)+F), your program should output CABEDF.

Problem 2.

Create and describe a method for representing character strings as a binary tree.

Problem 3.

Given a character string, build the corresponding binary tree using the method from Problem 2.

Problem 4.

Given a binary tree that represents a character string, compute this string.

Source: Obuchenieto po matematika i informatika, journal published by Bulgarian Ministry of Education, n. 4, 1989, pp. 49-50.
© The text is translated from Bulgarian by Emil Kelevedzhiev (keleved@math.bas.bg)
Return to the Home Page of Bulgarian Mathematics and Informatics Competitions.