PROGRAM 2


//  FILENAME:  PROGRAM2.CPP     AUTHOR:  ANTHONY F. ORTIZ

#include 
#include 
#include 
#include 
#include 

//  THIS IS THE DECLARATION FOR A CLASS CALLED STACK.
template 
class STACK
{
    private:
        //  THE STACK IS A LINKED LIST WITH NO HEADER.

        struct NODE
        {
            ELEMENT_TYPE ELEMENT;
            NODE * NEXT;
            NODE (ELEMENT_TYPE E = 0, NODE * N = 0):
            ELEMENT (E), NEXT (N) {}
        };

        NODE * STACK_TOP;

        STACK (STACK & VALUE);  //  DISABLED.

    public:
        //  DEFAULT STACK SIZE IS MEANINGLESS.
        STACK (unsigned int MAX_SIZE = 100) : STACK_TOP (0) {};

        //  DESTRUCTOR.
        ~STACK ();

        //  OPERATORS.
        const STACK & operator = (const STACK & VALUE);

        //  MEMBER FUNCTIONS.
        void PUSH (const ELEMENT_TYPE & X);
        void POP ();
        ELEMENT_TYPE POP_AND_TOP ();
        const ELEMENT_TYPE & TOP () const;
        int IS_EMPTY () const {return STACK_TOP == 0;}
};

//  THIS IS THE IMPLEMENTATION FOR A CLASS CALLED STACK.
template 
inline void
STACK  ::
PUSH (const ELEMENT_TYPE & X)
{
    NODE * P = new NODE (X, STACK_TOP);

    if (P == 0)
        cout << "OUT OF MEMORY.";
    else
        STACK_TOP = P;
}

template 
inline const ELEMENT_TYPE &
STACK  ::
TOP () const
{
    if (IS_EMPTY ())
        cout << "EMPTY STACK.";
    return STACK_TOP -> ELEMENT;
}

template 
inline void
STACK  ::
POP ()
{
    NODE * P;
    if (IS_EMPTY ())
        cout << "EMPTY STACK.";
    else
    {
        P = STACK_TOP -> NEXT;
        delete STACK_TOP;
        STACK_TOP = P;
    }
}

template 
inline ELEMENT_TYPE
STACK  ::
POP_AND_TOP ()
{
    ELEMENT_TYPE TOP_ELEMENT = TOP ();
    if (! IS_EMPTY ())
        POP ();
    return TOP_ELEMENT;
}

template 
STACK  ::
~STACK ()
{
    NODE * P = STACK_TOP;
    while (P != 0)
    {
        NODE * AFTER_P = P -> NEXT;
        delete P;
        P = AFTER_P;
    }
}

//  THIS IS THE DECLARATION FOR A CLASS CALLED EVALUATE.
class EVALUATE
{
    public:
        //  CONSTRUCTOR.
        EVALUATE () {};
        //  DESTRUCTOR.
        ~EVALUATE () {};
        //  READS THE INFIX AS A STRING.
        READ_INFIX ();
        //  CONVERTS THE INFIX TO A NUMBER STACK AND A
        //  ARITHMETIC SYMBOL STACK.
        CONVERT_TO_STACKS ();
        //  EVALUATES THE ARITHMETIC EXPRESSION.
        EVALUATE_POSTFIX ();
        //  PRINTS THE POSTFIX EVALUATION.
        PRINT_POSTFIX ();
    private:
        //  THIS IS THE STRING WHICH WILL TEMPORARY HOLD THE
        //  INFIX EXPRESSION UNTIL IT IS CONVERTED TO
        //  A NUMBER AND ARITHMETIC SYMBOL STACK.
        char INFIX [100];
        //  THIS WILL HOLD THE INFIX NUMBERS.
        STACK  INPUT_NUMBERS;
        //  THIS WILL HOLD THE INFIX ARITHMETIC SYMBOLS.
        STACK  INPUT_SYMBOLS;
        //  THIS WILL HOLD THE RESULT OF THE POSTFIX EVALUATION.
        int RESULT;
};

//  THIS IS THE IMPLEMENTATION OF A CLASS CALLED EVALUATE.

