1 курс. Задача. ПОЛИЗ.

На семинаре 1ПМ в подгруппе В.Ш. была задана задача по реализации вычисления выражения с использованием стека, заданного в виде ПОЛИЗ.
Условия и ограничения:
1)Решение оформляется как функция целого типа.
2)Функция имеет один исходный параметр - сама ПОЛИЗ, заданная виде стринга.
3)Каждый символ стринга либо дес. цифра, либо '+', '-' или '*'.
4)Используемый стек локализован внутри самой функции.

Вот пример реализации.

  1. program Polsk_zapis;
  2. var s:string;
  3.  
  4. FUNCTION Polsk_zapis(s:string):integer;
  5. const lim=256;
  6. type T=array [1..lim] of integer;
  7. var
  8.  mas:T;
  9.  top,a,i,c:integer;
  10. procedure push (v:integer);
  11. begin
  12.  if top=lim then writeln('Error: stack overflow')
  13.  else begin
  14.    inc(top);
  15.    mas[top]:=v;
  16.  end;
  17. end;
  18. function pop ():integer;
  19. begin
  20.  if 1<=top then begin
  21.    pop:=mas[top];
  22.    dec(top)
  23.  end
  24. end;
  25. function emp():boolean;
  26. begin
  27.  if top=0 then emp:=false
  28.  else emp:=true
  29. end;
  30. procedure ini ();
  31. begin
  32.  top:=0;
  33. end;
  34.  
  35. function correct():boolean;
  36. begin
  37.   if c<2 then begin
  38.     writeln;
  39.     write('Полиз ошибочна ');
  40.     correct:=false
  41.   end
  42.   else correct:=true;
  43.   dec(c);
  44. end;
  45.  
  46. Begin
  47.   ini;
  48.   c:=0;
  49.   for i:=1 to length(s) do begin
  50.     case s[i] of
  51.       '*': if correct then begin
  52.              push(pop * pop);
  53.            end;
  54.       '+': if correct then begin
  55.              push(pop + pop);
  56.            end;
  57.       '-': if correct then begin
  58.              push(-pop + pop); //Т.к. операция "-" не коммутативна
  59.            end;                // a-b = -b+a
  60.     else //case
  61.       inc(c);
  62.       push(ord(s[i]) - ord('0'));
  63.     end;//case
  64.  
  65.   end;//for
  66.   if c=1 then Polsk_zapis:=pop
  67.   else begin
  68.     write('Полиз ошибочна');
  69.     Polsk_zapis:=0;
  70.   end
  71. End;
  72.  
  73.  
  74. BEGIN
  75.   writeln('Введите полиз без пробелов');
  76.   readln(s);
  77.   writeln('Результат: ',Polsk_zapis(s));
  78.   readln;
  79. END.

Неплохо бы сделать так, чтобы

Неплохо бы сделать так, чтобы функция учитывала ошибки ввода ПОЛИЗ и сообщала об этом, а не выводила неправильный ответ.
Какие есть идеи, предложения, замечания?

Всё правильно, Антон. Но есть 2 вопроса:

Всё правильно, Антон. Но есть 2 вопроса:
1. Почему стек начинается с индекса 0 (некомфортно работать с -1)?
2. Зачем нужна переменная L (это ведь не очередь, и нет необходимости значения L когда-либо менять)?

По поводу же контроля ошибок входной строки, предлагаю следующий алгоритм. Завести счётчик. В for-цикле обработки стринга к счётчику прибавлять единицу, если текущий символ цифра и отнимать единицу, если знак операции. При этом конечно следить, чтобы других знаков не появлялось. Если счётчик по ходу обработки обнулится или по завершению обработки не примет значение 1, регистрируем ошибку.
Проверьте, мне кажется сработает.

ПОЛИЗ

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

ПОЛьской Инверсной Записью (ПОЛИЗ) называется бесскобочная форма записи выражений, в которой любой знак операции непосредственно следует за своими операндами.

Например, 2*((5-7)+3) в ПОЛИЗ запишется как 2,5,7,-,3,+,*

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

Действуем так.
Очищаем стек и посимвольно слева направо просматриваем ПОЛИЗ. Если текущим символом является операнд (элемент данных), то он загружается в стек. Если попадается знак операции, то эта операция выполняется над верхними элементами стека (которые из него удаляются). Результат выполненной операции помещается в стек. По завершению просмотра входной ПОЛИЗ-строки в стеке останется единственный элемент - вычисленное значение выражения.

Антон реализовал этот алгоритм для простейшего случая, когда данные в заданном ПОЛИЗ-выражении представлены цифрами, а операций всего три: +,-,*

Проверку ввел. Вроде бы все

Проверку ввел. Вроде бы все работает.
1. Трудно сказать... Изначально так сделал. Теперь переделал.
2. В переменной смысла нет. Теперь исправил.

И снова не идеал! Остаётся

