# 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.