PHP.SU

Программирование на PHP, MySQL и другие веб-технологии

PHP.SU Портал

Главная

Помощь

Поиск

Поиск Яндекс Вакансии

Пользователи

Здравствуйте, Гость

( Вход · Регистрация · Правила форума )

Забыли пароль?

Реализация функции

Форумы портала PHP.SU » PHP » Программирование на PHP » Вопросы новичков (Модераторы: OrmaJever, Саныч, Строитель)

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

Описание: Проверка на корректность написания скобок

Поиск в теме | Версия для печати

Mandalorian	Отправлено: 24 Ноября, 2021 - 14:10:17
Новичок Покинул форум Сообщений всего: 16 Дата рег-ции: Сент. 2021 Помог: 0 раз(а)	Здравствуйте! Стоит вот такая задача. Реализуйте функцию isBalanced, которая принимает на вход строку, состоящую только из открывающих и закрывающих круглых скобок, и проверяет, является ли эта строка корректной. Пустая строка (отсутствие скобок) считается корректной. Строка считается корректной (сбалансированной), если содержащаяся в ней скобочная структура соответствует требованиям: Скобки — это парные структуры. У каждой открывающей скобки должна быть соответствующая ей закрывающая скобка. Закрывающая скобка не должна идти впереди открывающей. Такой вариант недопустим )(, а вот такой допустим ()(). PHP: скопировать код в буфер обмена isBalanced('(())'); // true isBalanced('((())'); // false Написал решение такого плана: PHP: скопировать код в буфер обмена function isBalanced($str) { $length = strlen($str); $resLeft = []; $resRight = []; for($i = 0; $i < $length; $i++){ if ($str[$i] === '(') { $resLeft []= $i; } elseif ($str[$i] === ')') { $resRight []= $i; } } for($i = 0; $i < $length; $i++){ if($resLeft[$i] > $resRight[$i]) { return false; } } return true; } Вроде выдает правильные ответы. Вопрос: может можно както упростить? Или на что-то не обратил внимания.

Vladimir Kheifets	Отправлено: 24 Ноября, 2021 - 19:53:37
Частый посетитель Покинул форум Сообщений всего: 879 Дата рег-ции: Март 2017 Откуда: Германия, Бавария Помог: 37 раз(а)	Mandalorian пишет: Здравствуйте! Стоит вот такая задача. Реализуйте функцию isBalanced, которая принимает на вход строку, состоящую только из открывающих и закрывающих круглых скобок, и проверяет, является ли эта строка корректной. Пустая строка (отсутствие скобок) считается корректной. Строка считается корректной (сбалансированной), если содержащаяся в ней скобочная структура соответствует требованиям: Скобки — это парные структуры. У каждой открывающей скобки должна быть соответствующая ей закрывающая скобка. Закрывающая скобка не должна идти впереди открывающей. Такой вариант недопустим )(, а вот такой допустим ()(). Вопрос: может можно както упростить? Здравствуйте! Может быть как-то так: Спойлер (Отобразить) PHP: скопировать код в буфер обмена <? function isBalanced($str) { $str = trim($str); if($str === "") return true; while (strlen($str)>2) $str=str_replace("()","",$str); $str=str_replace("()","",$str); return strlen($str)>0?false:true; } $test=["","()()",")(",")","(", "()", "((((())))()())" ,"(()())", "(()()"]; foreach($test as $str) echo "str: '$str' isBalanced: ", isBalanced($str)?"true":"false","<br>"; /* str: '' isBalanced: true str: '()()' isBalanced: true str: ')(' isBalanced: false str: ')' isBalanced: false str: '(' isBalanced: false str: '()' isBalanced: true str: '((((())))()())' isBalanced: true str: '(()())' isBalanced: true str: '(()()' isBalanced: false / ?> Удачи! (Отредактировано автором: 24 Ноября, 2021 - 19:54:18)*

don.bidon	Отправлено: 24 Ноября, 2021 - 20:04:57
Гость Покинул форум Сообщений всего: 78 Дата рег-ции: Март 2019 Помог: 2 раз(а)	PHP: скопировать код в буфер обмена function isBalanced($str): bool { $length = strlen($str); $opened = 0; for ($i = 0; $i < $length; $i++) { $char = $str[$i]; if ('(' === $char) { $opened++; } else if (')' === $char) { if (0 === $opened) { return false; } $opened--; } else { 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 function isBalanced don.bidon Спойлер (Отобразить) PHP: скопировать код в буфер обмена <? function isBalanced($str): bool { $length = strlen($str); $opened = 0; for ($i = 0; $i < $length; $i++) { $char = $str[$i]; if ('(' === $char) { $opened++; } else if (')' === $char) { if (0 === $opened) { return false; } $opened--; } else { throw new InvalidArgumentException(sprintf('Invalid char "%s" at %d offset', $char, $i)); } } return 0 === $opened; } $str=str_repeat("((((())))()())", 50); $strl=strlen($str); $time_start = hrtime(true); echo "function isBalanced don.bidon<br>"; echo "str: '$str' ($strl) isBalanced: ", isBalanced($str)?"true":"false","<br>"; echo "Total execution time in nanoseconds: ",hrtime(true) - $time_start; ?> function isBalanced Vladimir Kheifets Спойлер (Отобразить) PHP: скопировать код в буфер обмена <? function isBalanced($str) { $str = trim($str); if($str === "") return true; while (strlen($str)>2) $str=str_replace("()","",$str); $str=str_replace("()","",$str); return strlen($str)>0?false:true; } $str=str_repeat("((((())))()())", 50); $strl=strlen($str); $time_start = hrtime(true); echo "function isBalanced Vladimir Kheifets<br>"; echo "str: '$str' ($strl) isBalanced: ", isBalanced($str)?"true":"false","<br>"; echo "Total execution time in nanoseconds: ",hrtime(true) - $time_start; ?> Удачи! (Отредактировано автором: 25 Ноября, 2021 - 10:18:49)

don.bidon	Отправлено: 25 Ноября, 2021 - 11:54:53
Гость Покинул форум Сообщений всего: 78 Дата рег-ции: Март 2019 Помог: 2 раз(а)	Vladimir Kheifets пишет: Сравнил по производительности две функции на PHP 7.4 А, ну C-шные либы значит шустрее будут ))

MouseZver	Отправлено: 16 Декабря, 2021 - 13:54:23
Новичок Покинул форум Сообщений всего: 58 Дата рег-ции: Июнь 2017 Откуда: php.ru Помог: 1 раз(а)	Vladimir Kheifets Твой скрипт ломается банально на одних ((( или )(( ты это должен был знать, делая ставку на скорость. Рабочий вариант со всеми нюансами: PHP: скопировать код в буфер обмена <?PHP // принимает на вход строку, состоящую только из открывающих и закрывающих круглых скобок function MouseZver( string $string ): bool { // Пустая строка (отсутствие скобок) считается корректной. if ( empty ( $string ) ) { return true; } // Закрывающая скобка не должна идти впереди открывающей. if ( $string[0] == ')' ) { return false; } // У каждой открывающей скобки должна быть соответствующая ей закрывающая скобка. $count_first = substr_count ( $string, '(' ); for ( $i = 0; $i < $count_first; $i++ ) { $string = str_replace ( '()', '', $string ); } return empty ( $string ); } $start = microtime ( true ); var_dump ( MouseZver( str_repeat ( '((((())))()())', 50 ) ) ); echo microtime ( true ) - $start; echo PHP_EOL; $start = microtime ( true ); var_dump ( MouseZver( str_repeat ( '(((()(', 50 ) ) ); echo microtime ( true ) - $start; echo PHP_EOL; $start = microtime ( true ); var_dump ( MouseZver( str_repeat ( ')))()((', 50 ) ) ); echo microtime ( true ) - $start; (Отредактировано автором: 16 Декабря, 2021 - 13:59:57)

Vladimir Kheifets	Отправлено: 17 Декабря, 2021 - 08:04:56
Частый посетитель Покинул форум Сообщений всего: 879 Дата рег-ции: Март 2017 Откуда: Германия, Бавария Помог: 37 раз(а)	MouseZver пишет: Vladimir Kheifets Твой скрипт ломается банально на одних ((( или )(( ты это должен был знать, делая ставку на скорость. Рабочий вариант со всеми нюансами: Спойлер (Отобразить) PHP: скопировать код в буфер обмена <?PHP // принимает на вход строку, состоящую только из открывающих и закрывающих круглых скобок function MouseZver( string $string ): bool { // Пустая строка (отсутствие скобок) считается корректной. if ( empty ( $string ) ) { return true; } // Закрывающая скобка не должна идти впереди открывающей. if ( $string[0] == ')' ) { return false; } // У каждой открывающей скобки должна быть соответствующая ей закрывающая скобка. $count_first = substr_count ( $string, '(' ); for ( $i = 0; $i < $count_first; $i++ ) { $string = str_replace ( '()', '', $string ); } return empty ( $string ); } $start = microtime ( true ); var_dump ( MouseZver( str_repeat ( '((((())))()())', 50 ) ) ); echo microtime ( true ) - $start; echo PHP_EOL; $start = microtime ( true ); var_dump ( MouseZver( str_repeat ( '(((()(', 50 ) ) ); echo microtime ( true ) - $start; echo PHP_EOL; $start = microtime ( true ); var_dump ( MouseZver( str_repeat ( ')))()((', 50 ) ) ); echo microtime ( true ) - $start; Добрый день! Спасибо за ответ. Верно, скрипт ломался банально на одних ((( или )(( Рабочий вариант со всеми нюансами: PHP: скопировать код в буфер обмена <? function isBalanced($str) { while (strpos($str,"()")!== false) $str=str_replace("()","",$str); return empty($str); } ?> тест функции isBalanced (25100 nanoseconds) PHP: скопировать код в буфер обмена <? $test=["","()()",")(",")","(", "()", "((((())))()())" ,"(()())", "(()()","(((",")(("]; $time_start = hrtime(true); echo "<hr>function isBalanced Vladimir Kheifets<br>"; foreach($test as $str) { echo "str: '$str' isBalanced: ", isBalanced($str)?"true":"false","<br>"; } echo "Total execution time in nanoseconds: ",hrtime(true) - $time_start; /* function isBalanced Vladimir Kheifets str: '' isBalanced: true str: '()()' isBalanced: true str: ')(' isBalanced: false str: ')' isBalanced: false str: '(' isBalanced: false str: '()' isBalanced: true str: '((((())))()())' isBalanced: true str: '(()())' isBalanced: true str: '(()()' isBalanced: false str: '(((' isBalanced: false str: ')((' isBalanced: false Total execution time in nanoseconds: 25100 / ?> тест функции MouseZver (39500 nanoseconds) PHP:* скопировать код в буфер обмена <? $test=["","()()",")(",")","(", "()", "((((())))()())" ,"(()())", "(()()","(((",")(("]; $time_start = hrtime(true); echo "<hr>function MouseZver<br>"; foreach($test as $str) { echo "str: '$str' MouseZver: ", MouseZver($str)?"true":"false","<br>"; } echo "Total execution time in nanoseconds: ",hrtime(true) - $time_start; /* function MouseZver str: '' MouseZver: true str: '()()' MouseZver: true str: ')(' MouseZver: false str: ')' MouseZver: false str: '(' MouseZver: false str: '()' MouseZver: true str: '((((())))()())' MouseZver: true str: '(()())' MouseZver: true str: '(()()' MouseZver: false str: '(((' MouseZver: false str: ')((' MouseZver: false Total execution time in nanoseconds: 39500 / ?> p.s. для оценки производительности скриптов рекомендуется использовать функцию hrtime* (PHP 7 >= 7.3.0, PHP 8) Удачи! (Отредактировано автором: 19 Декабря, 2021 - 14:39:53)

Поиск в теме | Версия для печати

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

Сейчас эту тему просматривают: 0 (гостей: 0, зарегистрированных: 0)

« Вопросы новичков »

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