--
-- Odwrotna Notacja Polska
-- www.algorytm.org (c) 2006
-- Tomasz Lubiński
--
--

with Text_IO;
use Text_IO;

procedure ONP is

   Stack_pointer: Integer range 0..1000 := 0;
   Stack: array (1 .. 1000) of Character;
   
   procedure concat(dst : in out String; src : in String; ptr : in out Integer) is
   begin
      for i in src'Range loop
        ptr := ptr + 1;
        dst(ptr) := src(i);
      end loop;
   end;
   
   -- returns true if stack is empty, false otherwise
   function stackIsEmpty return boolean is
   begin
      return (Stack_pointer = 0);
   end;
   
   -- gets character from stack
   function stackPop return character is
   begin
      if Stack_pointer > 0 then
         Stack_pointer := Stack_pointer - 1;
         return Stack(Stack_pointer + 1);
      end if;
      return ' ';
   end;
   
   -- pushes character on stack
   procedure stackPush(c: Character) is
   begin
      Stack_pointer := Stack_pointer + 1;
      Stack(Stack_pointer) := c;
   end;   

   -- gets all operators until bracket from stack
   function getFromStackUntilBracket return String is
      result : String(1..1000);
      ptr    : Integer := 0;
      c      : Character;
   begin
      if not stackIsEmpty then
         c := stackPop;
         ptr :=  ptr + 1;
         result(ptr) := ' ';
         while c /= '(' loop
            ptr := ptr + 1;
            result(ptr) := ' ';
            ptr := ptr + 1;
            result(ptr) := c;
            if stackIsEmpty then
               exit;
            end if;
            c := stackPop;
          end loop;
      end if;
      return result(1..ptr);
   end;

   -- gets all operators with priority less or equal to oeprator from stack
   function getFromStack(operator: Character) return String is
      result : String(1..1000);
      ptr    : Integer := 0;
      c      : Character;
   begin
      if not stackIsEmpty then
         c := stackPop;
         while (((operator = '+' or operator = '-') and c /= '(') or
                ((operator = '/' or operator = '*') and (c = '/' or c = '*'))) loop
            ptr := ptr + 1;
            result(ptr) := ' ';
            ptr := ptr + 1;
            result(ptr) := c;
            if stackIsEmpty then
               exit;
            end if;
            c := stackPop;
         end loop;
         stackPush(c);
      end if;
     
      stackPush(operator);
      return result(1..ptr);
   end;

   -- gets all from stack
   function getAllFromStack return String is
      result : String(1..1000);
      ptr    : Integer := 0;
      c      : Character;
   begin   
      while not stackIsEmpty loop
         c := stackPop;
         ptr := ptr + 1;
         result(ptr) := ' ';
         ptr := ptr + 1;
         result(ptr) := c;
      end loop;
      return result(1..ptr);
   end;


   statement: String := "(2+4)*3";
   sign     : boolean := true; --indicates that - is a number sign (not operator minus)
   result   : String (1..1000);
   ptr      : Integer := 0;
   
begin

   -- process all characters
   for i in statement'range loop
      if statement(i) = '(' then
         stackPush('(');
         sign := true;
         concat(result, " ", ptr);                               
      elsif statement(i) = ')' then
         concat(result, " " & getFromStackUntilBracket, ptr);
         sign := false;
      elsif (statement(i) = '+' or
             statement(i) = '-' or
             statement(i) = '*' or
             statement(i) = '/') and (sign = false) then
         concat(result, " " & getFromStack(statement(i)), ptr);             
         sign := true;
      else
         if sign and then
            statement(i) = '-' then
         concat(result, " ", ptr);                               
         end if;
         concat(result, ""&statement(i), ptr);                      
         sign := false;
      end if;
   end loop;
   
   concat(result, getAllFromStack, ptr);                               
   Put_Line(statement & " ONP: " & result(1..ptr));
 
end;