/*

------------------------------------------------------------------------------

A license is hereby granted to reproduce this software source code and
to create executable versions from this source code for personal,
non-commercial use.  The copyright notice included with the software
must be maintained in all copies produced.

THIS PROGRAM IS PROVIDED "AS IS". THE AUTHOR PROVIDES NO WARRANTIES
WHATSOEVER, EXPRESSED OR IMPLIED, INCLUDING WARRANTIES OF
MERCHANTABILITY, TITLE, OR FITNESS FOR ANY PARTICULAR PURPOSE.  THE
AUTHOR DOES NOT WARRANT THAT USE OF THIS PROGRAM DOES NOT INFRINGE THE
INTELLECTUAL PROPERTY RIGHTS OF ANY THIRD PARTY IN ANY COUNTRY.

Copyright (c) 1995, 1996, John Conover, All Rights Reserved.

Comments and/or bug reports should be addressed to:

    john@johncon.com (John Conover)

------------------------------------------------------------------------------

postfix.c, infix to postfix translator

ELEMENT *postfix (char *buffer, char *tokens);

    convert the character string of infix notation, contained in
    buffer, to a postfix stack/list of type ELEMENT, returning a
    reference to the postfix stack-the tokens contained in buffer will
    be parsed into the character string, tokens, with each token being
    referenced by an element in the postfix stack; on any stop

    the size of tokens should be twice the size of buffer to allow an
    EOS character between the tokens

Associativity of operators is left to right, and the precedence of
operators is identical to 'C':

    precedence      operator

    high            ! = not
    middle          & = and
    lowest          | = or

The algorithm is as follows:

    there are three stacks, the reverse postfix stack, which contains
    a list of the tokens in reverse posfix order, an intermediate
    stack, that contains the intermediate results of the parsed infix
    tokens, and a forward postfix stack, that contains the list of
    tokens in forward postfix order

    while there are still tokens to be read in buffer, read the next
    token

        if the token is an operand, then push it on the reverse
        postfix stack

        if the token is an '(', then place the token on top of the
        intermediate stack

        if the token is an ')', then pop tokens from the intermediate
        stack, pushing them onto the reverse postfix stack until a ')'
        token is found-discard the '(' and ')'

            note that the stack operators used, which are simple
            macros defined in stack.h, can not be used as arguments in
            control statements making the coding of the constructs in
            this section "clumsy"

        otherwise, repeatedly pop the intermediate stack and push the
        tokens onto the reverse postfix stack until the intermediate
        stack is empty or an operator of lower precedence is
        found-push the token with the lower precedence back onto the
        intermediate stack, and push the new token onto the stack as
        well

        after all tokens have been read, pop all tokens from the
        intermediate stack and push them onto the reverse postfix
        stack

        then, pop tokens from the reverse postfix stack, and push
        them on the forward postfix stack

        if all is well, perform a syntax check by scanning the forward
        postfix stack, counting the identifiers, and discounting the
        operators, making sure that there is always at least one
        identifier on the stack-the identifier count should be exactly
        unity at the conclusion of this operation, if the infix syntax
        was valid

Usage is a call with the infix string in buffer, and tokens at least
twice the size of buffer, for example, in a construct:

    char buffer[SIZE],
         tokens[2 * SIZE];

    ELEMENT *postfix_stack;

    load_buffer (buffer);

    if ((postfix_stack = postfix (buffer, tokens)) != (ELEMENT *) 0)
    {
        process_postfix (postfix_stack);
    }

    else
    {
        handle_postfix_error ();
    }

When finished, buffer is not disturbed, and tokens contains the
contents of buffer, with the tokens separated by exactly one '\0'
character, and no whitespace, ie., if the contents of buffer were:

                  +------------------
    buffer------->|sym1 sym2 sym3 ...
                  +------------------

then the contents of tokens, the postfix stack, and the evaluation
stack, would be:

                  +----------------------
    tokens------->|sym1\0sym2\0sym3\0 ...
                  +----------------------
                   ^     ^     ^
                   |     |     |
                   +-----+-----+-----------------------------+
                         |     |                             |
                         |     |                             |
                         |     +--------------------------+  |
                         |                                ^  |
                         |                                |  |
                         +-----------------------------+  |  |
                                                       |  |  |
                                                       |  |  |
    eval_stack-----------------------------------------+--+--+--+
                                                       |  |  |  |
                                                       |  |  |  |
    posfix_stack->typedef struct symbol_element        |  |  |  |
                  {                                    |  |  |  |
                      char *lexicon;-------------------+  |  |  |
                      enum token_type precedence;         |  |  |
               +------struct symbol_element *next;        |  |  |
               |      struct eval_element *eval;----------+--+--+->typedef struct eval_element
               |      struct bmhpattern_struct *pattern;  |  |  +->{
               |  } ELEMENT;                              |  |         int value;
               |                                          |  |         PTF function;
               +->typedef struct symbol_element           |  |  +------struct eval_element *next;
                  {                                       |  |  |  } EVAL;
                      char *lexicon;----------------------+  |  |
                      enum token_type precedence;            |  |
               +------struct symbol_element *next;           |  |
               |      struct eval_element *eval;-------------+--+->typedef struct eval_element
               |      struct bmhpattern_struct *pattern;     |  +->{
               |  } ELEMENT;                                 |         int value;
               |                                             |         PTF function;
               +->typedef struct symbol_element              |  +------struct eval_element *next;
                  {                                          |  |  } EVAL;
                      char *lexicon;-------------------------+  |
                      enum token_type precedence;               |
               +----- struct symbol_element *next;              |
               |      struct eval_element *eval;----------------+->typedef struct eval_element
               |      struct bmhpattern_struct *pattern;        +->{
               |  } ELEMENT;                                           int value;
               |                                                       PTF function;
               |                                                +------struct eval_element *next;
               |                                                |  } EVAL;
               |                                                |
               .                                                .
               .                                                .
               .                                                .

where the precedence element, in each ELEMENT structure, is set to the
appropriate value of the referenced symbol, and the pattern elements
are null-the order of the postfix_stack elements is in forward postfix
order, eg., the first ELEMENT structure should be evaluated first, the
second next, and so on

For a detailed description of infix to postfix translation, see "C For
Programmers," Walter A. Burkhard, Wadsworth Publishing Company,
Belmont, California, 1988, ISBN 0-534-08856-2, pp 457. See also, "Data
Structures: An Advanced Approach Using C," Jeffrey Esakov, Tom Weiss,
Prentice Hall, Englewood Cliffs, New Jersey, 1989, ISBN 0-13-108847-6,
pp 123. Also, "Data Structures Using C," Aaron M. Tenenbaum, Yedidyah
Langsam, Moshe J. Augenstein, Prentice Hall, Englewood Cliffs, New
Jersey, 1990, ISBN 0-13-199746-7, pp 83.

The argument, buffer, references the tokens to be parsed, and the
argument token, references space where the tokens will be parsed, and
must be at least twice as large as buffer

On any error, return null, else return a reference to the postfix list

ELEMENT, the postfix stack element, is defined in postfix.h

To test this module, compile the module source with -DTEST_POSTFIX

$Revision: 1.1 $
$Date: 1996/09/13 13:47:23 $
$Id: postfix.c,v 1.1 1996/09/13 13:47:23 john Exp $
$Log: postfix.c,v $
Revision 1.1  1996/09/13 13:47:23  john
Added handling of circularly linked directories and subdirectories in searchpath.c
Cosmetic changes to bmhsearch.c, postfix.c, rel.c, searchfile.c, translit.c, uppercase.c, version.c.

 * Revision 1.0  1995/04/22  05:13:18  john
 * Initial revision
 *

*/

