Задача: проверка скобочного выражения

Задача: проверка скобочного выражения
Оцени эту статью

Имеется текстовая строка, которая содержит произвольное скобочное выражение (скобки (), [], или {}). Необходимо создать функцию check(), которая будет проверять это скобочное выражение на правильность:

check(«y(x)») -> true
check(«[(]») -> false
check(«[{}]») -> true
check(«)(«) -> false
check(«») -> true
check(«b([{}-()]{a})») -> true

С решением нужно повозиться. Но когда оно найдется — будет кратким и компактным (10 — 15 строк). Вариантов решений может быть много.


Свои варианты решения добавляйте в комментарии (чтобы код в комментариях отображался корректно, размещайте его между тегами <code> </code>).

Рассылка новых уроков по программированию:

Olej

Об авторе Olej

Стаж практических программных разработок около 40 лет. Преподаватель международной софтверной компании Global Logic. Постоянный автор публикаций IBM Developer Works. Научный редактор книжного издательства компьютерной литературы "Символ-Плюс", Санкт-Петербург.

Задача: проверка скобочного выражения: 10 комментариев

  1. Типа того (код не проверял, могут быть опечатки). Можно всяко- разно украшать и делать гибче, но суть та же, что и в случае одного вида скобок — блок-схема алгоритма есть тут: http://pro-prof.com/archives/578

  2. > код не проверял
    А напрасно ;-) …

    1. вместо if (c == «(«) должно if (c == ‘(‘)
    ну и во всех подобных ветках…
    (и то если только это компилировать с опциями стандарта C++11)

    2. но и это не будет работать без:

    по крайней мере, до тех пор, пока это (bct1, bct2, bct3) — локальные переменные.

    3. и, наконец, это никогда не будет работать просто алгоритмически, потому что вот такое скобочное выражение тоже будет совершенно корректным:

    1. >> потому что вот такое скобочное выражение тоже будет совершенно корректным: ( 1 [ 2 { 3 ) 4 ] }

      Я не считаю такое выражение корректным. В условиях задачи написано «проверять на правильность». «правильность» вы никак не формализовали, приведенные в задаче примеры не содержат вроде бы ни одной группы скобок, внутри которой нарушается баланс других скобок. Ну и вообще, не понятно что именно задается (может задаваться) разными видами скобок.

      С кавычками и инициализацией переменных я накосячил, да. Еще конструкцию do while(false) я тут зря применил, профита с нее в этом случае не будет.

      Приведи свое решение со стеками, интересно посмотреть (я по твоему описанию профита с них не вижу).

      1. > Я не считаю такое выражение корректным.
        Вот и я не считаю.
        А код показанный — считает. ;-)

      2. > Приведи свое решение со стеками, интересно посмотреть
        А оно с 1-го для лежит под спойлером «Решение».
        И даже не одно решение…

      3. > Ну и вообще, не понятно что именно задается (может задаваться) разными видами скобок.

        Что такое правильное скобочное выражение (и для разных видов скобок тоже) дети учат в 4-м классе начальной школы.

  3. Вообще то, это в закамуфлированной форме задача вычисления вложенных скобочных выражений (как, например, в LISP lambda-выражений … или в калькуляторе), но специально в очень упрщённой формулировке. В общем виде задача таких вычислений решается рекурсивно: при открытии очередного скобочного выражения — заталкиваем параметры в стек и вызываем нижний уровень рекурсии, а при завершении обработки скобочного уровня — возврат из рекурсивного вызова и выталкивание переметров и стека обратно.
    Но в такой формулировке задачи вычисление на уровне рекурсии вырожденное (ничего не делать), поэтому рекурсия отпала, а стек остался.

  4. Я хочу разработать программу компютерная диагностики аудио видео радио аппаратуры описание программы там есть окошко где можно писаить пишем того что будем проверять и программа знает все параметры радио деталь в савляем щупы в вуковую карту и проверяем радио детали если горит зеленым цветом то радио деталь рабочая если горит желтым то радио деталь полу рабочая тоест луче поменять если горит красным то радио деталь не рабочая.Нужна помочт раработки?

    1. 1. это будет очень непростая по коду и размеру программа
      2. просто со входа звуковой карты (микрофонный?) так проверить не получится — это вход АЦП, на него можно подавать напряжение, но без внешнего источника напряжения подключать туда «радиодеталь» бессмысленно…
      3. даже решив вопрос с источником напряжения, так проверять параметры вы сможете очень немногих простейших радиодеталей: диода, некоторых резисторов … транзистор вы уже не проверите, не говоря уже о более сложных устройствах.
      4. такая программа (даже если бы вы её при всех ограничениях возможностей сделали) будет зависимой от операционной системы: работающая под Windows не будет работать под Linux, если вы сделаете под Linux — она не будет работать под FreeBSD, сделаете под FreeBSD — не будет работать под Solaris и т.д.

      В сети есть довольно много программ компьютерных осциллографов, подключаемых ко входу аудиокарты. Многие из них — с открытым кодом. Возьмите код таких программ и смотрите как они работают с аудиовходом.

Добавить комментарий

Код размещайте в тегах: <pre class="lang:c++ decode:true ">YOUR CODE</pre>