PHP.SU

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


 Страниц (9): « 1 2 3 4 [5] 6 7 8 9 »   

> Описание: Комбинаторика, алгоритмы и прочее - в программном коде
EuGen Администратор
Отправлено: 15 Июля, 2013 - 16:54:21
Post Id


Профессионал


Покинул форум
Сообщений всего: 9097
Дата рег-ции: Июнь 2007  
Откуда: Berlin


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




Классическая простейшая задача о скобочном выражении.
На входе даётся строка, содержащая различные пары скобок. Для определённости пусть пары будет три - обычные скобки, квадратные скобки и фигурные скобки. Кроме этого в строке могут содержаться и другие символы, считается, что они являются самостоятельными элементами (их проверять никак не нужно). Требуется дать ответ (true/false) - является ли данная строка правильным скобочным выражением.
Например, "abc([dy]*[dx]Fz)" - правильное выражение, а "pqr[Gdz)/(Hdx]" - нет
вариант (Отобразить)


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
VenZell
Отправлено: 16 Июля, 2013 - 09:20:25
Post Id


Частый гость


Покинул форум
Сообщений всего: 237
Дата рег-ции: Июнь 2013  


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




Мой вариант решения этой задачи. Далеко не самый оптимальный:
Спойлер (Отобразить)

Попробую еще один вариант без регулярок сделать.

(Отредактировано автором: 16 Июля, 2013 - 09:20:48)

 
 Top
EuGen Администратор
Отправлено: 16 Июля, 2013 - 09:47:42
Post Id


Профессионал


Покинул форум
Сообщений всего: 9097
Дата рег-ции: Июнь 2007  
Откуда: Berlin


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




VenZell
0.Функция не возвращает результата (вместо чего зачем-то выводит на экран строку true или false)
1. Некорректная работа, например, на правильных выражениях:


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
imya
Отправлено: 16 Июля, 2013 - 09:51:32
Post Id



Участник


Покинул форум
Сообщений всего: 1473
Дата рег-ции: Сент. 2012  
Откуда: Запорожье, Украина


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




Будет время - на C# сделаю, если можно конечно Закатив глазки


-----
PHP:
скопировать код в буфер обмена
  1. do {box != cat;} while (cat != box);


Когда нормальный человек, уезжая из дома одевает на жену пояс верности, веб-дизайнер ставит на нее счетчик...
 
My status
 Top
VenZell
Отправлено: 16 Июля, 2013 - 09:55:13
Post Id


Частый гость


Покинул форум
Сообщений всего: 237
Дата рег-ции: Июнь 2013  


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




EuGen, foo() - должно возвращать false? Но ведь скобки закрыты верно... Можно тогда уточнить условия задачи?
upd: а, все, понял. Речь о математических выражениях.
upd2: нет, все-таки не понял... Вы же сами говорите "на правильных выражениях". Функция на ваших примерах возвращает true. Что не так?
На всякий случай выкладываю исправленный пример с return'ом вместо echo
Спойлер (Отобразить)

(Отредактировано автором: 16 Июля, 2013 - 10:17:03)

 
 Top
EuGen Администратор
Отправлено: 16 Июля, 2013 - 10:20:38
Post Id


Профессионал


Покинул форум
Сообщений всего: 9097
Дата рег-ции: Июнь 2007  
Откуда: Berlin


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




VenZell
Пример для Вашей функции:
PHP:
скопировать код в буфер обмена
  1. function checkBrackets($input) {
  2.             $readable_pattern = array(
  3.                 'correct_figure_brackets' => '{[^\[\](){}]*}',
  4.                 'correct_round_brackets' => '\([^\[\](){}]*\)',
  5.                 'correct_square_brackets' => '\[[^\[\](){}]*\]',
  6.                                                 );
  7.                 $pattern = '@' . implode('|', $readable_pattern) . '@iu';
  8.                 $cleaned_data = preg_replace($pattern, '', $input);
  9.                 if ((bool) preg_match($pattern, $cleaned_data)) {
  10.                      checkBrackets($cleaned_data);
  11.                 } else {
  12.                      echo (empty($cleaned_data)) ? 'true' : 'false';
  13.                 }
  14. }
  15.  
  16. $rgExpr = ['foo', 'foo()', ']', '(){[]}'];
  17. array_map(function($sItem)
  18. {
  19.         echo($sItem.' ');
  20.         checkBrackets($sItem);
  21.         echo(PHP_EOL);
  22. }, $rgExpr);

