Покинул форум
Сообщений всего: 16
Дата рег-ции: Сент. 2021
Помог: 0 раз(а)
Здравствуйте! Стоит вот такая задача.
Реализуйте функцию isBalanced, которая принимает на вход строку, состоящую только из открывающих и закрывающих круглых скобок, и проверяет, является ли эта строка корректной. Пустая строка (отсутствие скобок) считается корректной.
Строка считается корректной (сбалансированной), если содержащаяся в ней скобочная структура соответствует требованиям:
Скобки — это парные структуры. У каждой открывающей скобки должна быть соответствующая ей закрывающая скобка.
Закрывающая скобка не должна идти впереди открывающей. Такой вариант недопустим )(, а вот такой допустим ()().
Вопрос: может можно както упростить? Или на что-то не обратил внимания.
Vladimir Kheifets
Отправлено: 24 Ноября, 2021 - 19:53:37
Частый посетитель
Покинул форум
Сообщений всего: 879
Дата рег-ции: Март 2017 Откуда: Германия, Бавария
Помог: 37 раз(а)
Mandalorian пишет:
Здравствуйте! Стоит вот такая задача.
Реализуйте функцию isBalanced, которая принимает на вход строку, состоящую только из открывающих и закрывающих круглых скобок, и проверяет, является ли эта строка корректной. Пустая строка (отсутствие скобок) считается корректной.
Строка считается корректной (сбалансированной), если содержащаяся в ней скобочная структура соответствует требованиям:
Скобки — это парные структуры. У каждой открывающей скобки должна быть соответствующая ей закрывающая скобка.
Закрывающая скобка не должна идти впереди открывающей. Такой вариант недопустим )(, а вот такой допустим ()().
throw new InvalidArgumentException(sprintf('Invalid char "%s" at %d offset',$char,$i));
}
}
return 0 ===$opened;
}
Не мерил производительность, но что-то подсказывает, что str_replace() использовать жестковато как-то )
Mandalorian
Отправлено: 25 Ноября, 2021 - 09:20:56
Новичок
Покинул форум
Сообщений всего: 16
Дата рег-ции: Сент. 2021
Помог: 0 раз(а)
Всем большое спасибо!
don.bidon пишет:
$opened = 0;
don.bidon, понравилось Ваше решение со счетчиком $opened
Vladimir Kheifets
Отправлено: 25 Ноября, 2021 - 10:14:58
Частый посетитель
Покинул форум
Сообщений всего: 879
Дата рег-ции: Март 2017 Откуда: Германия, Бавария
Помог: 37 раз(а)
don.bidon пишет:
Не мерил производительность, но что-то подсказывает, что str_replace() использовать жестковато как-то )
Добрый день!
Сравнил по производительности две функции на PHP 7.4
Получил средующие результаты:
на строке в 140 символов Ваша функция работает быстрее моей на 700 nanoseconds
function isBalanced don.bidon
str: '((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())' (140) isBalanced: true
Total execution time in nanoseconds: 29800
function isBalanced Vladimir Kheifets
str: '((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())' (140) isBalanced: true
Total execution time in nanoseconds: 30500
на строке в 700 символов Ваша функция работает медленее моей на 36.700 nanoseconds.
function isBalanced don.bidon
str: '((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())' (700) isBalanced: true
Total execution time in nanoseconds: 75700
function isBalanced Vladimir Kheifets
str: '((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())((((())))()())' (700) isBalanced: true
Total execution time in nanoseconds: 39000
Покинул форум
Сообщений всего: 879
Дата рег-ции: Март 2017 Откуда: Германия, Бавария
Помог: 37 раз(а)
MouseZver пишет:
Vladimir Kheifets
Твой скрипт ломается банально на одних ((( или )(( ты это должен был знать, делая ставку на скорость.
Рабочий вариант со всеми нюансами:
Все гости форума могут просматривать этот раздел. Только зарегистрированные пользователи могут создавать новые темы в этом разделе. Только зарегистрированные пользователи могут отвечать на сообщения в этом разделе.