Помощь - Поиск - Пользователи - Календарь
Полная версия: Скобочное выражение
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Maximka
Дано скобочное выражение и нужно написать алгорит для вывода его результата.
Например: входная строка: (1+2)-(1+2)
выходная строка: 0

Для реализации данного алгоритма я использовал польскую запись.
Вот алгоритм которым я пользовался:

______________

Рассматриваем поочередно каждый символ:
1. Если этот символ - число (или переменная), то просто помещаем его в выходную строку.
2. Если символ - знак операции (+, -, *, / ), то проверяем приоритет данной операции. Операции умножения и деления имеют наивысший приоритет (допустим он равен 3). Операции сложения и вычитания имеют меньший приоритет (равен 2). Наименьший приоритет (равен 1) имеет открывающая скобка.
Получив один из этих символов, мы должны проверить стек:

а) Если стек все еще пуст, или находящиеся в нем символы (а находится в нем могут только знаки операций и открывающая скобка) имеют меньший приоритет, чем приоритет текущего символа, то помещаем текущий символ в стек.
б) Если символ, находящийся на вершине стека имеет приоритет, больший или равный приоритету текущего символа, то извлекаем символы из стека в выходную строку до тех пор, пока выполняется это условие; затем переходим к пункту а).

3. Если текущий символ - открывающая скобка, то помещаем ее в стек.
4. Если текущий символ - закрывающая скобка, то извлекаем символы из стека в выходную строку до тех пор, пока не встретим в стеке открывающую скобку (т.е. символ с приоритетом, равным 1), которую следует просто уничтожить. Закрывающая скобка также уничтожается.

Если вся входная строка разобрана, а в стеке еще остаются знаки операций, извлекаем их из стека в выходную строку.

Рассмотрим алгоритм на примере простейшего выражения:
Дано выражение:
a + ( b - c ) * d
Результат:
a b c - d * +
------------------------------------------------------

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


Код


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; symv:char; var output:string);
      begin
        if Empty (s) then exit
       else
        begin
         symv:= s.elem[s.top];
         s.top:=S.top + 1;
         output:=output+symv;
        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 (s:stack; var output:string);
    var
     i: integer; input:string;
     t: boolean;
     elem:char;
      begin
       Makenull(s);
       write ('Inp = ');
       readln (input);
        for i:=1 to length (input) do
          case input[i] of
           '0'..'9': output:=output+input[i];
    '+','-','*','/': begin
                       t:=Empty(s);
                       if (t=true) or (prior(input[i]) > prior(top(s))) then instack(s,input[i]);
                        if prior(top(s))>=prior(input[i]) then
                        while (prior(top(s))>=prior(input[i])) do
                           begin
                            outstack(s,elem,output);
                           end;
                            instack (s,input[i]);
                         end;
                     end;
         for i:=max downto s.top do
          output:=output+s.elem[i];
            writeln ('out = ',output);
                   end;





  var
   outp,inp:string;
    s1:stack;
    begin
     OPZ (s1,outp);
     writeln ('---------------------------');
      readln;
     end.














volvo
Велосипедостроением не занимаемся... Перевод выражения в польскую запись есть здесь:
FAQ: Постфиксная форма записи, Перевод выражения в постфикс
Maximka
А как представлять числа с произвольной разрядностью??????
Для этих целей польская запись пойдет?
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.