FUNCTION Exp_to_Tree (X : VString) RETURN Tree IS
------------------------------------------------------------------------
--| Function to Convert Infix Expression to Expression Tree
--| Author: Michael B. Feldman, The George Washington University
--| Last Modified: January 1996
------------------------------------------------------------------------
  C         : Character;
  T         : VString(MaxLength(X)) := X;
  OpStack   : Stack(Capacity => Length(T));
  NodeStack : Stack(Capacity => Length(T));
  Temp      : Tree := NULL;

  PROCEDURE PopConnectPush IS
  BEGIN
    Temp := Top (OpStack);
    Pop (OpStack);
    Temp.Right := Top (NodeStack);
    Pop (NodeStack);
    Temp.left := Top (NodeStack);
    Pop (NodeStack);
    Push (NodeStack, Temp);
  END PopConnectPush;

BEGIN -- Exp_to_Tree
  IF IsEmpty (T) THEN
    RETURN NULL;
  END IF;
  LOOP
    C := Head (T);

    CASE C IS
      WHEN 'A' .. 'Z' | 'a' .. 'z' | '0' .. '9' =>
        Push (NodeStack, MakeNode (C));

      WHEN '+' | '-' | '*' | '/' =>
        IF IsEmpty (OpStack) THEN
          Push (OpStack, MakeNode (C));
        ELSIF Top (OpStack).Info = '(' THEN
          Push (OpStack, MakeNode (C));
        ELSIF Priority (Top (OpStack).Info) < Priority (C) THEN
          Push (OpStack, MakeNode (C));
        ELSE
          LOOP -- clear stack of higher priority operators
            PopConnectPush;
            EXIT WHEN IsEmpty (OpStack)
              OR ELSE Top (OpStack).Info = '('
              OR ELSE Priority (Top (OpStack).Info) < Priority (C);
          END LOOP;
          Push (OpStack, MakeNode (C));
        END IF;

      WHEN '(' =>
        Push (OpStack, MakeNode (C));

      WHEN ')' =>
        WHILE Top (OpStack).Info /= '(' LOOP
          PopConnectPush;
        END LOOP;
        Pop (OpStack); -- throw away the '('

      WHEN OTHERS =>
        NULL;
    END CASE;

    T := Tail (T);
    EXIT WHEN IsEmpty (T);
  END LOOP;

  WHILE NOT IsEmpty (OpStack) LOOP
    PopConnectPush;
  END LOOP;

  RETURN Top (NodeStack);

END Exp_to_Tree;