// BooleanParse.cpp : Parses and compiles Boolean algebra (full RPN stack version)
//

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <conio.h>
#include <ctype.h>
#include <time.h>

#define MAX_RESULT          256

#define TYPE_OPERAND    0
#define TYPE_OPERATOR   1
#define TYPE_NUMBER     2

#define OPERATOR_NOT    0
#define OPERATOR_AND    1
#define OPERATOR_OR     2

int nOperandsRequired[] = {1, 2, 2};
char cOps[] = {'¬', '.', '+'};

//////////////////////////////////////////////////////////////////////
// Stack handler

#define MAX_OPERAND_LENGTH  20
#define MAX_STACK_DEPTH     256

struct CRPNStackEntry
{
    int     nType;
    union
    {
        char    cText[MAX_OPERAND_LENGTH];
        int     nOperator;
        bool    bResult;
    };
};

CRPNStackEntry  stack[MAX_STACK_DEPTH];
int             nStackDepth = 0;

void PushOperator(int nOperator)
{
    stack[nStackDepth].nOperator = nOperator;
    stack[nStackDepth].nType = TYPE_OPERATOR;
    nStackDepth++;
}

void PushOperand(const char *pOperand, int nLength)
{
    strncpy(stack[nStackDepth].cText, pOperand, __min(MAX_OPERAND_LENGTH, nLength));
    stack[nStackDepth].nType = TYPE_OPERAND;
    nStackDepth++;
}

// Evaluates the RPN stack. (pResult <> NULL) specifies that all operands are numbers,
// and the final result should be calculated and placed in pResult.
bool EvalStack(bool *pResult)
{
    int     i, j;
    bool    bResult;
    bool    *workingspace = (bool *)malloc(nStackDepth * sizeof(bool));

#ifdef _DEBUG
    // String variables to allow printing of working
    static  char    szResult[MAX_RESULT];
    static  char    *szStackStrings[256];

    for (i = 0; i < nStackDepth; i++)
        szStackStrings[i] = (char *)malloc(MAX_RESULT * sizeof(char));
#else
    if (pResult == NULL)
        return false;
#endif

    j = 0;
    for (i = 0; i < nStackDepth; i++)
    {
        // Pop off the next thing from the stack and decide what to do with it.
        switch (stack[i].nType)
        {
        case  TYPE_OPERATOR:
            // Its an operator. Make sure we have two operands to work with:
            if (j < nOperandsRequired[stack[i].nOperator])
            {
                printf(" Stack is not well formed!\n");
                return false;
            }
            switch (stack[i].nOperator)
            {
            case OPERATOR_AND:
                bResult = workingspace[j - 2] && workingspace[j - 1];
#ifdef _DEBUG
                sprintf(szResult, "(%s . %s)", szStackStrings[j - 2], szStackStrings[j - 1]);
#endif
                break;
            
            case OPERATOR_OR:
                bResult = workingspace[j - 2] || workingspace[j - 1];
#ifdef _DEBUG
                sprintf(szResult, "(%s + %s)", szStackStrings[j - 2], szStackStrings[j - 1]);
#endif
                break;
            
            case OPERATOR_NOT:
                bResult = !workingspace[j - 1];
#ifdef _DEBUG
                sprintf(szResult, "(¬%s)", szStackStrings[j - 1]);
#endif
                break;

            default:
                printf(" Invalid operator in stack: %d\n", stack[i].nOperator);
                return false;
            }

            j -= (nOperandsRequired[stack[i].nOperator] - 1);
            workingspace[j - 1] = bResult;
#ifdef _DEBUG
            strcpy(szStackStrings[j - 1], szResult);
#endif
            break;

        case TYPE_NUMBER:
            workingspace[j] = stack[i].bResult;
#ifdef _DEBUG
            sprintf(szStackStrings[j], "%d", stack[i].bResult ? 1 : 0);
#endif
            j++;
            break;

        case TYPE_OPERAND:
#ifdef _DEBUG
            if (pResult)
            {
#endif
                printf("Error in stack - operands should have been substituted\n");
                return false;
#ifdef _DEBUG
            }
            sprintf(szStackStrings[j], "%s", stack[i].cText);
            j++;
#endif
            break;
        }
    }
    // Result is last number in working space.
    
    if (j < 1)
    {
        printf("Stack is corrupt!\n");
        return false;
    }

#ifdef _DEBUG
    if (pResult)
        printf("%s = %c\n", szStackStrings[j - 1], workingspace[j - 1] ? '1' : '0');
    else
        printf("%s\n", szStackStrings[j - 1]);

    for (i = 0; i < nStackDepth; i++)
        free(szStackStrings[i]);
#endif

#ifdef _DEBUG
    if (pResult)
#endif
        *pResult = workingspace[j - 1];

    free(workingspace);
    
    return true;
}

