Найти максимальную глубину вложенных скобок в строке
Нам дают строку с круглыми скобками, как показано ниже
«(((X)) (((Y))))»
Нам нужно найти максимальную глубину сбалансированных скобок, как 4 в приведенном выше примере. Так как 'Y' окружено 4 сбалансированными скобками.
Если круглые скобки не сбалансированы, верните -1.
Примеры :
Метод 1 (использует стек)
Простым решением является использование стека, который отслеживает текущие открытые скобки.
Сложность времени: O (n)
Вспомогательное пространство: O (n)
Метод 2 (O (1) вспомогательное пространство)
Это также можно сделать без использования стека.
Ниже приведена реализация вышеуказанного алгоритма.
// Программа на C ++ для определения максимальной глубины вложенности
// скобки в данном выражении
#include <iostream>
using namespace std;
// функция берет строку и возвращает
// максимальная глубина вложенных скобок
int maxDepth(string S)
int current_max = 0; // текущий счет
int max = 0; // общее максимальное количество
// Обход строки ввода
for ( int i = 0; i< n; i++)
// обновить макс при необходимости
if (current_max> max)
// наконец проверяем несбалансированную строку
if (current_max != 0)
// Java программа для поиска максимальной глубины вложенности
// скобки в данном выражении
// функция берет строку и возвращает
// максимальная глубина вложенных скобок
static int maxDepth(String S) <
int current_max = 0 ; // текущий счет
int max = 0 ; // общее максимальное количество
// Обход строки ввода
for ( int i = 0 ; i < n; i++) <
// обновить макс при необходимости
if (current_max > max) <
if (current_max > 0 ) <
// наконец проверяем несбалансированную строку
if (current_max != 0 ) <
public static void main(String[] args) <
# Программа Python, чтобы найти максимальную глубину вложенности
# скобки в данном выражении
Функция # принимает строку и возвращает
# максимальная глубина вложенных скобок
# Пройти строку ввода
for i in xrange (n):
if current_max > max :
if current_max > 0 :
# наконец, проверьте несбалансированную строку
if current_max ! = 0 :
# Этот код предоставлен BHAVYA JAIN
<?php
// PHP программа для поиска
// максимальная глубина вложенности
// скобки в данном
// выражение
// функция принимает строку
// и возвращает максимум
// глубина вложенных скобок
function maxDepth( $S )
// общее максимальное количество
// Обход строки ввода
for ( $i = 0; $i < $n ; $i ++)
// обновить макс при необходимости
if ( $current_max > $max )
if ( $current_max >0)
if ( $current_max != 0)
echo maxDepth( $s );
// Этот код предоставлен mits
?>
Выход :
Сложность времени: O (n)
Вспомогательное пространство: O (1)
Эта статья предоставлена Гауравом Шармой . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.
Найдите максимальную глубину вложенных скобок в строке R-кода
У меня проблема с завершением этого кода R. Нам дается строка со скобками, как показано ниже «(((X)) (((Y))))» Нам нужно найти максимальную глубину сбалансированной скобки, например 4 в примере выше. Поскольку «Y» заключен в 4 сбалансированные круглые скобки.
Если круглые скобки неуравновешены, верните -1 Мой код выглядит так:
но когда я вызываю функцию def («(A ((B)))»), ответ должен быть 2. Но каждый раз он показывает 0, даже когда круглые скобки неуравновешены. Я не уверен, правильный ли код или где ошибка. Я пытаюсь выучить R, так что проявите ко мне терпение. Спасибо
Я не думаю, что is.element(‘(‘,n[i]) делает то, что вы думаете! Вам наверное нужен substr(n,i,i)==»(«
Итак, наконец, я закончил код. Теперь он показывает, сбалансированы ли скобки или нет. Если он сбалансирован, он показывает максимальную скобку, если он несбалансирован, он показывает -1. Спасибо всем за большую помощь. Я очень ценю это. Вот окончательный код для всех, кому нужно будет решить эту проблему: sample = function(z) < y = match( strsplit(z, "")[[1]], c("(", ")"), 0 ) m <- max(cumsum( c(1, -1)[y] )) if((min(cumsum( c(1, -1)[y] ))<0)||(sum( c(1, -1)[y])!=0)) < print(-1) >else < print(m) >> Просто назовите его как sample(«(A((B)))»)
@Filip Pittner, sample(«abc») должен быть 0, но дает другой ответ и несколько предупреждений.
Ответы 2
Если x <- «( ((X)) (((Y))) )» , то удалите все скобки и разделите на символы .
а затем максимальное вложение — это наибольшая совокупная сумма +1 (для ( ) и -1 (для ) ) .
Если круглые скобки не сбалансированы, то sum(ifelse(y==»(«, 1, -1))) не будет равен нулю.
Связанная идея состояла бы в том, чтобы сопоставить отдельные символы с ( и ) с y = match( strsplit(x, «»)[[1]], c(«(«, «)»), 0 ) , затем перекодировать и суммировать max(cumsum( c(1, -1)[y] )) .
Я пробовал, но когда скобка неуравновешена, она показывает мне первую сбалансированную скобку. Как (A) (B)) показывает 1, но он должен показать -1, поскольку B не сбалансирован. Я включил его в функцию, чтобы я мог легко называть его sample = function(z)
Вот три решения. Все они векторизованы, то есть входной x может быть вектором символов, и все они правильно обрабатывают случай отсутствия скобок.
1) strapply / proto strapply в пакетах gsubfn соответствует регулярному выражению, указанному в качестве второго аргумента, запускающего функцию fun в прото-объекте p , который также должен быть передан в strapply . Функция pre в p инициализирует вычисление для каждого компонента входного x . Прото-объект можно использовать для сохранения памяти о прошлых совпадениях (здесь lev — уровень вложенности), позволяя производить подсчет. Мы добавляем произвольный символ, здесь «X» , к каждой строке, чтобы всегда было хотя бы одно совпадение. Если бы мы знали, что вводимых строк символов нулевой длины нет, это можно было бы опустить. sapply использует Max , который берет максимум из возвращенных глубин или возвращает -1, если баланс отсутствует.
2) Уменьшить Это базовое решение. Он использует Max из (1).
3) strapply / list (ремешок / список) Другая возможность — извлечь круглые скобки и вернуть +1 или -1 для ( и ) , используя strapply со списком замен. Затем запустите cumsum и Max (сверху) поверх этого.
Это тоже хорошо, но недостаточно. Если скобка не сбалансирована, возникает проблема. Как и (A) ((B) или (A (B))), он должен вывести -1, но он будет печатать первую правильную круглую скобку, даже если она не сбалансирована
Это просто вопрос замены max на функцию Max , которая возвращает максимум или -1 в зависимости от того, есть баланс или нет. Сделали это изменение.
Как определить максимальную глубину вложенности скобок
Relan, насколько я понял человеку надо выделить именно самые вложенные скобки(и их содержимое), а не глубину, на котрой они находятся.
То есть что-то типа того:
Добавлено 20.02.05, 12:05
Relan, твой код только проверяет на парность скобок. Т.е. если все скобки парные, твой код вернет 0
mikv, он хотел определить именно глубину вложенности. Посмотри на вопрос
Добавлено 20.02.05, 12:08
Если мой подойдет, то алгоритм прост до безобразия, это одна из самых простых задач на рекурсию. Мы идем по открытым скобкам и считаем их, пока не дойдем до закрывающейся. Когда мы до нее доходим, то максимальная глубина вложенности скобок будет определяться максимумом двух значений: а) текущим значением открытых скобок б) текущим значением открытых скобок минус 1 (вследствие того, что мы встретили закрывающуюся скобку) плюс количество открывающихся скобок после найденной нами закрывающейся. Вот так вот.
Добавлено 20.02.05, 12:10
зы. млин, и как все-таки галимо выглядит рекурсия в сях