[Back to PARSING SWAG index] [Back to Main SWAG index] [Original]

    {
    I am trying to write an algorithm(in pseudocode or Pascal)  that
    converts a nonparenthesized infix expression to the equivalent postfix
    expression.

    For example, the infix expression

    3 - 6 * 7 + 2 / 4 * 5 - 8

    converts to the postfix expression
    ------ message termination by server was premature----

    but postfix notation would be:  3 6 7 * - 2 4 / + 5 * 8 -

    In the program that follows, the input is a character string which is
    then converted to a linked list. If numeric values are desired, the
    VAL function can be used at the time the list is made.

    The advantage of the linked list approach is the ease with which the
    order of the terms may be rearranged. The disadvantage is the "write
    only" looking code that results--very un-Pascal like. Hopefully, the
    comments make it clearer.

    The conversion of infix to postfix notation follows these rules:

    1. Multiplication and division take precedence over addition and
    subtraction.

    2. Where operations are of equal precedence, they are performed in
    sequential order from left to right.

    The algorithm uses two linked lists. One is a queue, or FIFO, type
    list. Each node of this list is linked to the next and each node
    stores a "word" from the original math string in the same order as
    written. The other op linked list is a short list of one or two nodes
    which stores the math operations in order of their postfix execution.
    In both these lists, the last node points to nil. The math list is
    parsed from the front. Each operation is placed in the op list and
    removed from the longer list. The longer list is relinked and the op
    list is inserted in the proper position for postfix notation.

    <clifpenn@airmail.net>   11:12PM  3/1/96
    --------------------------- }

    Program InFixToPostFix;
    { Written in Turbo Pascal v6.0 by Clif Penn, Mar 1, 1996  }

    Uses CRT;
    Label finis;

    TYPE   link = ^node;   { link is a pointer to a node }
           node = record
                nxt:link;  { points to next node (or nil) }
                dat:string[12];   {length of 12 is arbitrary}
           end;
    VAR
    head, p1, p2, op:link;
    s, postfix:string;

    Procedure MakeWrdList(ss:string);
    VAR
    wrd:string[12];   { 12 is arbitrary }
    s1, s2, len:integer;
    pt1, pt2:link;

    Begin
         pt1 := nil;
         s1 := 1;
         len := Length(ss);

         While s1 < len do
         Begin
              { skip spaces }
              While (ss[s1] = ' ') AND (s1 < len) Do Inc(s1);
              s2 := s1;   {start of word}
              { parse to next space }
              While (ss[s2] <> ' ') AND (s2 <= len) Do Inc(s2);
              wrd := Copy(ss, s1, s2 - s1);   {extract wrd sans spaces}
              s1 := s2;  {advance string index}

              pt2 := pt1;  {initially pt2 to nil, normally move down list}
              new(pt1) ;   {get address for pt1 from heap}
              if pt2 = nil then head := pt1;    {head-->first node}
              pt2^.nxt := pt1;      {links old node to new}
              pt1^.nxt := nil;      {last node in list points to nil}
              pt1^.dat := wrd;      {stores wrd in node}
         End;

    { After above:  pt1 and pt2 no longer used
             head-->[arg1]-->[op1]-->[arg2]-->[ .... ]-->nil       }
    End;

    Procedure ShowList;
    VAR tmp:link;
    Begin
         tmp := head;
         postfix := '';
         While tmp <> nil do
         begin
              postfix := postfix + tmp^.dat + ' ';  {concatanate string}
              tmp := tmp^.nxt;  {traverse the list head to tail}
         end;
         Writeln(postfix);
    End;

    Procedure InsertOp;
    {Inserts Op node(s) into PostFix linked list}
    Begin
         p1^.nxt := op;  {insert op, the last op node points to nil}
         While p1^.nxt <> nil do p1 := p1^.nxt;
         p1^.nxt := p2^.nxt;  {remove p2 node from list}
         p1 := p1^.nxt;  {last node of prev op now linked to list}
         op := p2;       {new op becomes p2}
         op^.nxt := nil;
         p2 := p1;  {both now point to next argument}
    End;

    Procedure ExtendOp;
    {Extracts math symbol node from PostFix list and extends Op list}
    Begin
         p1^.nxt := p2^.nxt;    {remove p2 from list}
         p1 := p1^.nxt;         {relink arg-->arg}
         p2^.nxt := op;         {place p2 in front of old op}
         op := p2;              {now op linked list has 2 nodes}
         p2 := p1 ;             {both now point to next argument}
    End;

    Procedure DoPostFix(st:string);
    Const
    Hi = ['*', '/'];   {Hi, Lo are math precedence rank of symbols}
    Lo = ['-', '+'];

    Begin
         MakeWrdList(st);
         p1 := head;       {After this initialization, }
         op := nil;        {p1, p2, arg1 --> arg2      }
         p2 := p1^.nxt;    {op --> op1 --> nil         }
         ExtendOp;

         While p2^.nxt <> nil Do    {last node points to nil}
         Begin
              p2 := p2^.nxt;  {p2 now pointing to math operation}
              {Conditional char comparisons follow}
              If (op^.dat[1] in Hi) OR (p2^.dat[1] in Lo) then
                    InsertOp
              Else  ExtendOp;
         End;
         p1^.nxt := op;  {links final math operation(s)}
    End;

    BEGIN  {main program}
         ClrScr;
         Writeln('Just press Enter to quit.'); Writeln;
         { Example }
         s := '3 - 6 * 7 + 2 / 4 * 5 - 8';

         DoPostFix(s);
         Writeln('In postfix notation, the infix string:');
         Writeln(s, ' becomes:');
         ShowList;
    Repeat
         Writeln;
         Writeln('Infix math string (spaces between everything):');
         Readln(s);
         If Length(s) < 5 then goto finis;

         DoPostFix(s);
         ShowList;
    Until Length(s) < 5;

    finis:
    END.

[Back to PARSING SWAG index] [Back to Main SWAG index] [Original]