home *** CD-ROM | disk | FTP | other *** search
/ The World of Computer Software / World_Of_Computer_Software-02-387-Vol-3of3.iso / f / find12as.zip / TREE.C < prev    next >
C/C++ Source or Header  |  1992-02-22  |  5KB  |  171 lines
  1. /* Routines to build and evaluate the expression tree.
  2.    Copyright (C) 1987, 1990 Free Software Foundation, Inc.
  3.  
  4.    This program is free software; you can redistribute it and/or modify
  5.    it under the terms of the GNU General Public License as published by
  6.    the Free Software Foundation; either version 1, or (at your option)
  7.    any later version.
  8.  
  9.    This program is distributed in the hope that it will be useful,
  10.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12.    GNU General Public License for more details.
  13.  
  14.    You should have received a copy of the GNU General Public License
  15.    along with this program; if not, write to the Free Software
  16.    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
  17.  
  18. /* MS-DOS port (c) 1990 by Thorsten Ohl, ohl@gnu.ai.mit.edu
  19.    This port is also distributed under the terms of the
  20.    GNU General Public License as published by the
  21.    Free Software Foundation.
  22.  
  23.    Please note that this file is not identical to the
  24.    original GNU release, you should have received this
  25.    code as patch to the official release.
  26.  
  27.    $Header: e:/gnu/find/RCS/tree.c 1.2.0.3 90/09/23 16:09:57 tho Exp $
  28.  */
  29.  
  30. #include <stdio.h>
  31. #include <sys/types.h>
  32. #include "defs.h"
  33.  
  34. #ifdef MSDOS
  35. struct pred_struct *scan_rest (struct pred_struct **input,\
  36.                    struct pred_struct *head, short prev_prec);
  37. #else /* not MSDOS */
  38. struct pred_struct *scan_rest ();
  39. #endif /* not MSDOS */
  40.  
  41.  
  42. /* Return a pointer to a tree that represents the
  43.    expression prior to non-unary operator *INPUT.
  44.    Set *INPUT to point at the next input predicate node.
  45.  
  46.    Only accepts the following:
  47.    
  48.    <victim>
  49.    expression        [operators of higher precedence]
  50.    <uni_op><victim>
  51.    (arbitrary expression)
  52.    <uni_op>(arbitrary expression)
  53.    
  54.    In other words, you can not start out with a bi_op or close_paren.
  55.  
  56.    If the following operator (if any) is of a higher precedence than
  57.    PREV_PREC, the expression just nabbed is part of a following
  58.    expression, which really is the expression that should be handed to
  59.    our caller, so get_expr recurses. */
  60.  
  61. struct pred_struct *
  62. get_expr (input, prev_prec)
  63.      struct pred_struct **input;
  64.      short prev_prec;
  65. {
  66.   struct pred_struct *next;
  67.  
  68.   if (*input == NULL)
  69.     error (1, 0, "invalid expression");
  70.   switch ((*input)->p_type)
  71.     {
  72.     case NO_TYPE:
  73.     case BI_OP:
  74.     case CLOSE_PAREN:
  75.       error (1, 0, "invalid expression");
  76.       break;
  77.  
  78.     case VICTIM_TYPE:
  79.       next = *input;
  80.       *input = (*input)->pred_next;
  81.       break;
  82.  
  83.     case UNI_OP:
  84.       next = *input;
  85.       *input = (*input)->pred_next;
  86.       next->pred_left = get_expr (input, NEGATE_PREC);
  87.       break;
  88.  
  89.     case OPEN_PAREN:
  90.       *input = (*input)->pred_next;
  91.       next = get_expr (input, NO_PREC);
  92.       if ((*input == NULL)
  93.       || ((*input)->p_type != CLOSE_PAREN))
  94.     error (1, 0, "invalid expression");
  95.       *input = (*input)->pred_next;    /* move over close */
  96.       break;
  97.  
  98.     default:
  99.       error (1, 0, "oops -- invalid expression type!");
  100.       break;
  101.     }
  102.  
  103.   /* We now have the first expression and are positioned to check
  104.      out the next operator.  If NULL, all done.  Otherwise, if
  105.      PREV_PREC < the current node precedence, we must continue;
  106.      the expression we just nabbed is more tightly bound to the
  107.      following expression than to the previous one. */
  108.   if (*input == NULL)
  109.     return (next);
  110.   if ((int) (*input)->p_prec > (int) prev_prec)
  111.     {
  112.       next = scan_rest (input, next, prev_prec);
  113.       if (next == NULL)
  114.     error (1, 0, "invalid expression");
  115.     }
  116.   return (next);
  117. }
  118.  
  119. /* Scan across the remainder of a predicate input list starting
  120.    at *INPUT, building the rest of the expression tree to return.
  121.    Stop at the first close parenthesis or the end of the input list.
  122.    Assumes that get_expr has been called to nab the first element
  123.    of the expression tree.
  124.    
  125.    *INPUT points to the current input predicate list element.
  126.    It is updated as we move along the list to point to the
  127.    terminating input element.
  128.    HEAD points to the predicate element that was obtained
  129.    by the call to get_expr.
  130.    PREV_PREC is the precedence of the previous predicate element. */
  131.  
  132. struct pred_struct *
  133. scan_rest (input, head, prev_prec)
  134.      struct pred_struct **input;
  135.      struct pred_struct *head;
  136.      short prev_prec;
  137. {
  138.   struct pred_struct *tree;    /* The new tree we are building. */
  139.  
  140.   if ((*input == NULL) || ((*input)->p_type == CLOSE_PAREN))
  141.     return (NULL);
  142.   tree = head;
  143.   while ((*input != NULL) && ((int) (*input)->p_prec > (int) prev_prec))
  144.     {
  145.       switch ((*input)->p_type)
  146.     {
  147.     case NO_TYPE:
  148.     case VICTIM_TYPE:
  149.     case UNI_OP:
  150.     case OPEN_PAREN:
  151.       error (1, 0, "invalid expression");
  152.       break;
  153.  
  154.     case BI_OP:
  155.       (*input)->pred_left = tree;
  156.       tree = *input;
  157.       *input = (*input)->pred_next;
  158.       tree->pred_right = get_expr (input, tree->p_prec);
  159.       break;
  160.  
  161.     case CLOSE_PAREN:
  162.       return (tree);
  163.  
  164.     default:
  165.       error (1, 0, "oops -- invalid expression type!");
  166.       break;
  167.     }
  168.     }
  169.   return (tree);
  170. }
  171.