Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Проверить правильность выражения

Автор: AlexP11223 1.4.2012, 20:21

Подскажите, как надо решать эту задачу? Что почитать?

Цитата

Проверить правильность выражения, заданного в виде строки S
<выражение> ::= <цифра> | <выражение> + <цифра> | <выражение> – <цифра>
Если выражение составлено правильно, то вывести 0, в противном случае вывести номер первого ошибочного (или лишнего) символа в строке S.

Автор: DarkProg 1.4.2012, 20:32

Парсинг строк и рекурсию.

Автор: AlexP11223 1.4.2012, 20:49

Парсить строки я умею, а рекурсию как использовать? Можно ссылку на что-нибудь по этой теме, а то что-то не особо гуглится?

Автор: ksnk 1.4.2012, 21:41

на каком языке решать-то?
imho, метод рекурсивного спуска наиболее практичен для самодельных парсеров.

Автор: AlexP11223 1.4.2012, 21:57

Pascal/Delphi

Автор: _Y_ 1.4.2012, 22:01

Цитата(Omfgnoob123 @ 1.4.2012, 20:49

)

рекурсию как использовать

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

Понятно, что не только со скобками так. Приоритет операций, например, разбивать можно аналогичным образом.

ЗЫ: Во многих языках вроде бы есть встроенные или подключаемые библиотеки для парсинга мат или булевых выражений, записаннных текстом.

Автор: AlexP11223 2.4.2012, 00:07

А правильно ли я понимаю, что <выражение> ::= <цифра> | <выражение> + <цифра> | <выражение> – <цифра> означает, что строка S может быть
либо 8
либо 8 + 3
либо 8 - 3 (где 8 число, где 3 любая цифра)
или как? какие еще есть варианты? Что означает <выражение>?

Автор: ksnk 2.4.2012, 07:44

Omfgnoob123,

правильнее будет переписать эту конструкцию так

Код


<операция> ::= "+"|"-"
<выражение> ::= <цифра> [ <операция> <выражение >]

Вот и рекурсия почти в чистом виде.

Автор: DarkProg 2.4.2012, 19:17

Цитата(Omfgnoob123 @ 2.4.2012, 01:07

)

Что означает <выражение>?

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

Код


procedure MyInc(Var p, s:integer);
begin
  p:=p+1;
  if p<s then MyInc(p, s);
end;

Я думаю понятно, хотя сама по себе функция бессмысленна.

Автор: AlexP11223 25.5.2012, 20:59

Сделал с помощью этого самого рекурсивного спуска, однако препод сказал, что надо через дерево.

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

Автор: Pavia 26.5.2012, 08:49

Omfgnoob123,
В данной постановки профессор дурак либо вы что-то не поняли. Так как при помощи дерева проверяются не грамматические правила, а семантические.

Дерево является результатом грамматического анализа. Вам всего навсего надо построить дерево в процессе вашего рекурсивного спуска.
Делается это при выходи из рекурсии добавляя результирующее дерево, то в левое, то в правое поддерево.

Автор: user07 19.12.2012, 14:49

НУ, КАКИЕ ПРЕДЛОЖЕНИЯ ИМЕЮТСЯ ПО ЗАДАННОЙ ЗАДАЧЕ??? smile

Проверить правильность выражения, заданного в виде строки S. Если выражение составлено правильно, то вывести 0, в противном случае вывести номер первого ошибочного (или лишнего) символа в строке S.
НА СИ++ ИЛИ PASCAL

Автор: maxim1000 19.12.2012, 17:00

user07, если вопрос в алгоритме для той задачи, которая описана, то в теме уже есть ответ

если нужна конкретная реализация - лучше в http://forum.vingrad.ru/Vingrad-help-center.html

Автор: Akina 19.12.2012, 17:41

Цитата(Omfgnoob123 @ 1.4.2012, 21:21

)

<выражение> ::= <цифра> | <выражение> + <цифра> | <выражение> – <цифра>

Цитата(ksnk @ 2.4.2012, 08:44

)

<операция> ::= "+"|"-"
<выражение> ::= <цифра> [ <операция> <выражение >]

Неэквивалентно.
1+2 соответствует второму, но не соответствует первому.

Добавлено через 6 минут и 9 секунд

