VPF::Обратная польская запись - Форум программистов

MaxXx

Дата 6.6.2006, 12:33 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 18
Регистрация: 6.6.2006

Репутация: нет
Всего: нет

Мне нужно составить алгоритм вычисляющий скобочное выражение т.е.
пример: выражение: (1+3)-(2-1)
результат: 3
Для реализации алгоритма я использую обратную польскую запись. Но у меня возникли проблемы (алгоритм "не хочет" приводить выражение к польской записи). Уважаемы программисты помогите отыскать отыскать ошибки в моем коде)

--------------------------------------

Код


const
max=1000;
type
 STACK = record
          top:integer;
          elem:array [1..max] of char;
         end;
 {---------------------------------------}
   procedure MakeNull (var S:STACK);
       begin
         S.top:=max + 1;
       end;
{---------------------------------------}
   function Empty (var S:Stack):boolean;
       begin
        if S.top > max then
           Empty:=true
        else
           Empty:=false;
       end;
{----------------------------------------}
   function Top( s : stack) : char;
  begin
    if Empty(s) then
      exit
    else
      Top := s.elem[s.top];
  end;
{---------------------------------------}
   procedure OutStack (var s:stack; var x: char);
      begin
        if Empty (s) then exit
       else
        begin
         x:= s.elem[s.top];
         s.top:=S.top + 1;
        end;
      end;
{---------------------------------------}
   procedure Instack (var S:Stack;x:char);
      begin
        if S.top = 1 then exit
       else
            begin
             s.top:=s.top-1;
             s.elem[s.top]:=x;
            end ;
       end;
{----------------------------------------}
   function Prior(f : char) : Byte;
begin
    case f of
       '+','-' : prior := 2;
       '*','/' : prior := 3;
       '(' , ')' : prior := 1;
        else
     prior := 0;
    end;
end;
{----------------------------------------}
  procedure opz ( input: string; var output:string);
    var
     i: integer; s,s2:stack;
     t: boolean; elem:char;
      begin
       write ('Inp = ');
       readln (input);
        for i:=1 to length (input) do
          case input[i] of
           '1'..'9': begin
                      output:=output+input[i];
                     end;

    '+','-','*','/': begin
                      t:=empty(s);
                       if t then instack (s,input[i]);
                        if t=false then
                       begin
                        if prior(top(s)) < prior(input[i]) then instack (s,input[i])
                       else
                        if prior(top(s))>= prior(input[i]) then
                          while prior(top(s))>= prior(input[i]) do
                            begin
                             outstack (s,elem);
                             instack  (s2,elem);
                            end;
                            instack (s,input[i]);
                        end;
                      end;
                     end;



  for i:=max downto s.top do
   output:=output+s.elem[i];
  for i:=max downto s2.top do
   output:=output+s.elem[i];
   end;

  var
   outp,inp:string;
    begin
     OPZ (inp,outp);
      writeln ('out = ',outp);
      readln;
     end.

Добавлено @ 12:47
А это алгоритм которым я пользовался:
Входная строка просматривается слева направо, если входной символ является
операндом (число или буква), то он переносится в выходную строку, иначе обрабатывается стеком по нижеприведенному принципу.
■Если стек пуст, то операция просто заносится в стек.
■Если в стеке верхняя операция (элемент стека) имеет более низкий приоритет,
то рассматриваемая операция просто проталкивается в стек.
■Если в стеке верхняя операция имеет более высокий приоритет, то из стека
вытапливаются в выходную строку все элементы, до тех пор пока не встретится
операция с приоритетом ниже чем у рассматриваемой, после чего она
проталкивается в стек.
■Если входной символ "(", то он проталкивается в стек. Если входной символ ")",
то он выталкивает из стека в выходную строку все операции до ближайшей "(".
Сами скобки взаимно уничтожаются и в выходную строку не попадают.

MaxXx

Дата 6.6.2006, 18:47 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 18
Регистрация: 6.6.2006

Репутация: нет
Всего: нет

Вроде сам сделал.....Но эта реализация не подходит для чисел с произвольной разрядностью.
А как можно представлять числа с произвольной разрядностью?

Mailman

Дата 6.6.2006, 20:33 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 19
Регистрация: 6.6.2006

Репутация: нет
Всего: нет

Не стал читать если честно. Попробуй использовать массив из строк [255] для промежуточной польской записи. У меня так работает. А в неё и произвольная разрядность и ар-е знаки пойдут. Чтобы выделить число используй while s[i] in [0..9] do inc(i); Ну и подобное для пропуска многобуквенной переменной.

Заранее прошу прощения если написал не то, что хотели.

Это сообщение отредактировал(а) Mailman - 6.6.2006, 20:34

MaxXx

Дата 6.6.2006, 22:29 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 18
Регистрация: 6.6.2006

Репутация: нет
Всего: нет

Спасибо!!!! Вроде то...Попробую реализовать....
У вас не осталось рабочего примера..Если "да" то киньте мне его пожалуйста на мыло.....

e-moe

Дата 6.6.2006, 22:29 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 88
Регистрация: 3.8.2004
Где: Украина, Донецк

Репутация: нет
Всего: 4

http://labinskiy.com/Calc.zip
когда-то сам писал.. пока только считает, а в планах было символьное дифференцирование.

MaxXx

Дата 7.6.2006, 10:02 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 18
Регистрация: 6.6.2006

Репутация: нет
Всего: нет

Буду разбираться.....Всем спасибо

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Object Pascal: кроссплатформенные технологии \| Следующая тема »