- результат:
CODE (text):
скопировать код в буфер обмена
  1. foo false
  2. foo() false
  3. ] false
  4. (){[]} true


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
soffrick
Отправлено: 16 Июля, 2013 - 10:30:09
Post Id



Посетитель


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


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





Цитата:
PHP:
скопировать код в буфер обмена
  1. return (empty($cleaned_data)) ? true : false;


Цитата:
PHP:
скопировать код в буфер обмена
  1. echo (empty($cleaned_data)) ? 'true' : 'false';

(Отредактировано автором: 16 Июля, 2013 - 10:32:06)



-----
Правильный вопрос - уже половина правильного ответа!

p.s. индусы повсюду, будьте осторожны!
 
 Top
VenZell
Отправлено: 16 Июля, 2013 - 11:03:02
Post Id


Частый гость


Покинул форум
Сообщений всего: 237
Дата рег-ции: Июнь 2013  


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




Я понял, в чем заковыка была.
Я перед функцией удалял все символы, кроме скобок. Цитирую сам себя:
PHP:
скопировать код в буфер обмена
  1. $testcase = preg_replace('/[^{}()\[\]]*/i', '', $input);

И работал уже с этим массивом...
Добавил этот функционал в функцию плюс исправил ошибку, приводящую к тому, что функция возвращала null.
Спойлер (Отобразить)
 
 Top
soffrick
Отправлено: 25 Июля, 2013 - 11:39:44
Post Id



Посетитель


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


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




Цитата:
Классическая простейшая задача о скобочном выражении.



PHP:
скопировать код в буфер обмена
  1. function check($str) {
  2.     if (preg_match('/[\[\]]/', $str)) {
  3.         if (!preg_match_all('/\[[^\[\]]*?\]/', $str, $tmp)) {
  4.             //echo '[]';
  5.             return false;
  6.         }
  7.     }
  8.     if (preg_match('/[\(\)]/', $str)) {
  9.         if (!preg_match_all('/\([^\(\)]*?\)/', $str, $tmp)) {
  10.             //echo '()';
  11.             return false;
  12.         }
  13.     }
  14.     if (preg_match('/[\{\}]/', $str)) {
  15.         if (!preg_match_all('/\{[^\{\}]*?\}/', $str, $tmp)) {
  16.             //echo '{}';
  17.             return false;
  18.         }
  19.     }
  20.     return true;
  21. }
  22.  
  23. $tests = array(
  24.     'pqr[Gdz)/(Hdx]',   // false
  25.     'abc([dy]*[dx]Fz)', // true
  26.     '}{',               // false
  27.     '[]',               // true
  28.     ']',                // false
  29.     'foo()',            // true
  30.     'foo',              // true
  31.     '(){[]}'            // true
  32. );
  33.  
  34. foreach($tests as $test) {
  35.     var_dump(check($test));
  36. }


-----
Правильный вопрос - уже половина правильного ответа!

p.s. индусы повсюду, будьте осторожны!
 
 Top
EuGen Администратор
Отправлено: 25 Июля, 2013 - 11:52:00
Post Id


Профессионал


Покинул форум
Сообщений всего: 9097
Дата рег-ции: Июнь 2007  
Откуда: Berlin


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




soffrick
Плохой велосипед.


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
soffrick
Отправлено: 25 Июля, 2013 - 12:09:53
Post Id



Посетитель


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


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




EuGen пишет:
({)}

Ага, такого не учёл, позже попробую исправить ...

Хотя возможно это может и считаться правильным, если () либо {} будут считаться как обычные символы, в зависимости от того какая скобка будет открыта первой

(Добавление)
Спойлер (Отобразить)

PHP:
скопировать код в буфер обмена
  1. var_dump(check('foo[({)}]bar')); // false
  2. var_dump(check('abc([dy]*[dx]Fz)')); // FAIL