Цитата(Omfgnoob123 @ 2.4.2012, 01:07

)

Неправильно понимаешь.
Вот пример простого выражения:
1+2-9
При этом на месте цифр 1 и/или 2 может стоять легитимное выражение. Например, если такое легитимное выражение будет 3+4-5, и оно стоИт только вместо первой цифра, то ты имеешь легитимное выражение:
3+4-5+2-9
Если вместо второй, то:
1+3+4-5-9
Если вместо обеих, то:
3+4-5+3+4-5-9
В любом из этих трёх выражений любая цифра любого подвыражения точно так же может быть заменена на любое легитимное выражение. Неограниченное количество раз.

Автор: Akina 19.12.2012, 19:42

На самом деле в данной конкретной задаче всё проще.
В легитимном выражении:
1) Перваый и последний символы - цифры;
2) После цифры - знак плюс или минус;
3) После знака - цифра;
4) Количество плюсов в любом фрагменте от начала не меньше количества минусов;
5) Общее количество плюсов равно количеству минусов.
Так что просто сканируем строку до первого несоответствия. Не встретилось - последовательность легитимна. Встретилось - это и есть начало косяка.

Автор: ksnk 19.12.2012, 22:30

Цитата(Akina @ 19.12.2012, 17:41

)

Неэквивалентно.
1+2 соответствует второму, но не соответствует первому.

Это как это? Что такое второе и что такое первое?
В моей записи, операция это либо литера '-' либо литера '+'. Выражение, это число, но если после числа идет опрерация, то за операций идёт еще одно выражение.

1+2 вполне вписывается в мою грамматику.

Автор: Akina 19.12.2012, 23:18

Цитата(ksnk @ 19.12.2012, 23:30

)

Что такое второе и что такое первое?

Первое - определение в первой цитате в моём постинге, автор Omfgnoob123.
Второе - определение во второй цитате в моём постинге, автор ksnk.

Цитата(ksnk @ 19.12.2012, 23:30

)

1+2 вполне вписывается в мою грамматику.

Но совершенно не вписывается в грамматику исходного постинга. Какой смысл решать задачу, которую топикстартер не задавал?

Автор: ksnk 19.12.2012, 23:23

Цитата(Akina @ 19.12.2012, 23:18

)

Какой смысл решать задачу, которую топикстартер не задавал?

Цитата

<выражение> ::= <цифра> | <выражение> + <цифра> | <выражение> – <цифра>

Это как это не задавал? smile

Автор: Akina 20.12.2012, 08:47

ksnk, а ты-то ему какую предложил решать? совсем другую.

Автор: ksnk 20.12.2012, 09:24

Цитата(Akina @ 20.12.2012, 08:47

)

ksnk, а ты-то ему какую предложил решать? совсем другую.

Почему другую? Моя грамматика эквивалентна заданной. Это, imho, очевидно, но можно попытаться и формально это доказать.
Но в моей записи она, imho, более подходит к прямой реализации на ЯВУ.

Да и вообще, насколько разумно продолжать тред, начатый 1 апреля? smile

Автор: Akina 20.12.2012, 09:40

Цитата(ksnk @ 20.12.2012, 10:24

)

Моя грамматика эквивалентна заданной. Это, imho, очевидно

Как всё запущено...
Что выражение "1+2" соответствует твоей грамматике, мы уже договорились.
А вот теперь будь любезен показать, что оно соответствует ИСХОДНОЙ грамматике

Код


<выражение> ::= <цифра> | <выражение> + <цифра> | <выражение> – <цифра>

Когда будешь показывать, не забудь учесть, что скобок, указывающих на необязательность какого-то фрагмента, в ней не наблюдается.

Автор: ksnk 20.12.2012, 11:55

Цитата(Akina @ 20.12.2012, 09:40

)

А символы | не означают выбор одного из 3-х возможных вариантов <выражения>?

Автор: Akina 20.12.2012, 12:03

Нет, конечно... поскольку нет скобок, формирующих группу лексем, этот символ означает выбор одного варианта из двух возможных лексем. Т.е. сначала цифра либо выражение, потом строго плюс, потом снова цифра либо выражение, потом строго минус, потом строго цифра.

Автор: ksnk 20.12.2012, 12:37

Хмм... скобок нет, действительно.

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