Завдання № 49. Перевірити баланс круглих дужок в символьному вираженні » Pascal - основи програмування

Основи програмування на мові Pascal

 

Спонсори

Завдання № 49. Перевірити баланс круглих дужок в символьному вираженні

Завдання № 49. Перевірити баланс круглих дужок в символьному вираженні
Формулювання. Дана послідовність символів довжини n (n> = 1). Перевірити баланс круглих дужок у цьому виразі. Наприклад, при введенні виразу (()) () програма повинна со-общить про правильність розстановки дужок, а при введенні виразу ((()) - про неправильність.
Примітка: збалансованою скобочной записом називається символьний вираз, в якому кожній відкриває скобці відповідає закриває дужка правіше і навпаки, кожній закриває скобці відповідає відкриває дужка лівіше.
Так як ми вводимо послідовність довільних символів, в якій враховуються тільки круглі дужки, то між знаками дужок може перебувати будь-яка символьна інформа-ція, в силу чого коректна програма може перевіряти баланс дужок в арифметичних Вира-женіях, тексті і т. Д. Наприклад, вираз (7y + 1) (17 - (x + 3)) - правильне, а (146x + 18 (y + 9) - неправильне, що зможе розпізнати програма.
Рішення. Уявімо собі посимвольним введенням скобового вираження з клавіатури (коли вже введено деяку кількість символів) і подумаємо, які висновки можна зробити на дан-ном етапі (для простоти сприйняття будемо розглядати вирази, що складаються тільки з ско-пліч):
1) ((()
Зараз «як би» ми бачимо початок скобового вираження і не знаємо, які символи сле-дмуть далі. Які висновки можна зробити на цьому етапі? Наявне вираз містить лиш-ня відкривають дужки і його можна як збалансувати, якщо дописати дві закривають скоб-ки, так і порушити, якщо залишити в тому ж вигляді або застосувати безліч інших комбінацій. Висновок: якщо є зайві відкривають дужки, то вираз ще може бути збалансує-вано.
2) (()))
Цей вираз містить явне порушення балансу дужок, яке вже не може бути скомпенсировано додаванням будь-яких дужкових комбінацій справа, так як не всім закрива-ющим дужках відповідає за однією відкриває скобці лівіше. Звідси висновок: якщо в Вира-жении з'явилася хоча б одна зайва закриває дужка, то вираз «неправильне» і подальша перевірка безглузда.
Приступимо до реалізації цих міркувань. Заведемо лічильник count для підрахунку відкривають-чих і закривають дужок: при введенні відкриває дужки будемо збільшувати його на 1, а при введенні закриває - зменшувати на 1.
Нам потрібно створити змінну c символьного типу char, в яку ми будемо послідовно-тельно вводити всі символи нашого вираження. Варто відзначити, що в тип char також входить пробіл, що впливає на значення довжини введеної послідовності. Наприклад, довжина n вводь-мого виразу (7y  +  1) (17  -  (x  +  3)) дорівнює 22 (пробіли виділені червоним кольором).
Після введення n ми входимо в цикл з n повторень, в якому вводимо в c черговий символ. Покладаючись на попередні міркування, ми збільшуємо count на 1, якщо c = '(' і зменшуємо на 1, якщо c = ')':

readln (n);
count: = 0;
for i: = 1 to n do begin
  read (c);
  if c = '(' then inc (count);
  if c = ')' then dec (count)
end;

Примітка: функція dec (x) зменшує значення змінної x числового типу на 1.
До речі, так як будь будь-яка змінна не може мати відразу два будь-яких значення, ми можемо помістити другий умовної оператор циклу в else-блок першого, що буде виглядати ло-гічної, але ми не будемо цього робити, щоб підвищити читаність коду.
Відзначимо, що введення n здійснюється за допомогою readln (), так як він вимагає введення enter'а як обмежувача. При введенні n через read () далі наступний пробіл або enter буде вклю-чен безпосередньо під вводимую послідовність, що спричинить помилку. Крім того, не можна розділяти зайвими пробілами або enter'амі символи послідовності при введенні, так як вони не ігноруються при введенні в змінні типу char і повинні бути включені в послідовно-ність (при цьому кожен пробіл додає до довжини 1, а кожен enter - 2 ).
Повернемося до розбору. Як же бути, якщо деякий початковий фрагмент вводиться висловлю-ня стане свідомо неправильних, тобто, якщо в ньому з'являться зайві закривають дужки? Але тоді при появі зайвої («некомпенсовані») закриває дужки змінна count стане дорівнює -1, що можна оформити як умова виходу з циклу і помістити після перших двох операторів порівняння:
if count = -1 then break;

Які результати ми отримаємо по завершенні циклу?
1) Цикл пройшов по всіх символам, але були знайдені зайві відкривають дужки (тобто, count> 0), компенсування яких ми очікували, проте вони так і не були скомпенсі-рова і Дужковий послідовність неправильна;
2) Цикл пройшов по всіх символам (тобто, не було виходу), причому кількість дужок обох видів одно (тобто, count = 0) і Дужковий послідовність, відповідно, правильна;
3) Був здійснений вихід з циклу (тобто, знайшли «некомпенсируемое» заслони дужку і count = -1) і послідовність неправильна.
Виходить, правильна відповідь дасть висновок вираження count = 0 (воно істинне в 2-му випадку і хибно в 1-му та 3-му):
writeln (count = 0);

Код:


  1. program BracketSequence;
  2. var
  3. count: integer;
  4. i, n: byte;
  5. c: char;
  6. begin
  7. readln(n);
  8. count := 0;
  9. for i := 1 to n do begin
  10. read(c);
  11. if c = '(' then inc(count);
  12. if c = ')' then dec(count);
  13. if count = -1 then break
  14. end;
  15. writeln(count = 0)
  16. end.

0049.-BracketSequence.rar [691 b] (cкачувань: 6)

скачать dle 10.4фильмы бесплатно Наступна сторінка » Завдання № 50. Обчислити експоненту із ... Попередня сторінка » Завдання № 48. Вивести на екран всі чис...