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.