Структури от данни в програмирането 2005/06 - упражнения и практикум

Проект № 4. Буквен пъзел

Буквен пъзел е тъждество, представено като низ от знаци, съдържащ букви, единствен знак за равенство, кръгли скоби и един или няколко знака за аритметични операции. Допустими знаци са:

- големите букви A, B, C, …, Z;
- знак за равенство = ;
- знак за събиране + ;
- знак за изваждане - ;
- знак за умножение * ;
- знак за степенуване ^ ;
- кръгли скоби ( и ) .

Във всеки буквен пъзел една буква съответства на точно една цифра и еднаквите цифри са означени с еднаква буква. Например: FORTY + TEN + TEN = SIXTY представлява да се съберат едно пет цифрено число и две еднакви трицифрени числа, получената сума да е равна на друго пет цифрено число. Да се реши един буквен пъзел означава да се намери на коя буква коя цифра съответства. Горният пример има единствено решение 29786 + 850 + 850 = 31486 . Някои буквени пъзели могат да нямат решение, а други да имат повече от едно решение.

Да се състави програма, която:

а) по даден буквен пъзел във вид на символен низ построява съответно двоично дърво (например чрез обратен полски запис)

б) по даден буквен пъзел представен като двоично дърво проверява кандидат за решение дали наистина е решение

в) по даден буквен пъзел представен като двоично дърво намира всички решения на пъзела

Двоичното дърво го реализираме като binary файл с пряк достъп. Всеки възел описваме със следната структура:

struct node
{
char value[11];
int left, right;
};

Пример: подусловие “ а) ” при подаден низ “ FORTY+TEN+TEN=SIXTY ” трябва да построи във файл дървото:

Нека да преобразуваме дадения низ в обратен полски запис:

FORTY,TEN,+,TEN,+,SIXTY,=

Полученият файл (например PUZZLE.DAT) ще съдържа 7 възела (записа), номерирани от 0 до 6, като коренът на дървото – операцията “=” ще е в последния запис:

Забележки: За подусловие “б)” кандидат решение е списък от наредени двойки <буква,цифра> , което може да се представи в символен низ например така:

“ F=2,O=9,R=7,T=8,Y=6,E=5,N=0,S=3,I=1,X=4 ”.

Резултатът от подусловие “в)” следва да се запише в текстов файл (например OUTPUT.TXT ), като на всеки ред се записва по едно решение на буквения пъзел, като за целта дървото на буквения пъзел се обхожда ляво-корен-дясно и се извеждат необходимия брой скоби:

((29786+850)+850)=31486