исправил, но теперь правильное выражение считается неправильным, вообщем плохой велосипед - картинка как раз этому и соответствует Улыбка

(Отредактировано автором: 25 Июля, 2013 - 13:44:12)



-----
Правильный вопрос - уже половина правильного ответа!

p.s. индусы повсюду, будьте осторожны!
 
 Top
EuGen Администратор
Отправлено: 25 Июля, 2013 - 12:12:34
Post Id


Профессионал


Покинул форум
Сообщений всего: 9097
Дата рег-ции: Июнь 2007  
Откуда: Berlin


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




soffrick пишет:
Хотя возможно это может и считаться правильным, если () либо {} будут считаться как обычные символы

Не может - по условию задачи. Более того, для того, чтобы показать то, что вектор решения в лучшем случае неоптимален (на деле, судя по всему, неверен из-за неопределённости уровня вложенности и порядка следования), можно добавить другие пары скобок. Например, < и > или / и \


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
soffrick
Отправлено: 25 Июля, 2013 - 12:31:23
Post Id



Посетитель


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


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




EuGen
позвольте тогда и Вашему варианту сделать незначительное замечание Улыбка
PHP:
скопировать код в буфер обмена
  1. var_dump(checkBrackets('}{'));
  2. var_dump(checkBrackets(']'));

Цитата:
Notice: Undefined offset: 0 in index.php on line 7
Notice: Undefined offset: 0 in index.php on line 7

Спойлер (Отобразить)
p.s. рнр 5.3.13 (заменил [] на array())


-----
Правильный вопрос - уже половина правильного ответа!

p.s. индусы повсюду, будьте осторожны!
 
 Top
EuGen Администратор
Отправлено: 25 Июля, 2013 - 12:38:35
Post Id


Профессионал


Покинул форум
Сообщений всего: 9097
Дата рег-ции: Июнь 2007  
Откуда: Berlin


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




Это очевидно - поскольку в целях демонстрации алгоритма опущены некоторые проверки (не проиводящие, разумеется, к некорректной работе).
Поскольку и сам стремлюсь в общем случае к инициализации и избегании NOTICE, рекомендую добавить проверку до обращения по индексу, например,
PHP:
скопировать код в буфер обмена
  1. if(($iBracket=array_search($sData[$i], $rgBrackets))%2 && count($rgStack) && $rgStack[0]==$rgBrackets[$iBracket+1])

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


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
VenZell
Отправлено: 25 Июля, 2013 - 14:06:42
Post Id


Частый гость


Покинул форум
Сообщений всего: 237
Дата рег-ции: Июнь 2013  


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




Значительно упростил свою функцию, убрав рекурсивный вызов:
PHP:
скопировать код в буфер обмена
  1. function checkBrackets($str) {
  2.     $clean_str = preg_replace('/[^{}()\[\]]*/i', '', $str);
  3.     $length = strlen($clean_str);
  4.     if ($length % 2 === 1)
  5.         return false;
  6.     for ($i = 0; $i < $length / 2; ++$i)
  7.         $clean_str = str_replace(array('{}', '()', '[]'), '', $clean_str);
  8.     return empty($clean_str);
  9. }
  10.  
  11. //Проверка:
  12. $input = array('aa({}]', 'foo', 'foo()', ']', 'asd()asd{[asd]}ads[as{()aa}]');
  13. foreach ($input as $item) {
  14.     var_dump(checkBrackets($item));
  15. }
  16. unset($item);
  17. /*
  18. boolean false
  19. boolean true
  20. boolean true
  21. boolean false
  22. boolean true
  23. */

Интересно, насколько оптимально такое решение? При желании, от регулярки, очищающей строку, можно избавиться.

(Отредактировано автором: 25 Июля, 2013 - 14:38:41)

 
 Top
Страниц (9): « 1 2 3 4 [5] 6 7 8 9 »
Сейчас эту тему просматривают: 1 (гостей: 1, зарегистрированных: 0)
« Прочее »


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



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

 
Powered by ExBB FM 1.0 RC1. InvisionExBB