//  READS THE INFIX AS A STRING.
EVALUATE :: READ_INFIX ()
{
    //  CLEAR SCREEN AND ENTER THE ARITHMETIC EXPRESSION.
    //  THIS PART IS NOT ERROR CHECKED SO THE USER MUST
    //  ENTER A BLANK BEFORE EACH NUMBER AND SYMBOL.  ALSO
    //  THE USER MUST ENTER A EQUALS SIGN.  OTHERWISE, THE
    //  RESULT IS UNPREDICTABLE.
    clrscr ();
    cout << "ENTER A NUMERIC EXPRESSION.  PLEASE TYPE A SPACE ";
    cout << "AFTER EACH NUMBER OR SYMBOL " << endl;
    cout << "AND END WITH A '='. ";
    cout << endl << endl;
    gets (INFIX);
    cout << endl << endl;
    return 0;
}

//  CONVERT THE INFIX STRING INTO A NUMBER AND ARITHMETIC SYMBOL STACK.
EVALUATE :: CONVERT_TO_STACKS ()
{
    //  THIS VARIABLE HOLDS THE CHARACTER COUNT FOR THE STRING.
    int COUNT = 0;
    //  THIS VARIABLE HOLDS THE COUNT OF THE INDIVIDUAL DIGITS OF EACH
    //  NUMBER IN THE STRING.
    int COUNT2 = 0;
    //  THIS VARIABLE HOLDS THE DIGITS OF A NUMBER SO IT CAN LATER BE
    //  CHANGED TO A NUMBER USING THE ATOI FUNCTION.
    char NUMBER [10];
    //  THIS HOLDS THE NUMBERS AND THE SYMBOLS TEMPORARILY FOR THE
    //  INFIX EXPRESSION.  BECAUSE THE STACKS WILL HAVE THE INFIX IN THE
    //  REVERSE ORDER THAT I WANT THEM IN, I WILL LATER USE POP AND PUSH
    //  STACK FUNCTIONS TO PUT THEM IN THE CLASS'S INPUT STACKS.  THEY
    //  WILL THEN BE IN THE CORRECT ORDER.
    STACK  TEMP_SYMBOLS;
    STACK   TEMP_NUMBERS;
    //  STOP LOOP WHEN INFIX = END OF STRING MARKER.
    while (INFIX [COUNT] != '\0')
    {
        //  IF THE CHARACTER IS A DIGIT, CONVERT IT TO A NUMBER.
        if (int (INFIX [COUNT]) <= 57 && int (INFIX [COUNT]) >= 48)
        {
            //  PUT THE INFIX CHARACTER STRING INTO THE NUMBER
            //  CHARACTER STRING.
            NUMBER [COUNT2] = INFIX [COUNT];
            //  COUNT THE NUMBER OF DIGITS IN THE NUMBER STRING.
            COUNT2 = COUNT2 + 1;
            //  IF THE NEXT CHARACTER EQUALS A SPACE, THEN
            //  CONVERT CHARACTER STRING TO A INTEGER NUMBER AND
            //  PLACE IT ON THE NUMBER STACK.
            if (INFIX [COUNT + 1] == ' ' || INFIX [COUNT + 1] == '\0')
            {
                NUMBER [COUNT2] = '\0';
                TEMP_NUMBERS.PUSH (atol (NUMBER));
                //  INITIALIZE NEXT CHARACTER NUMBER TO 0.
                COUNT2 = 0;
            }
        }
        //  IF INFIX CHARACTER IS A MATH OPERATOR, PUT IT INTO
        //  THE SYMBOL STACK.
        else if (INFIX [COUNT] == '+' || INFIX [COUNT] == '-' || INFIX [COUNT] == '*' || INFIX [COUNT] == '/' || INFIX [COUNT] == '=')
        {
            TEMP_SYMBOLS.PUSH (INFIX [COUNT]);
        }
        //  COUNT THE NEXT CHARACTER IN THE INFIX STRING.
        COUNT = COUNT + 1;
    }
    //  PUT THE SYMBOLS IN THE TEMP STACK VARIABLE INTO INPUT STACK
    //  SYMBOL VARIABLE.  THIS WILL PUT THE SYMBOLS IN THE CORRECT ORDER.
    while (!TEMP_SYMBOLS.IS_EMPTY ())
    {
        INPUT_SYMBOLS.PUSH (TEMP_SYMBOLS.POP_AND_TOP ());
    }
    //  PUT THE NUMBERS IN THE TEMP STACK VARIABLE INTO INPUT STACK
    //  NUMBER VARIABLE.  THIS WILL PUT THE NUMBERS IN THE CORRECT ORDER.
    while (!TEMP_NUMBERS.IS_EMPTY ())
    {
        INPUT_NUMBERS.PUSH (TEMP_NUMBERS.POP_AND_TOP ());
    }
    return 0;
}

