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

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

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

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

Pascal/Delphi

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

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

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

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


Это сообщение отредактировал(а) Omfgnoob123 - 2.4.2012, 00:15

Omfgnoob123, 

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



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

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

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

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

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

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

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

Это сообщение отредактировал(а) Pavia - 26.5.2012, 08:58

НУ, КАКИЕ ПРЕДЛОЖЕНИЯ ИМЕЮТСЯ ПО ЗАДАННОЙ ЗАДАЧЕ??? 
Проверить правильность выражения, заданного в виде строки S. Если выражение составлено правильно, то вывести 0, в противном случае вывести номер первого ошибочного (или лишнего) символа в строке S.  
НА СИ++ ИЛИ PASCAL

Это сообщение отредактировал(а) user07 - 19.12.2012, 14:51

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

если нужна конкретная реализация - лучше в Центр Помощи

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

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

Неправильно понимаешь.
Вот пример простого выражения:
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
В любом из этих трёх выражений любая цифра любого подвыражения точно так же может быть заменена на любое легитимное выражение. Неограниченное количество раз.

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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