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

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

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

на каком языке решать-то? 
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) Общее количество плюсов равно количеству минусов.
Так что просто сканируем строку до первого несоответствия. Не встретилось - последовательность легитимна. Встретилось - это и есть начало косяка.