//  EVALUATE THE ARITHMETIC EXPRESSION.
EVALUATE :: EVALUATE_POSTFIX ()
{
    //  THIS STACK VARIABLE WILL HOLD THE EVALUATIONS OF THE
    //  NUMBERS, IF THERE IS ANY.
    STACK  OUTPUT_NUMBERS;
    //  THIS STACK VARIABLE WILL HOLD THE SYMBOLS.
    STACK  OUTPUT_SYMBOLS;
    //  POP THE FIRST NUMBER FROM THE INPUT STACK (NUMBERS) AND PUT IT IN
    //  THE OUTPUT STACK VARIABLE (NUMBERS).
    OUTPUT_NUMBERS.PUSH (INPUT_NUMBERS.POP_AND_TOP ());
    //  STOP LOOP WHEN INPUT STACK SYMBOL EQUALS '='.
    while (INPUT_SYMBOLS.TOP () != '=')
    {
        //  POP ANOTHER NUMBER FROM THE INPUT STACK (NUMBERS) AND PUT
        //  IT IN THE OUTPUT STACK VARIABLE (NUMBERS.
        OUTPUT_NUMBERS.PUSH (INPUT_NUMBERS.POP_AND_TOP ());
        //  POP THE SYMBOL FROM THE INPUT STACK (SYMBOLS) AND PUT IT
        //  IN THE OUTPUT STACK VARIABLE (SYMBOLS).
        OUTPUT_SYMBOLS.PUSH (INPUT_SYMBOLS.POP_AND_TOP ());
        //  IF THE TOP OF THE OUPUT SYMBOL STACK = '*' THEN
        //  POP THE NUMBERS FROM THE OUTPUT STACK (NUMBERS)
        //  AND MULTIPLY THEM.  THEN POP THE THE SYMBOL FROM THE
        //  OUTPUT STACK (SYMBOLS).
        if (OUTPUT_SYMBOLS.TOP () == '*')
        {
            long int NUMBER1 = OUTPUT_NUMBERS.POP_AND_TOP ();
            long int NUMBER2 = OUTPUT_NUMBERS.POP_AND_TOP ();
            long int NUMBER3 = NUMBER2 * NUMBER1;
            OUTPUT_NUMBERS.PUSH (NUMBER3);
            OUTPUT_SYMBOLS.POP_AND_TOP ();
        }
        //  IF THE TOP OF THE OUPUT SYMBOL STACK = '/' THEN
        //  POP THE NUMBERS FROM THE OUTPUT STACK (NUMBERS)
        //  AND DIVIDE THEM.  THEN POP THE THE SYMBOL FROM THE
        //  OUTPUT STACK (SYMBOLS).
        else if (OUTPUT_SYMBOLS.TOP () == '/')
        {
            long int NUMBER1 = OUTPUT_NUMBERS.POP_AND_TOP ();
            long int NUMBER2 = OUTPUT_NUMBERS.POP_AND_TOP ();
            long int NUMBER3 = NUMBER2 / NUMBER1;
            OUTPUT_NUMBERS.PUSH (NUMBER3);
            OUTPUT_SYMBOLS.POP_AND_TOP ();
        }
    }
    //  PUT THE LAST SYMBOL FROM THE INPUT STACK (SYMBOLS) INTO
    //  THE OUTPUT STACK (SYMBOLS).
    OUTPUT_SYMBOLS.PUSH (INPUT_SYMBOLS.POP_AND_TOP ());
    //  NOW THE NUMBERS AND SYMBOLS ARE AGAIN IN THE WRONG ORDER SO
    //  REVERSE THE ORDER BY POPING THEM OUT OF THE OUTPUT STACKS
    //  FOR NUMBERS AND SYMBOLS AND PUT THEM BACK IN THE INPUT
    //  STACK FOR NUMBERS AND SYMBOLS.
    while (!OUTPUT_SYMBOLS.IS_EMPTY ())
    {
        INPUT_SYMBOLS.PUSH (OUTPUT_SYMBOLS.POP_AND_TOP ());
    }
    while (!OUTPUT_NUMBERS.IS_EMPTY ())
    {
        INPUT_NUMBERS.PUSH (OUTPUT_NUMBERS.POP_AND_TOP ());
    }
    //  REPEAT THE ABOVE PROCESS FOR ADDITION AND SUBTRACTION.
    //  POP THE FIRST NUMBER FROM THE INPUT STACK (NUMBERS) AND PUT IT IN
    //  THE OUTPUT STACK VARIABLE (NUMBERS).
    OUTPUT_NUMBERS.PUSH (INPUT_NUMBERS.POP_AND_TOP ());
    //  STOP LOOP WHEN INPUT STACK SYMBOL EQUALS '='.
    while (INPUT_SYMBOLS.TOP () != '=')
    {
        //  POP ANOTHER NUMBER FROM THE INPUT STACK (NUMBERS) AND PUT
        //  IT IN THE OUTPUT STACK VARIABLE (NUMBERS.
        OUTPUT_NUMBERS.PUSH (INPUT_NUMBERS.POP_AND_TOP ());
        //  POP THE SYMBOL FROM THE INPUT STACK (SYMBOLS) AND PUT IT
        //  IN THE OUTPUT STACK VARIABLE (SYMBOLS).
        OUTPUT_SYMBOLS.PUSH (INPUT_SYMBOLS.POP_AND_TOP ());
        //  IF THE TOP OF THE OUPUT SYMBOL STACK = '+' THEN
        //  POP THE NUMBERS FROM THE OUTPUT STACK (NUMBERS)
        //  AND ADD THEM.  THEN POP THE THE SYMBOL FROM THE
        //  OUTPUT STACK (SYMBOLS).
        if (OUTPUT_SYMBOLS.TOP () == '+')
        {
            long int NUMBER1 = OUTPUT_NUMBERS.POP_AND_TOP ();
            long int NUMBER2 = OUTPUT_NUMBERS.POP_AND_TOP ();
            long int NUMBER3 = NUMBER2 + NUMBER1;
            OUTPUT_NUMBERS.PUSH (NUMBER3);
            OUTPUT_SYMBOLS.POP_AND_TOP ();
        }
        //  IF THE TOP OF THE OUPUT SYMBOL STACK = '-' THEN
        //  POP THE NUMBERS FROM THE OUTPUT STACK (NUMBERS)
        //  AND SUBTRACT THEM.  THEN POP THE THE SYMBOL FROM THE
        //  OUTPUT STACK (SYMBOLS).
        else if (OUTPUT_SYMBOLS.TOP () == '-')
        {
            long int NUMBER1 = OUTPUT_NUMBERS.POP_AND_TOP ();
            long int NUMBER2 = OUTPUT_NUMBERS.POP_AND_TOP ();
            long int NUMBER3 = NUMBER2 - NUMBER1;
            OUTPUT_NUMBERS.PUSH (NUMBER3);
            OUTPUT_SYMBOLS.POP_AND_TOP ();
        }
    }
    //  POP THE LAST NUMBER FROM THE OUTPUT STACK FOR NUMBERS AND
    //  PUT IT IN THE VARIABLE CALLED RESULT.
    RESULT = OUTPUT_NUMBERS.POP_AND_TOP ();
    return 0;
}

