1

Тема: Застосування стеку

Написати програму, що визначає, чи має символьний рядок, що вводиться з клавіатури, правильну форму виду  a D b D c D ... D z  , де кожний рядок a, b, c, ..., z називається подібним і  має форму виду  x C y, де x - рядок, що складається з літер A і B, а y - рядок, обернений до рядка x (наприклад, якщо x = AАBABB, то y повинен дорiвнювати BBABАA).  Отже, рядок має правильну форму, якщо він складається з будь-якої кiлькостi подiбних рядків, що роздiленi символом D. Визначити чи введений рядок є правильним. 
Мені потрібно реалізувати за допомогою стеку(у вигляді класу)

Підскажіть з чого почати, так як вперше зустрівся з АТД і і зі стеком теж..приблизний алгортм...

2

Re: Застосування стеку

В нас є автомат з двома станами і магазином. Спершу він перебуває в стані додавання до стеку, і читає по порядку всі символи рядка.

В стані додавання до стеку, коли він зустрічає:
А - кладе його в стек
B - кладе його в стек
С - перейти в стан діставання зі стеку.
D - рядок має неправильну форму (ми очікуємо на C), завершити роботу.
Закінчення рядка - рядок має неправильну форму (ми очікуємо на C), завершити роботу.

В стані діставання зі стеку:
A - витягти символ зі стеку, і якщо він не A - рядок має неправильну форму, завершити роботу.
B - витягти символ зі стеку, і якщо він не B - рядок має неправильну форму, завершити роботу.
C - рядок має неправильну форму (другий під ряд C, це не за правилами), завершити роботу
D - якщо стек не порожній - рядок має неправильну форму, завершити роботу. Якщо порожній - перейти в стан додавання до стеку.
Закінчення рядка - якщо стек не порожній - рядок має неправильну форму. Якщо порожній - рядок має правильну форму. Завершити роботу.


Ну а стек ви самі повинні вміти писати.

Подякували: koala, Replace, Chemist-i3

3

Re: Застосування стеку

це наприклад буде ААBBCBBAA вводитися, то кожен символ окремо буде заганятися в стек через push, коли потрапиться C викликаєм pop, і витягуємо вимволи BBAA...а як ії порівнювати з тими, що вводили в стек...можна на коді приблизно показати будь-ласка

4

Re: Застосування стеку

sardar2222 написав:

а як ії порівнювати з тими, що вводили в стек

Ви знаєте такі слова як push і pop, і не знаєте такого оператора як ==? Це дивно...

Подякували: koala1