// Builds the RPN stack.
bool BuildStack(const char *pExpression, int nStart = 0, int nEnd = -1)
{
    int     i, j, nOperator, nBrackets;
    bool    bUnaryOp = false;

#ifdef _DEBUG
    for (i = 0; i < nStart; i++)
        putchar(' ');
    printf("Evaluating ");
    fwrite(&pExpression[nStart], nEnd - nStart, sizeof(char), stdout);
    printf("\n");
#endif

    // First pass: detect what type of operand we have

    for (i = nStart; isspace(pExpression[i]) && (i < nEnd); i++)
        ;

    if (i == nEnd)
    {
        // blank expression
        printf(" Blank expression\n");
        return false;
    }

    switch (pExpression[i])
    {
    case '(':
        // Copy expression between matching brackets and recurse
        nBrackets = 1;
        for (j = i + 1; (nBrackets > 0) && (j < nEnd); j++)
        {
            switch (pExpression[j])
            {
            case '(':
                nBrackets++;
                break;
            case ')':
                nBrackets--;
                break;
            }
        }
        if (nBrackets > 0)
        {
            printf(" Mismatched brackets\n");
            return false;
        }
        if (!BuildStack(pExpression, i + 1, j - 1))
            return false;

        i = j;
        break;

    // Now handle unary operators
    case '!':   // NOT operator
    case '¬':   // Alternative NOT operator
        bUnaryOp = true;
        // Just break and pretend weve done first operand
        break;

    default:
        if (!isalnum(pExpression[i]))
        {
            printf(" Unexpected character at position %d\n", i);
            return false;
        }
        // Get whole of operand, which must be wholly alphanumeric
        for (j = i; (isalnum(pExpression[j])) && (j < nEnd) && ((j - i) < MAX_OPERAND_LENGTH); j++)
            ;

        if ((j - i) >= MAX_OPERAND_LENGTH)
        {
            printf(" Operand is too long\n");
            return false;
        }

        PushOperand(&pExpression[i], j - i);
        i = j;
        break;
    }

    // Now we have our first operand. We should be positioned just after.
    while (isspace(pExpression[i]) && (i < nEnd))
        i++;

    if (i == nEnd)
        // just one operand
        return true;

    // Get operator.
    switch (pExpression[i])
    {
    case '!':   // NOT operator
    case '¬':   // Alternative NOT operator
        nOperator = OPERATOR_NOT;
        break;

    case '+':   // OR
        nOperator = OPERATOR_OR;
        break;
    
    case '.':   // AND
        nOperator = OPERATOR_AND;
        break;
    
    default:
        printf(" Unrecognised character %c\n", pExpression[i]);
        return false;
    }

    if (!bUnaryOp && (nOperandsRequired[nOperator] == 1))
    {
        printf(" Operator %c is a unary operator\n", cOps[nOperator]);
        return false;
    }

    // Now we get the second operand simply by recursively parsing the last section:
    if (!BuildStack(pExpression, i + 1, nEnd))
        return false;

    // Were done!
    PushOperator(nOperator);
    
    return true;
}

bool Evaluate(const char *pExpression, bool *pResult)
{
    int i;

    if (!BuildStack(pExpression, 0, strlen(pExpression)))
        return false;

#ifdef _DEBUG
    printf("Final stack:\n depth = %d\n", nStackDepth);

    for (i = 0; i < nStackDepth; i++)
    {
        if (stack[i].nType == TYPE_OPERATOR)
            printf(" Operator: %c\n", cOps[stack[i].nOperator]);
        else
            printf(" Operand:  %.20s\n", stack[i].cText);
    }

    if (!EvalStack(NULL))
        return false;
#endif

    // Convert all text operands to numbers
    for (i = 0; i < nStackDepth; i++)
    {
        if (stack[i].nType == TYPE_OPERAND)
        {
            int     c;
            bool    bResult;

            // Check to see if its a number
            if (((stack[i].cText[0] == '0') || (stack[i].cText[0] == '1')) && 
                (stack[i].cText[1] == '\0'))
                bResult = (stack[i].cText[0] == '1');
            else
            {
                printf("Enter %s: ", stack[i].cText);
                do
                {
                    c = getch();
                    if ((c != '0') && (c != '1'))
                        putchar('\a');
                }
                while ((c != '0') && (c != '1'));
                printf("%c\n", c);
                bResult = (c == '1');
                
                for (int j = i + 1; j < nStackDepth; j++)
                {
                    if (stack[j].nType == TYPE_OPERAND)
                    {
                        if (!strcmp(stack[j].cText, stack[i].cText))
                        {
                            stack[j].bResult = bResult;
                            stack[j].nType = TYPE_NUMBER;
                        }
                    }
                }
            }
            stack[i].bResult = bResult;
            stack[i].nType = TYPE_NUMBER;
        }
    }
    
    return EvalStack(pResult);
}

int main(int argc, char *argv[])
{
    printf("Boolean algebra parser (RPN stack version) v1.0\n");
    printf(" Copyright (C) David McCabe, 2000.\n\n");

    if (argc < 2)
    {
        printf("BooleanParse: Usage: BooleanParse \"expression\"\n");
        return 1;
    }

    // Now we have expression, build RPN stack for each permutation, solve and compare

    bool    b;
    
    if (!Evaluate(argv[1], &b))
        return 2;

    printf("%s = %c\n", argv[1], b ? '1' : '0');

    return 0;
}