И снова не идеал!
Остаётся непонятной возня вокруг несодержательных (немнемоничных для стека!) обозначений L и R. Значимым элементом информационной составляющей СТЕКА, как известно являются только его ВЕРХУШКА (традиционное и мнемоничное обозначение - top). ДНО стека (тогда уж bottom, а не L) обычно никак специально не обозначается. Впрочем, вся реализация и принятые в профессиональной среде обозначения даны в лекции. Странно, что Вы решили от них без всякой нужды отойти.

P.S. Поясню, как многим может показаться, свои "мелочные придирки" (программа-то работает!). Внимание к выбору обозначений - азбука профессионализма. Огрехи в освоении этой азбуки оказываются принципиальными, как только мы выходим за рамки "игрушечных" программ.

Сообщение является даблпостом

Сообщение является даблпостом и удалено.

Мой вариант решения

В настоящий момент я готов предложить свой вариант решения этой задачи. К сожалению, я делаю это с опозданием, так как у меня не всегда есть возможность попасть за компьютер.
Итак, для начала несколько комментариев. В своем варианте программы я реализовал операции сложения, вычитания, умножения и деления с отбрасыванием остатка для более чем однозначных целых чисел.
Основная функция работает в несколько этапов и использует два внешних булевских параметра (поэтому ее нельзя полноценно импортировать в другой проект, и поэтому она частично не соответствует критерию полноценной функции), говорящих о некорректности вводимой записи.
Последовательность шагов главной функции такова:
1) Ввод исходной строки, содержащей ПОЛИЗ;
2) Исправление строки (удаление ведущих, концевых и лишних пробелов и запятых);
3) Проверка на наличие лишних символов (выполняется отдельно, так как принципиально проста и если выявит некорректность стринга, то следующие шаги можно опустить);
4) Проверка на сбалансированность по алгоритму, предложенному Валерием Шахамболетовичем (если запись некорректна, то следующий шаг также можно опустить);
5) Вычисление ПОЛИЗ;
В теле проверяющей программы предусмотрен контроль ошибок по флагам, изменяемым в теле основной функции.
Из-за необходимости такого подхода, думаю, вычисление ПОЛИЗ лучше осуществить в виде процедуры вида:
procedure PolizCalc(s: string; var value: integer; var error: integer);
которая преобразует строковое представление s ПОЛИЗ к числовому значению и записывает его в переменную value. При этом error = 0, преобразование прошло успешно; error = 1, если в записи имеются лишние символы; error = 2, если запись несбалансированная.

  1. program ReversePolishNotation;
  2.  
  3. var
  4.   s: string;
  5.   x: integer;
  6.   incorrect, unbalanced: boolean; // флаги для передачи параметров из функции
  7.  
  8. function PolizCalc(s: string): integer;
  9. var
  10.   A: array[1..255] of integer; // массив для реализации стека
  11.   top: 0..255; // вершина стека
  12.   s1: byte; // переменная для хранения индекса подстроки
  13.   x, y: integer; // переменные для хранения операндов в целочисленном виде
  14.   z: string; // переменная для хранения текущего операнда или знака операции
  15.  
  16.   procedure correction; // процедура коррекции ошибок во входном стринге
  17.   var
  18.     s1: byte;
  19.   begin
  20.     s := trim(s); // удаляем ведущие и концевые пробелы
  21.     s1 := pos(',', s);
  22.     while s1 <> 0 do begin // в цикле заменяем все запятые пробелами
  23.       s[s1] := ' ';
  24.       s1 := pos(',', s)
  25.     end;
  26.     s1 := pos('  ', s);
  27.     while s1 <> 0 do begin // в цикле сокращаем все многопробельные конструкции до однопробельных
  28.       delete(s, s1, 1);
  29.       s1 := pos('  ', s)
  30.     end
  31.   end;
  32.  
  33.   function correct: boolean; // функция для обнаружения недопустимых символов
  34.   var
  35.     i: 1..255;
  36.     flag: boolean;
  37.   begin
  38.     flag := true;
  39.     if s = '' then begin // если стринг пуст, то выражение некорректно
  40.       flag := false
  41.     end;
  42.     i := 1;
  43.     while flag and (i <= length(s)) do begin
  44.       if (s[i] <> ' ') and (s[i] <> '+') and (s[i] <> '-') and (s[i] <> '*') and (s[i] <> '/') and ((s[i] < '0') or (s[i] > '9')) then begin
  45.         flag := false // если нашли недопустимый символ, то выражение некорректно
  46.       end;
  47.       inc(i)
  48.     end;
  49.     correct := flag
  50.   end;
  51.  
  52.   function balance: boolean; // функция, проверяющая правильность введенной записи
  53.   var
  54.     s1, count: byte;
  55.     u, z: string;
  56.     x, y: integer;
  57.   begin
  58.     count := 0;
  59.     u := s; // используем временную переменную стрингового типа
  60.     s1 := pos(' ', u); // первый операнд обрабатываем отдельно
  61.     val(copy(u, 1, s1 - 1), x, y); // считаем, что первым слева в строке стоит операнд
  62.     if y = 0 then begin // если это так, то продолжаем проверку
  63.       inc(count);
  64.       delete(u, 1, s1); // удаляем его из строки
  65.       s1 := pos(' ', u);
  66.       while (count >= 1) and (length(u) >= 1) do begin // если баланс записи можно скомпенсировать и строка не пуста
  67.         if s1 = 0 then begin // если пробелов больше нет, то элемент последний
  68.           z := u; // и занимает всю строку целиком, поэтому она копируется полностью
  69.           u := '' // очищаем строку, чтобы выйти из цикла
  70.         end
  71.         else begin // если пробелы есть
  72.           z := copy(u, 1, s1 - 1) // то копируем элемент
  73.         end;
  74.         if length(z) = 1 then begin // если элемент однозначный, то это либо оператор, либо однозначное ЦБЗ
  75.           if (z[1] = '+') or (z[1] = '-') or (z[1] = '*') or (z[1] = '/') then begin // если это оператор
  76.             dec(count) // уменьшаем счетчик по условию
  77.           end
  78.           else begin // в противном случае это ЦБЗ
  79.             inc(count) // и увеличиваем счетчик
  80.           end
  81.         end
  82.         else begin // если длина элемента больше 1, то это в любом случае число
  83.           inc(count) // и увеличиваем счетчик
  84.         end;
  85.         if length(u) > 1 then begin // если элемент не был последним и стринг не очищен
  86.           delete(u, 1, s1) // удаляем содержащую элемент часть стринга вместе с пробелом
  87.         end;
  88.         s1 := pos(' ', u) // ищем следующий пробел
  89.       end
  90.     end;
  91.     balance := (count = 1) // если запись сбалансированная, счетчик равен 1
  92.   end;
  93.  
  94.   procedure ini;
  95.   begin
  96.     top := 0;
  97.   end;
  98.  
  99.   procedure push(x: integer);
  100.   begin
  101.     inc(top);
  102.     A[top] := x
  103.   end;
  104.  
  105.   function pop: integer;
  106.   begin
  107.     pop := A[top];
  108.     dec(top)
  109.   end;
  110.  
  111. begin // тело основной функции
  112.   ini;
  113.   correction; // корректируем запись
  114.   s1 := pos(' ', s);
  115.   if correct then begin // если нет посторонних символов
  116.     if balance then begin // и запись сбалансированная
  117.       while length(s) >= 1 do begin // пока стринг не пуст
  118.         if s1 = 0 then begin // если пробелов больше нет, то элемент последний
  119.           z := s; // и занимает всю строку целиком, поэтому она копируется полностью
  120.           s := '' // очищаем строку, чтобы выйти из цикла
  121.         end
  122.         else begin // если пробелы есть
  123.           z := copy(s, 1, s1 - 1) // то копируем элемент
  124.         end;
  125.         if length(z) = 1 then begin // если длина элемента равна 1, то это либо однозначное ЦБЗ, либо оператор
  126.           case z[1] of // если длина стринга равна 1, то с ним можно работать как с его первым элементом
  127.             '+': begin // перебор вариантов
  128.               push(pop + pop) // так как a + b = b + a
  129.             end;
  130.             '-': begin
  131.               push(-pop + pop) // a - b = -b + a
  132.             end;
  133.             '*': begin
  134.               push(pop * pop) // a * b = b * a
  135.             end;
  136.             '/': begin
  137.               y := pop;
  138.               x := pop;
  139.               push(x div y) // предполагается только целочисленное деление
  140.             end
  141.             else begin // если это не оператор
  142.               val(z, x, y); // то преобразуем его в число
  143.               push(x) // и добавляем в стек
  144.             end
  145.           end
  146.         end
  147.         else begin // если длина элемента больше 1, то это в любом случае число
  148.           val(z, x, y); // и мы преобразуем его
  149.           push(x) // и добавляем в стек
  150.         end;
  151.         if length(s) > 1 then begin // если элемент не был последним и стринг не очищен
  152.           delete(s, 1, s1) // удаляем содержащую элемент часть стринга вместе с пробелом
  153.         end;
  154.         s1 := pos(' ', s) // ищем следующий пробел
  155.       end;
  156.       PolizCalc := pop // результат вычисления есть единственное оставшееся в стеке число
  157.     end
  158.     else begin
  159.       unbalanced := true // иначе меняем соответствующий флаг
  160.     end
  161.   end
  162.   else begin
  163.     incorrect := true // иначе меняем соответствующий флаг
  164.   end
  165. end;
  166.  
  167. begin // тело управляющей программы
  168.   incorrect := false; // инициализация
  169.   unbalanced := false; // внешних параметров
  170.   readln(s);
  171.   x := PolizCalc(s); // вычисляем значение ПОЛИЗ, при этом функция скрыто изменила внешние параметры
  172.   if incorrect then begin // если строка содержит посторонние символы
  173.     writeln('Incorrect expression!') // сообщаем об ошибке
  174.   end
  175.   else begin // если нет
  176.     if unbalanced then begin // но при этом запись несбалансированная
  177.       writeln('The number of operators does not matches to the number of operands!') // сообщаем об ошибке
  178.     end
  179.     else begin
  180.       writeln(x) // если оба условия не выполнены, выводим ответ
  181.     end
  182.   end
  183. end.