#include "rel.h"

#include "rel.h"

#ifndef LINT /* include rcsid only if not running lint */

static char rcsid[] = "$Id: postfix.c,v 1.1 1996/09/13 13:47:23 john Exp $"; /* module version */
static char rcsid_h[] = POSTFIX_H_ID; /* module include version */

#endif

#ifdef __STDC__

ELEMENT *postfix (char *buffer, unsigned char *tokens)

#else

ELEMENT *postfix (buffer, tokens)
    char *buffer;
    unsigned char *tokens;

#endif

{
    unsigned char *token; /* reference to current token in tokens */

    int postfix_error = NO_ERROR, /* module error value, assume no errors from this module */
        grouping_count = 0, /* grouping operator count for syntax, increment for left grouping, decrement for right grouping */
        operand_count = 0; /* operand counter for syntax errors, increment for operand, decrement for operator */

    enum token_type lex_val, /* lexicon type of token */
         precedence; /* lexicon type/precedence of token */

    ELEMENT *intermediate_element, /* reference to token from the intermediate stack */
            *new_element = (ELEMENT *) 0, /* reference to new ELEMENT structure for the new token */
            *intermediate_stack = (ELEMENT *) 0, /* reference to the intermediate stack */
            *forward_postfix_stack = (ELEMENT *) 0, /* reference to the forward postfix stack */
            *reverse_postfix_stack = (ELEMENT *) 0, /* reference to the reverse postfix stack */
            *retval = (ELEMENT *) 0; /* return value, assume error */

    (void) lexicon ((char *) 0, (unsigned char *) 0); /* reset lexicon()'s internal static buffer reference */
    token = tokens; /* reference to the beginning of a token in tokens */

    while ((lex_val = lexicon (buffer, token)) != NONE) /* while there are more tokens in buffer, get the next token */
    {

        if (lex_val != RIGHT) /* is the token a ')'? */
        {

            if ((new_element = (ELEMENT *) memalloc (sizeof (ELEMENT))) == (ELEMENT *) 0) /* no, allocate a new ELEMENT */
            {
                postfix_error = URMEM_ERR; /* module error value */
                break; /* the return value is NULL, break out of the token processing loop, and return the error */
            }

            new_element->lexicon = token; /* reference the token */
            new_element->precedence = lex_val; /* save the token type/precedence */
            new_element->pattern = (BMHPATTERN *) 0; /* null the reference to bmhpattern structure for this element */
            new_element->eval = (EVAL *) 0; /* null the reference to eval structure for storing intermediate results of eval */

            if (lex_val != LEFT) /* is the token a '('? */
            {

                if ((postfix_error = allocate_eval (new_element)) != NO_ERROR) /* no, allocate the ELEMENT's EVAL structure */
                {
                    break; /* couldn't allocate the ELEMENT's EVAL structure, return the error */
                }

            }

        }

        switch (lex_val) /* which kind of token? */
        {

            case NOT: /* operator? */

            case AND:

            case OR:

                if (intermediate_stack != (ELEMENT *) 0)
                {

                    do /* while the intermediate stacks not empty, and the token on the stack's precedence > precedence of token */
                    {
                        if (intermediate_stack == (ELEMENT *) 0)
                        {
                            intermediate_element = (ELEMENT *) 0;
                            break;
                        }

                        intermediate_element = POP (intermediate_stack); /* pop the token off of the intermediate stack */

                        /* intermediate stack not empty, and token on the intermediate stack's precedence > precedence of token? */

                        if (intermediate_element != (ELEMENT *) 0 && (int) intermediate_element->precedence >= (int) lex_val)
                        {
                            PUSH (reverse_postfix_stack, intermediate_element); /* yes, push the token on reverse postfix stack */
                        }

                    }
                    while (intermediate_element != (ELEMENT *) 0 && (int) intermediate_element->precedence >= (int) lex_val);

                    if (intermediate_element != (ELEMENT *) 0) /* intermediate stack have any tokens? */
                    {
                        PUSH (intermediate_stack, intermediate_element); /* yes, push the token from the back */
                    }

                }

                PUSH (intermediate_stack, new_element); /* push the new token on the intermedate stack */
                break;

            case LEFT: /* '(' grouping operator? */

                grouping_count++; /* one more grouping operator */
                PUSH (intermediate_stack, new_element); /* yes, push it on the intermedate stack */
                break;

            case RIGHT: /* ')' grouping operator? */

                grouping_count--; /* one less grouping operator */

                do /* yes, for each token on the intermediate stack */
                {
                    intermediate_element = POP (intermediate_stack); /* pop the token from the intermediate stack */
                    precedence = intermediate_element->precedence; /* save the token's precedence */

                    if (precedence != LEFT) /* token a '('? */
                    {
                        PUSH (reverse_postfix_stack, intermediate_element); /* no, push it on the reverse postfix stack */
                    }

                    /* if malloc(2) is used, the token may be deallocated

                    else
                    {
                        free(intermediate_element);
                    }

                    */

                }
                while (precedence != LEFT);

                break;

            case IDENTIFIER: /* a word? */

            case NONE: /* no token? */

            default:

                PUSH (reverse_postfix_stack, new_element); /* token is an identifier, push it on the reverse postfix stack */
                break;

        }

        while (*token != (unsigned char) '\0') /* skip over the current token: while the character referenced by token is not an EOS: */
        {
            token++; /* skip the character */
        }

        token++; /* reference first character past token's EOS */
    }

    if (postfix_error == NO_ERROR) /* any errors? (if there is, forward_postfix_stack will be returned as null, indicating error) */
    {
        postfix_error = URPAR_ERR; /* assume error in grouping operators */

        if (grouping_count == 0) /* no, too many left or right grouping operators? */
        {

            while (intermediate_stack != (ELEMENT *) 0) /* no, for each token remaining on the intermediate stack */
            {
                intermediate_element = POP (intermediate_stack); /* pop the token off the intermediate stack */
                PUSH (reverse_postfix_stack, intermediate_element); /* push the token on the reverse postfix stack */
            }

            while (reverse_postfix_stack != (ELEMENT *) 0) /* for each token in the reverse postfix stack */
            {
                intermediate_element = POP (reverse_postfix_stack); /* pop the token off the reverse postfix stack */
                PUSH (forward_postfix_stack, intermediate_element); /* push the token on the forward postfix stack */
            }

            postfix_error = NO_ERROR; /* assume no errors */
            retval = forward_postfix_stack; /* return a reference to the forward_postfix stack, assume no errors */
            intermediate_element = forward_postfix_stack; /* reference first element in forward postfix stack */

            while (intermediate_element != (ELEMENT *) 0) /* for each token in the forward postfix stack */
            {

                /*

                note: the forward postfix stack is scanned at this
                point to verify syntax-if a list of the identifiers is
                desired, this is where it should be constructed, for
                example, the list of identifiers could be printed to
                stdio, (since none of the file names have been output
                from main(), yet,) preceeded by a '+' character and
                separated by '|' characters to make an egrep(1)
                compatible search argument, which could, conceivably,
                be used as the search argument in a browser so that
                something like:

                    browse `rel arg directory'

                would automatically search the directory for arg, load
                the files into the browser, and skip to the first
                instance of an identifier, with one button scanning to
                the next instance, and so on-identifiers that have
                been eliminated with a "not" operator do not,
                necessarily, have to be eliminated from the list,
                since no document will be loaded that contains these
                identifiers

                */

                if (intermediate_element->precedence == IDENTIFIER) /* element an identifier? */
                {
                    operand_count++; /* yes, increment the operand count */
                }

                else
                {
                    operand_count--; /* no, decrement the operand count */

                    if (operand_count < 1) /* operand count less than one? */
                    {
                        postfix_error = URSYN_ERR; /* yes, assume error in syntax */
                    }

                }

                intermediate_element = intermediate_element->next; /* next element in forward_postfix_stack */
            }

            if (operand_count != 1) /* operand count not one? */
            {
                postfix_error = URSYN_ERR; /* yes, assume error in syntax */
            }

        }

    }

    if (postfix_error != NO_ERROR) /* pending error? */
    {
        message (postfix_error, (char *) 0); /* yes, print the error */
        retval = (ELEMENT *) 0; /* assume error */
    }

    return (retval); /* return a reference to the forward_postfix stack if no errors, NULL if error */
}

