Вычисления выражени, Проблемка... Опции

[Relrin]

Необходима помощь в задаче. Суть ее состоит в следующем: Необходимо с помощью рекурсии вычислить значение выражения, представленного в виде некоторого "константного выражения". То есть, вы вводим некоторую строку, и потом работаем с нем, вычисляя необходимое
Примеры таких выражений: 24; 2*2+2; (634+45); ((7-121)*32)

Мой код получился следующим:

Uses Crt;

Var
  str : string;
  c,op: char;
  x,y : integer;

{Подсчет значения выражения с помощью рекурсии}
{i - индекс соотв. символа}
{s - строка с выражением}
Function Res(i:integer; s:string):integer;
Begin
  c:=s[i];
  {Перевод в число целого типа}
  if (c>='0') and (c<='9') then
    Res:=Ord©-ord('0')
  {Арифметические операции с операндами}
  else
    begin
      x:=Res(i,s);
      inc(i);
      op:=s[i];
      inc(i);
      c:=s[i];
      y:=Res(i,s);
      case op of
        '+': Res:=x+y;
        '-': Res:=x-y;
        '*': Res:=x*y;
      end;
      inc(i);
      c:=s[i];
    end;
End;

{Основная программа}
Begin
  clrscr;
  write('Исходное выражение: ');
  readln(str);
  writeln('Значение выражения: ',Res(1,str));
  readkey;
End.

Сообщение отредактировано: Relrin - 8.04.2011 20:09

[Гость]

Во-первых, не
Function Res(i:integer; s:string):integer;
а
Function Res(i:integer; const s:string):integer;


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

Также тебе придётся распознавание чисел вынести в отдельную процедуру, потому что пока что у тебя только цифра распознаётся.

Ссылка на статью с готовым алгоритмом давать не хочу, потому что то, что есть, уже неплохо, надо только довести.

[Relrin]

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;

[Гость]

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]

Переделал, теперь берет и 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;

Сообщение отредактировано: Relrin - 9.04.2011 0:41

[TarasBer]

В общем, переделать чуть-чуть у меня не вышло, к сожалению.
Переделал дофига (то есть как бы делал я).

Вышло так:

{$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;

begin
  i := 1;
  Result := Res(0);
end;

{Основная программа}
Begin
  write('Исходное выражение: ');
  readln(str);
  writeln('Значение выражения: ',Value(str));
  readln;
End.

А общая теория тут: http://algolist.manual.ru/syntax/parsear.php

[Relrin]

За помощь! Пока читаю "теорию"+разбираю код. До этого пару раз проверил пару примеров, типа (634+45), однако результат получил 0. Вопрос: как это исправить?

Сообщение отредактировано: Relrin - 9.04.2011 1:16

[TarasBer]

> До этого пару раз проверил пару примеров, типа 7-121+3, однако результат получил 0.

В смысле, у тебя?
(я у себя проверил - у меня выдаёт -117, но вот на пробелы он реагировать не умеет, значит, надо вставить код, пропускающий пробелы. Только не вздумай писать код, УДАЛЯЮЩИЙ пробелы!!! Их надо именно пропускать, а не удалять.)

> Вопрос: как это исправить?

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

Сообщение отредактировано: TarasBer - 9.04.2011 1:20

[Relrin]

Ошибка найдена!
Вот это:

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]

Не верю.
(634+45) работает в моём варианте.
В моём вообще всё работает (кроме пробелов), не?
Кстати, Д7 на твоё код выдаёт предупреждение: из-за того, что ты тмп+приор внёс в условие, оно стало "возможно не определено".
И ещё почему-то 2(2+2) стало равно 4.

[Relrin]

Не верю.
(634+45) работает в моём варианте.
В моём вообще всё работает (кроме пробелов), не?
Кстати, Д7 на твоё код выдаёт предупреждение: из-за того, что ты тмп+приор внёс в условие, оно стало "возможно не определено".
И ещё почему-то 2(2+2) стало равно 4.

У меня все обратно. Все так, в подправленном, работает как надо
Скриншот как подтверждение

[TarasBer]

Ты покажи выражение, которое НЕ работает в моём варианте.
А в свой вбей 2(2+2)

[Relrin]

Ты покажи выражение, которое НЕ работает в моём варианте.
А в свой вбей 2(2+2)

Если указать 2(2+2), то конечно 4 будет, т.к. знака между 2 и скобками нету
В изначальном варианте, у меня не работает варианты:
(7-121)=0
(634+45)*3=0
((7-121)+3)=0
т.е. выражение, где есть скобки, показывает результат 0
у меня же, в подправленном варианте, эти варианты, как и без скобок решает без проблем

[TarasBer]

> В изначальном варианте, у меня не работает варианты:
(7-121)=0
(634+45)*3=0
((7-121)+3)=0
т.е. выражение, где есть скобки, показывает результат 0

Да ты просто походу пробел в начале выражения поставил. Всё в моём варианте прекрасно работает.
Хоть сейчас перепроверь и отладчиком пройдись.
Либо ты сначала сделал с ним что-то не то.

Так вот, если ты его покорёжил, то это не о мне претензии. Потому что я его проверил и отладил.

> Если указать 2(2+2), то конечно 4 будет, т.к. знака между 2 и скобками нету

А вот мой вариант останавливает разбор после первой двойки. И в него намного проще добавить диагностику неверных выражений.

[Relrin]

Да ты просто походу пробел в начале выражения поставил. Всё в моём варианте прекрасно работает.
Хоть сейчас перепроверь и отладчиком пройдись.
Либо ты сначала сделал с ним что-то не то.

Пробелы как раз-таки я не вводил. Сразу вводил необходимое выражение

[TarasBer]

Значит, что-то не то сделал с моим кодом.

Судя по ошибке, ты куда-то дел елсе при переписывании того фрагмента. И почему, вместо того, чтобы внимательно посмотреть, правильно ли ты переписал код и восстановить елсе, ты просто дописал точкозапятую после тхена и перенёс явное присвоение тмп_приор в одну из ветвей, заставляя компилятор выдавать предупреждение?

Сообщение отредактировано: TarasBer - 9.04.2011 3:06