Модераторы: Aliance, IZ@TOP, SamDark, skyboy, MoLeX, ksnk, ksnk, ksnk
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Рекурсивный разбор строки, a( b( c( ) ) ) 
V
    Опции темы
flashaa
Дата 21.1.2008, 19:15 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 796
Регистрация: 7.3.2006

Репутация: 2
Всего: 25



Создаю парсер формул, т.к. не нашел готового универсального решения.
Работает он так: подаем строку вида tg(log(x)/sqrt(y)).
Эту строку необходимо преобразовать в красивый HTML-код формулы:отношение должно быть записано как дробь, sqrt как корень и тп. 
Возникла проблема из-за вложенности ф-ций. Допустим если формула представляет собой f( g( x ) ),
то при попытке разобрать такую строку регулярным выражением означающим формулу, получаю то, что парсер вылавливает первую открывающую и первую закрывающую скобки, т.е. вот так - f( g( x ) ). Несложно догадаться, что мое регулярное выражение для формул вычленяет открывающую и закрывающую скобки. Собственно вопрос: какой должна быть регулярка или может быть сам подход к решению этой задачи, что программа смогла получить именно содержимое соответствующих друг другу открывающей и закрывающей скобок? А не брала первые попавшиеся.

Добавлено через 9 минут и 59 секунд
P.S. решение для парсинга формул в соседней теме. Но задачка с рекурсивным разбором остается актуальной.
PM MAIL   Вверх
Mayk
Дата 21.1.2008, 19:33 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


^аВаТаР^ сообщение>>
****


Профиль
Группа: Участник
Сообщений: 2616
Регистрация: 22.5.2005
Где: за границей разум а

Репутация: нет
Всего: 134



Цитата(flashaa @  21.1.2008,  23:15 Найти цитируемый пост)
ли может быть сам подход к решению этой задачи, что программа смогла получить именно содержимое соответствующих друг другу открывающей и закрывающей скобок

Например рекурсивным нисходящим парсером (подробности в гугле).



--------------------
 Здесь был кролик. Но его убили.
Человеки < кроликов, йа считаю.
PM MAIL WWW ICQ   Вверх
skyboy
Дата 21.1.2008, 19:35 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


неОпытный
****


Профиль
Группа: Модератор
Сообщений: 9820
Регистрация: 18.5.2006
Где: Днепропетровск

Репутация: 8
Всего: 260



Цитата(flashaa @  21.1.2008,  18:15 Найти цитируемый пост)
рограмма смогла получить именно содержимое соответствующих друг другу открывающей и закрывающей скобок?

включи жадность. тогда регулякра из 
Цитата

f( g( x ) )

выберет сначала
"f( g ( x ) )" и "g ( x )".
потом рекурсивно обработать "g ( x )", чтоб выбрать "x".

Добавлено через 3 минуты и 13 секунд
правда, вариант с использованием жадности прокатывает только в отсутствие операторов - только при использовании функций(в противном случае из "g( f( x ) ) + a ( y ( k ) )" будет выбрано "f ( x ) ) + a ( y ( k )", что не есть правильно).
PM MAIL   Вверх
sTa1kEr
Дата 22.1.2008, 18:45 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


9/10 программиста
***


Профиль
Группа: Завсегдатай
Сообщений: 1553
Регистрация: 21.2.2007

Репутация: 5
Всего: 146



Так ведь в PCRE есть рекурсивные шаблоны. В документации они достаточно хорошо описаны. Т.е. в вашем случае шаблон будет выглядеть примерно так:
Код

$str = "a + b(x) + 6 * 7 ^ cos( log( 10 ) ) / z";
$pattern = "/\s* ( \w+ | \w*\s*\(((?R)+)\)  ) \s* ( [+\-*\/\^] | $ | (?=\)) )/isx";
preg_match_all($pattern, $str, $m, PREG_SET_ORDER);
var_dump($m);

Т.о мы захватим все последовательности операнд-оператор:
$m[0][1] - Операнд (слово/цифра, функция или скобки со всеми "своими" операнд-операторами внутри)
$m[0][3] - Оператор или пусто, если конец строки.
$m[0][2] - Строка внутри скобок, которую можно так же распарсить этим шаблоном (можно даже через callback)

