Необходима помощь в задаче. Суть ее состоит в следующем: Необходимо с помощью рекурсии вычислить значение выражения, представленного в виде некоторого "константного выражения". То есть, вы вводим некоторую строку, и потом работаем с нем, вычисляя необходимое Примеры таких выражений: 24; 2*2+2; (634+45); ((7-121)*32)
Во-первых, не Function Res(i:integer; s:string):integer; а Function Res(i:integer; const s:string):integer;
Я так понял, у тебя приоритеты операций и скобки не учитываются пока что. То, что есть, уже неплохо. Но, для того, чтобы алгоритм понимал приоритеты, надо, чтобы в функцию Res передавалась не только последняя позиция, но и приоритет последнего арифметического оператора.
Также тебе придётся распознавание чисел вынести в отдельную процедуру, потому что пока что у тебя только цифра распознаётся.
Ссылка на статью с готовым алгоритмом давать не хочу, потому что то, что есть, уже неплохо, надо только довести.
Relrin
8.04.2011 23:05
C приоритетами и скобками пока не очень могу представить как нужно сделать... А вот с выделением чисел подправил(правда, больше чем integer значения не берет).
{Выделения числа из строки} Function DetNumber(const s:string;pos: integer):longint; Var numb : string; j,q : longint; value: integer; Begin numb:=''; c:=s[pos]; while (c>='0') and (c<='9') do begin numb:=numb+s[pos]; inc(pos); c:=s[pos]; end; val(numb,value,q); DetNumber:=value; End;
{Подсчет значения выражения} Function Res(const s:string;prior:byte):longint; Begin c:=s[i]; {Выделение числа из строки} if (c>='0') and (c<='9') then Res:=DetNumber(s,i) {Арифметические операции} else begin x:=Res(s,prior); inc(i); op:=s[i]; inc(i); c:=s[i]; y:=Res(s,prior); case op of '+': Res:=x+y; '-': Res:=x-y; '*': Res:=x*y; end; inc(i); c:=s[i]; end; End;
Гость
8.04.2011 23:51
1. Перепиши определитель числа без библиотечного val. Перебор подстрок, для которых вал сработает - это лажа. 2.
y:=Res(s,prior); case op of '+': Res:=x+y; '-': Res:=x-y; '*': Res:=x*y; end;
Не так
case op of '+': Res:=x+Res(s, 1); '-': Res:=x-Res(s, 1); '*': Res:=x*Res(s, 2); '/': Res:=x div Res(s, 2); end;
И внутри res организуй цикл. В общем, пока ещё подумай, через час где-то я постараюсь написать полное решение на основе твоего.
Relrin
9.04.2011 0:38
Переделал, теперь берет и longint числа
Function DetNumber(const s:string;pos: integer):longint; Var numb : string; j,rate: longint; value : longint; Begin rate:=1; value:=0; numb:=''; c:=s[pos]; while (c>='0') and (c<='9') do begin numb:=numb+s[pos]; inc(pos); c:=s[pos]; end; for j:=1 to pos-1 do begin value:=(value*rate)+(Ord(numb[j])-ord('0')); if j=1 then rate:=rate*10 else rate:=10; end; DetNumber:=value; End;
TarasBer
9.04.2011 0:55
В общем, переделать чуть-чуть у меня не вышло, к сожалению. Переделал дофига (то есть как бы делал я).
Вышло так:
{$APPTYPE CONSOLE} var str : string;
{Подсчет значения выражения с помощью рекурсии} {s - строка с выражением} function Value(S: string): longint; var i: integer;
Function Res(prior: integer):longint; var sign: boolean; tmp_prior: integer; r: integer; // сюда будем писать результат
function GetNumber: boolean; // возвращает, получилось ли взять число var start_i: integer; begin start_i := i; result := false; r := 0; sign := false; if i <= Length(s) then case s[i] of '-' : begin // минус перед числом sign := true; inc(i); end; '+' : begin // плюс перед числом sign := false; inc(i); end; end; while (i <= Length(s)) and (s[i] in ['0' .. '9']) do begin // собираем число по цифрам r := r * 10 + (ord(s[i]) - ord('0')); result := true; inc(i); end; if sign then r:= -r; if not result then i := start_i; // если не удалось взять число, возвращаем указатель на место end;
Begin {Перевод в число целого типа} if GetNumber then // взяли число, значит r стал какой надо, значит, всё в порядке else if s[i] = '(' then begin // рекурсивно разобрать то, что внутри скобки inc(i); r := Res(0); if s[i] = ')' then inc(i); // а если нет, то это ошибка выражения end;
tmp_prior := 0; while (i <= Length(s)) do begin
case S[i] of // определить приоритет текущей операции '+': tmp_prior := 1; '-': tmp_prior := 1; '*': tmp_prior := 2; '/': tmp_prior := 2; else break; end;
if tmp_prior < prior then break; // тут и учитываетя приоритет операций! // если приоритет новой операции ниже текущего, то надо выйти из рекурсии // на уровень выше - пусть новую операцию обрабатывают на том уровне
case S[i] of '+': begin inc(i); r := r + Res(tmp_prior); end; '-': begin inc(i); r := r - Res(tmp_prior); end; '*': begin inc(i); r := r * Res(tmp_prior); end; '/': begin inc(i); r := r div Res(tmp_prior); end; else break; end; end; result := r; End;
За помощь! Пока читаю "теорию"+разбираю код. До этого пару раз проверил пару примеров, типа (634+45), однако результат получил 0. Вопрос: как это исправить?
TarasBer
9.04.2011 1:18
> До этого пару раз проверил пару примеров, типа 7-121+3, однако результат получил 0.
В смысле, у тебя? (я у себя проверил - у меня выдаёт -117, но вот на пробелы он реагировать не умеет, значит, надо вставить код, пропускающий пробелы. Только не вздумай писать код, УДАЛЯЮЩИЙ пробелы!!! Их надо именно пропускать, а не удалять.)
> Вопрос: как это исправить?
Долго сидеть с отладчиком, и понять, где не разбирается какой-то левый случай, точнее сказать не могу. При написании разборщика выражений всё ошибки именно такого мерзского характера - в какой-то ситуации надо сдвигать индекс, а в какой-то не надо, а в какой-то надо, но не так. Что-то общее сказать сложно. Из-за этого попытки написать надёжный разборщик превращаются в монструозный код с кучей проверок на каждом шагу.
Relrin
9.04.2011 1:48
Ошибка найдена! Вот это:
if GetNumber then // взяли число, значит r стал какой надо, значит, всё в порядке else if s[i] = '(' then begin // рекурсивно разобрать то, что внутри скобки inc(i); r := Res(0); if s[i] = ')' then inc(i); // а если нет, то это ошибка выражения end; tmp_prior := 0;
Изменил на вот это
if GetNumber then tmp_prior := 0; // взяли число, значит r стал какой надо, значит, всё в порядке if s[i] = '(' then begin // рекурсивно разобрать то, что внутри скобки inc(i); r := Res(0); if s[i] = ')' then inc(i); // а если нет, то это ошибка выражения end;
и заработало
TarasBer
9.04.2011 1:55
Не верю. (634+45) работает в моём варианте. В моём вообще всё работает (кроме пробелов), не? Кстати, Д7 на твоё код выдаёт предупреждение: из-за того, что ты тмп+приор внёс в условие, оно стало "возможно не определено". И ещё почему-то 2(2+2) стало равно 4.
Relrin
9.04.2011 2:04
Цитата(TarasBer @ 8.04.2011 21:55)
Не верю. (634+45) работает в моём варианте. В моём вообще всё работает (кроме пробелов), не? Кстати, Д7 на твоё код выдаёт предупреждение: из-за того, что ты тмп+приор внёс в условие, оно стало "возможно не определено". И ещё почему-то 2(2+2) стало равно 4.
У меня все обратно. Все так, в подправленном, работает как надо Скриншот как подтверждение
TarasBer
9.04.2011 2:10
Ты покажи выражение, которое НЕ работает в моём варианте. А в свой вбей 2(2+2)
Relrin
9.04.2011 2:17
Цитата(TarasBer @ 8.04.2011 22:10)
Ты покажи выражение, которое НЕ работает в моём варианте. А в свой вбей 2(2+2)
Если указать 2(2+2), то конечно 4 будет, т.к. знака между 2 и скобками нету В изначальном варианте, у меня не работает варианты: (7-121)=0 (634+45)*3=0 ((7-121)+3)=0 т.е. выражение, где есть скобки, показывает результат 0 у меня же, в подправленном варианте, эти варианты, как и без скобок решает без проблем
TarasBer
9.04.2011 2:24
> В изначальном варианте, у меня не работает варианты: (7-121)=0 (634+45)*3=0 ((7-121)+3)=0 т.е. выражение, где есть скобки, показывает результат 0
Да ты просто походу пробел в начале выражения поставил. Всё в моём варианте прекрасно работает. Хоть сейчас перепроверь и отладчиком пройдись. Либо ты сначала сделал с ним что-то не то.
Так вот, если ты его покорёжил, то это не о мне претензии. Потому что я его проверил и отладил.
> Если указать 2(2+2), то конечно 4 будет, т.к. знака между 2 и скобками нету
А вот мой вариант останавливает разбор после первой двойки. И в него намного проще добавить диагностику неверных выражений.
Relrin
9.04.2011 2:44
Цитата(TarasBer @ 8.04.2011 22:24)
Да ты просто походу пробел в начале выражения поставил. Всё в моём варианте прекрасно работает. Хоть сейчас перепроверь и отладчиком пройдись. Либо ты сначала сделал с ним что-то не то.
Пробелы как раз-таки я не вводил. Сразу вводил необходимое выражение
TarasBer
9.04.2011 2:47
Значит, что-то не то сделал с моим кодом.
Судя по ошибке, ты куда-то дел елсе при переписывании того фрагмента. И почему, вместо того, чтобы внимательно посмотреть, правильно ли ты переписал код и восстановить елсе, ты просто дописал точкозапятую после тхена и перенёс явное присвоение тмп_приор в одну из ветвей, заставляя компилятор выдавать предупреждение?
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.