PHP.SU

Программирование на PHP, MySQL и другие веб-технологии
PHP.SU Портал     На главную страницу форума Главная     Помощь Помощь     Поиск Поиск     Поиск Яндекс Поиск Яндекс     Вакансии  Пользователи Пользователи


 Страниц (1): [1]   

> Описание: Проверка на корректность написания скобок
Mandalorian
Отправлено: 24 Ноября, 2021 - 14:10:17
Post Id


Новичок


Покинул форум
Сообщений всего: 10
Дата рег-ции: Сент. 2021  


Помог: 0 раз(а)




Здравствуйте! Стоит вот такая задача.

Реализуйте функцию isBalanced, которая принимает на вход строку, состоящую только из открывающих и закрывающих круглых скобок, и проверяет, является ли эта строка корректной. Пустая строка (отсутствие скобок) считается корректной.

Строка считается корректной (сбалансированной), если содержащаяся в ней скобочная структура соответствует требованиям:

Скобки — это парные структуры. У каждой открывающей скобки должна быть соответствующая ей закрывающая скобка.
Закрывающая скобка не должна идти впереди открывающей. Такой вариант недопустим )(, а вот такой допустим ()().

PHP:
скопировать код в буфер обмена
  1.  
  2. isBalanced('(())');  // true
  3. isBalanced('((())'); // false
  4.  


Написал решение такого плана:

PHP:
скопировать код в буфер обмена
  1.  
  2. function isBalanced($str) {
  3. $length = strlen($str);    
  4. $resLeft = [];
  5. $resRight = [];
  6.    
  7. for($i = 0; $i < $length; $i++){
  8. if ($str[$i] === '(') {
  9.     $resLeft []= $i;
  10.     } elseif ($str[$i] === ')') {
  11.     $resRight []= $i;
  12.     }
  13. }
  14.  
  15. for($i = 0; $i < $length; $i++){
  16.  
  17. if($resLeft[$i] > $resRight[$i]) {
  18.     return false;
  19. }
  20. }
  21. return true;
  22. }
  23.  


Вроде выдает правильные ответы.

Вопрос: может можно както упростить? Или на что-то не обратил внимания.
 
 Top
Vladimir Kheifets
Отправлено: 24 Ноября, 2021 - 19:53:37
Post Id



Частый посетитель


Покинул форум
Сообщений всего: 736
Дата рег-ции: Март 2017  
Откуда: Германия, Бавария


Помог: 33 раз(а)




Mandalorian пишет:
Здравствуйте! Стоит вот такая задача.

Реализуйте функцию isBalanced, которая принимает на вход строку, состоящую только из открывающих и закрывающих круглых скобок, и проверяет, является ли эта строка корректной. Пустая строка (отсутствие скобок) считается корректной.

Строка считается корректной (сбалансированной), если содержащаяся в ней скобочная структура соответствует требованиям:

Скобки — это парные структуры. У каждой открывающей скобки должна быть соответствующая ей закрывающая скобка.
Закрывающая скобка не должна идти впереди открывающей. Такой вариант недопустим )(, а вот такой допустим ()().

Вопрос: может можно както упростить?


Здравствуйте!
Может быть как-то так:
Спойлер (Отобразить)
Удачи!

(Отредактировано автором: 24 Ноября, 2021 - 19:54:18)

 
 Top
don.bidon
Отправлено: 24 Ноября, 2021 - 20:04:57
Post Id


Новичок


Покинул форум
Сообщений всего: 60
Дата рег-ции: Март 2019  


Помог: 2 раз(а)




PHP:
скопировать код в буфер обмена
  1. function isBalanced($str): bool
  2. {
  3.     $length = strlen($str);
  4.     $opened = 0;
  5.  
  6.     for ($i = 0; $i < $length; $i++) {
  7.         $char = $str[$i];
  8.         if ('(' === $char) {
  9.             $opened++;
  10.         } else if (')' === $char) {
  11.             if (0 === $opened) {
  12.                 return false;
  13.             }
  14.             $opened--;
  15.         } else {
  16.             throw new InvalidArgumentException(sprintf('Invalid char "%s" at %d offset', $char, $i));
  17.         }
  18.     }
  19.     return 0 === $opened;
  20. }

Не мерил производительность, но что-то подсказывает, что str_replace() использовать жестковато как-то )
 
 Top
Mandalorian
Отправлено: 25 Ноября, 2021 - 09:20:56
Post Id


Новичок


Покинул форум
Сообщений всего: 10
Дата рег-ции: Сент. 2021  


Помог: 0 раз(а)




Всем большое спасибо!

don.bidon пишет:
$opened = 0;

don.bidon, понравилось Ваше решение со счетчиком $opened Здорово
 
 Top
Vladimir Kheifets
Отправлено: 25 Ноября, 2021 - 10:14:58
Post Id



Частый посетитель


Покинул форум
Сообщений всего: 736
Дата рег-ции: Март 2017  
Откуда: Германия, Бавария


Помог: 33 раз(а)




don.bidon пишет:
Не мерил производительность, но что-то подсказывает, что str_replace() использовать жестковато как-то )

Добрый день!

Сравнил по производительности две функции на PHP 7.4
Получил средующие результаты:
на строке в 140 символов Ваша функция работает быстрее моей на 700 nanoseconds
Спойлер (Отобразить)
на строке в 700 символов Ваша функция работает медленее моей на 36.700 nanoseconds.
Спойлер (Отобразить)
function isBalanced don.bidon
Спойлер (Отобразить)
function isBalanced Vladimir Kheifets
Спойлер (Отобразить)
Удачи!

(Отредактировано автором: 25 Ноября, 2021 - 10:18:49)

 
 Top
don.bidon
Отправлено: 25 Ноября, 2021 - 11:54:53
Post Id


Новичок


Покинул форум
Сообщений всего: 60
Дата рег-ции: Март 2019  


Помог: 2 раз(а)




Vladimir Kheifets пишет:
Сравнил по производительности две функции на PHP 7.4

А, ну C-шные либы значит шустрее будут ))
 
 Top
Страниц (1): [1]
Сейчас эту тему просматривают: 1 (гостей: 1, зарегистрированных: 0)
« Вопросы новичков »


Все гости форума могут просматривать этот раздел.
Только зарегистрированные пользователи могут создавать новые темы в этом разделе.
Только зарегистрированные пользователи могут отвечать на сообщения в этом разделе.
 



Powered by PHP  Powered By MySQL  Powered by Nginx  Valid CSS  RSS

 
Powered by ExBB FM 1.0 RC1. InvisionExBB