Это сообщение отредактировал(а) sTa1kEr - 22.1.2008, 18:46
PM MAIL   Вверх
flashaa
Дата 22.1.2008, 21:46 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 796
Регистрация: 7.3.2006

Репутация: 2
Всего: 25



Всем спасибо, Stalker - реальное решение. Пытался разобраться с ?R, изучая обработку вложенных конструкций {} в DbSimple, но так собственно и на том все и затухло.

Код

 function _expandPlaceholdersFlow($query)
    {
        $re = '{
            (?>
                # Ignored chunks.
                (?>
                    # Comment. 
                    -- [^\r\n]* 
                ) 
                  |
                (?> 
                    # DB-specifics.
                    ' . trim($this->_performGetPlaceholderIgnoreRe()) . '
                )
            ) 
              |
            (?> 
                # Optional blocks
                \{
                    # Use "+" here, not "*"! Else nested blocks are not processed well.
                    ( (?> (?>[^{}]+)  |  (?R) )* )             #1
                \}
            )
              |
            (?>
                # Placeholder
                (\?) ( [_dsafn\#]? )                           #2 #3
            )
        }sx';
        $query = preg_replace_callback(
            $re,
            array(&$this, '_expandPlaceholdersCallback'), 
            $query
        );
        return $query;
    }


Это сообщение отредактировал(а) flashaa - 22.1.2008, 21:48
PM MAIL   Вверх
sTa1kEr
Дата 23.1.2008, 12:25 (ссылка) |    (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


9/10 программиста
***


Профиль
Группа: Завсегдатай
Сообщений: 1553
Регистрация: 21.2.2007

Репутация: 5
Всего: 146



flashaa, ну в общем то ничего сложного я не вижу в этом шаблоне.

Первые скобки - любые комменты sql или специфичные для БД. Не захватываются (видимо просто вырезается все что попало под условие)

Третьи - это видимо для биндинга параметров определеного типа ?d, ?_, etc.

Вторые - это фигурные скобки с любым количеством вложенных "правильных" скобок. Видимо это какие-то шаблоны, которые потом заменяются нужными данными, т.ч. для того что бы правильно распарсить множество таких шаблонов и используется рекурсия.  Что бы понять как она работает (нужно понять как она работает smile ...) можно просто заменить конструкцию (?R) самим шаблоном столько раз, на сколько хватит терпенья(сил, места на винте, прочности клавиш Cntrl+V). Предположим укоротим этот шаблон, оставим только вторые скобки:
Код

$re = '{
\{(
   (?>
      (?>[^{}]+)
   |
      #BEGIN R
      (?R)
      #END R
   )*   
)\}           
}sx';

И заменим 3 раза (?R)
Код

$re = '{
\{(
   (?>
      (?>[^{}]+)
   |
      #BEGIN R
\{(
   (?>
      (?>[^{}]+)
   |
      #BEGIN R
\{(
   (?>
      (?>[^{}]+)
   |
      #BEGIN R
\{(
   (?>
      (?>[^{}]+)
   |
      #BEGIN R
      (?R)
      #END R
   )*   
)\}           
      #END R
   )*   
)\}           
      #END R
   )*   
)\}           
      #END R
   )*   
)\}           
}sx';

Т.е. после открывающийся скобкой должны идти любые не скобки или открывающиеся скобки и любые не скобки... и затем стока же раз закрывающиеся скобки. На пример из текста " {a} + {b{c}} {d} } " корректно попадет под условие {a}, целиком {b{c}}, и {d}, а последняя скобка останется.
PM MAIL   Вверх
flashaa
Дата 24.1.2008, 00:13 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 796
Регистрация: 7.3.2006

Репутация: 2
Всего: 25



Sta1kEr, спасибо за подробное пояснение. вот действие ?R как раз и не совсем понятно было. Значит, разбор рекурсивно вложенного, если так можно сказать, самого в себя шаблона, реализуем с помощью рекурсивного вызова preg_replace_callback, получая сначала внешние экземпляры шаблона, затем все более и более вложенные, как капусту чистим =)
PM MAIL   Вверх
Google
  Дата 19.4.2019, 01:38 (ссылка)  





  Вверх
  
Ответ в темуСоздание новой темы Создание опроса
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | PHP: Тексты | Следующая тема »


 




[ Время генерации скрипта: 0.2474 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.