#ifdef TEST_POSTFIX

/*

simple exerciser for testing postfix (); get an infix string from
stdin, parse it into postfix order, and print it to stdout; ignore
the:

declared global, could be static
    postfix             postfix.c(xxx)

from lint

as a simple test, redirecting the following example into stdin:

THESE | THOSE
THESE & THOSE | THEM | THAT
THESE ! THOSE ! THAT
(THESE & THOSE & THEM ) | (THAT | OTHERS & THINGS)

should produce:

"THESE" (5), "THOSE" (5), "|" (1)
"THESE" (5), "THOSE" (5), "&" (2), "THEM" (5), "|" (1), "THAT" (5), "|" (1)
"THESE" (5), "THOSE" (5), "!" (3), "THAT" (5), "!" (3)
"THESE" (5), "THOSE" (5), "&" (2), "THEM" (5), "&" (2), "THAT" (5), "OTHERS" (5), "THINGS" (5), "&" (2), "|" (1), "|" (1)

on stdout

*/

#ifdef __STDC__

int main (void)

#else

int main ()

#endif

{
    char buffer[BUFSIZ]; /* buffer containing infix notation string */

    unsigned char tokens[2 * BUFSIZ]; /* buffer containing tokens from infix notation string */

    int token_count; /* count of tokens */

    ELEMENT *postfix_stack, /* will contain the forward list of tokens in postfix notation */
            *temp_element; /* temporary ELEMENT reference used during the reversal of the order of the lists */

    if (make_uppercase () == (unsigned char *) 0) /* setup the uppercase array */
    {
        (void) fprintf (stderr, "Couldn't setup the uppercase array\n"); /* couldn't setup the uppercase array, print the error */
        exit (1); /* exit with the error */
    }

    while (gets (buffer) != 0) /* while a string of infix notation is available from the stdin */
    {
        token_count = 0; /* reset the count of tokens */

        if ((postfix_stack = postfix (buffer, tokens)) != (ELEMENT *) 0) /* get the postfix notation for the infix string */
        {

            while (postfix_stack != (ELEMENT *) 0) /* for each token on the forward ordered stack */
            {
                temp_element = POP (postfix_stack); /* pop the next token from the forward ordered stack */

                if (token_count == 0) /* first token? */
                {
                    (void) printf ("\"%s\" (%d)", temp_element->lexicon, (int) temp_element->precedence); /* yes, print it */
                }

                else
                {
                    (void) printf (", \"%s\" (%d)", temp_element->lexicon, (int) temp_element->precedence); /* no, print it */
                }

                token_count++; /* one more token */
            }

            (void) printf ("\n"); /* print EOL */
        }

    }

    exit (0); /* exit to OS */

#ifdef LINT /* include only if running lint */

    return (0); /* for LINT formality */

#endif

}

#endif