//  PRINT THE POSTFIX RESULT.
EVALUATE :: PRINT_POSTFIX ()
{
    cout << "THE RESULT OF THE POSTFIX IS " << RESULT << endl;
    return 0;
}

//  THIS PROGRAM EVALUATES A POSTFIX EXPRESSION.
int main ()
{
    //  DECALARE THE VARIABLE FOR THE EVALUATE CLASS.
    EVALUATE AEXPRESSION;
    //  READ IT IN AS A STRING FROM THE KEYBOARD.
    AEXPRESSION.READ_INFIX ();
    //  CONVERT IT TO TWO INPUT STACKS, ONE FOR NUMBERS, THE OTHER FOR
    //  SYMBOLS.
    AEXPRESSION.CONVERT_TO_STACKS ();
    //  EVALUATE THEM BY PUTTING THE INPUT STACKS INTO OUTPUT STACKS.
    AEXPRESSION.EVALUATE_POSTFIX ();
    //  PRINT THE RESULT.
    AEXPRESSION.PRINT_POSTFIX ();
    return 0;
}

//  OUTFILE:  PROG2.OUT

ENTER A NUMERIC EXPRESSION.  PLEASE TYPE A SPACE AFTER EACH NUMBER OR SYMBOL
AND END WITH A '='.                                                             
                                                                                
1 + 2 - 3 / 1 * 10 =                                                            
                                                                                
                                                                                
THE RESULT OF THE POSTFIX IS -27 




BACK TO CS3240 PAGE.