ВВ
Я про PEG грамматику (разбирающую выражения).
А, ОК. Подумал, РВ — это регулярные выражения.
Size: a a a
2020 April 20
v
А, ОК. Подумал, РВ — это регулярные выражения.
parser parser(R"(
EXPRESSION <- TERM (TERM_OPERATOR TERM)*
TERM <- FACTOR (FACTOR_OPERATOR FACTOR)*
FACTOR <- NUMBER / '(' EXPRESSION ')'
TERM_OPERATOR <- < [-+] >
FACTOR_OPERATOR <- < [/*] >
NUMBER <- < [0-9]+ >
%whitespace <- [ \t\r\n]*
)");
Ее можно редуцировать, оставив только скобки?
v
А, ОК. Подумал, РВ — это регулярные выражения.
PEG использует кванторы и группы, как в регулярках.
ВВ
Так пойдёт?
EXPR <- ('(' EXPR ')')*v
Так пойдёт?
EXPR <- ('(' EXPR ')')*ВВ
О, прикольная штука!
ВВ
Спасибо за ссылки! Давно с грамматиками не сталкивался, и как раз сегодня днём думал, что бы такого поковырять. А с этой библиотекой будет интереснее. :)
A
кто-нибудь может подсказать,как выразить функции остаток от деление и целую часть от деления через базис Клини?
i
Ребят, а у меня такая просьба. Можете помочь понять решение.
Есть строка, которая состоит из '(', ')', '*' и нужно определить валидная ли расстановка скобок. Звёздочки можно рассматривать как пустота, или открывающаяся скобка, или закрывающаяся.
(*)( -> invalid
(()(**) -> valid
(*())) -> valid
Решение такое.
Пройдемся по массиву с лева направо и на каждом шаге проверяем, валидная ли расстановка скобок, если считать каждую звёздочку как левую.
Потом справа на лево, проверяя на каждом шаге, валидная ли перестановка, если считать * как правая.
Если до этого мы не вернули false, то здесь возвращаем true. То есть что перестановка валидная.
Но я не могу понять последний шаг
Есть строка, которая состоит из '(', ')', '*' и нужно определить валидная ли расстановка скобок. Звёздочки можно рассматривать как пустота, или открывающаяся скобка, или закрывающаяся.
(*)( -> invalid
(()(**) -> valid
(*())) -> valid
Решение такое.
Пройдемся по массиву с лева направо и на каждом шаге проверяем, валидная ли расстановка скобок, если считать каждую звёздочку как левую.
Потом справа на лево, проверяя на каждом шаге, валидная ли перестановка, если считать * как правая.
Если до этого мы не вернули false, то здесь возвращаем true. То есть что перестановка валидная.
Но я не могу понять последний шаг
Стек
i
А есть РВ грамматика правильных скобочных выражений? Я не могу построить ее из грамматики калькулятора с скобками.
Стэк и все
P
Стек
Ну решение выше за O(1) по доп памяти.
v
Ну решение выше за O(1) по доп памяти.
А сколько памяти в packrat парсере?
i
Вряд ли за о1
P
А сколько памяти в packrat парсере?
packrat?
i
Даже счётчик в цикле требует логарифм памяти
CD
Ну решение выше за O(1) по доп памяти.
щито?
CD
скобочную последовательность на правильность за О(1) памяти проверяем? :)
P
Даже счётчик в цикле требует логарифм памяти
В смысле? Логарифм от чего?