CMPSC 122 HW 4 evaluate.cpp

// Simple Expression Evaluation
// This program will evaluate simple arithmetic expressions
// represented as a linked-list of tokens.  Keyboard input
// will be accepted into a string, which will be converted
// into that linked list.
//
// If the first symbol in the input string is an operator,
// then the value of the previous expression will be taken
// as an implicit first operand.
//
// The expressions may consist of the following:
// -- integer values (which may have multiple digits)
// -- simple arithmetic operators ( +, -, *, /, % )
// -- matched parentheses for grouping

// This implementation consists of a set of mutually-recursive
// functions. which will track the structure of the expression.
//
// A sum expression is the sum or difference of one or more products.
// A product expression is the product or quotient of one or more factors.
// A factor may be a number or a parenthesized sum expression.

#include <iostream>
using namespace std;
#include "tokenlist.h"
#include "vartree.h"

// Conversion to postfix function
void convertToPostfix(TokenList &, TokenList &);
void postFixVar(ListIterator &, TokenList &, TokenList&, TokenList &);
void postFixSum(ListIterator &, TokenList &, TokenList&, TokenList &);
void postFixProduct(ListIterator &, TokenList &, TokenList&, TokenList &);
void postFixFactor(ListIterator &, TokenList &, TokenList&, TokenList &);

int evaluatePostfix(TokenList &, VarTree &);

// Evaluate
// Begins to tokenize the string, and then recursively evaluates it.
int evaluate(const char expr[], VarTree &vars) {
    TokenList list = TokenList(expr);                   // Conversion from character array to TokenList
    int value = 0;                                      // Result of artithmetic expression

    cout << "Expression: " << (list) << endl;

    TokenList listPostfix = TokenList();
    convertToPostfix(list, listPostfix);        // Conversion to postfix

    cout << "Expression in postfix: " << (listPostfix) << endl;

    value = evaluatePostfix(listPostfix, vars);

    return value;
}

// ConvertToPostfix
// Converts the infix TokenList to postfix
void convertToPostfix(TokenList &t, TokenList &listPostFix) {

    ListIterator iter = t.begin();
    TokenList operStack = TokenList();

    postFixVar(iter, t, listPostFix, operStack);
}

// postFixVar
// Handles assignment operators ('=') and variables (e.g. Five, Twenty, etc.)
void postFixVar(ListIterator &iter, TokenList &t, TokenList &listPostFix, TokenList &operStack)
{
    Token equalsToken = Token('='); // Equals token to be added at the end
    Token *varToken;                // Token being tested
    string text;                    // Variable name
    bool equalsCheck = false;       // Check for an equals

    varToken = &iter.token();               // Tests the token
    text = varToken->tokenText();           // Find the token's text

    if (varToken->tokenChar() == '=') {     // If the token is an equals
        equalsCheck = true;                 // The equals will be added after evaluation of the rest of the expression
        iter.advance();                     // Go past the equals
        varToken = &iter.token();           // And save the assumed variable
    }
    else if (text != "+" || text != "-" || text != "*" || text != "/" || text != "%" || text != "(" || text != ")" && !iter.currentIsInteger())     // If the token is a variable and not a number
    {
        if (listPostFix.empty())                                // If the list is empty
            listPostFix.push_back(iter.token());                // Add the variable to the head of the list
        else
            listPostFix.push_front(iter.token());               // Add the variable to the tail of the list
        iter.advance();                                         // And get past it
    }

    if (iter != t.end()) {                                      // If the iterator is not at the end
        postFixSum(iter, t, listPostFix, operStack);                // Continue with the rest of the expression

        if (equalsCheck) {                                          // If there was an equals somewhere in the expression
            if (listPostFix.empty())                                // If the list is empty
                listPostFix.push_back(equalsToken);                 // Add the equals to the head of the list
            else
                listPostFix.push_front(equalsToken);                // Add the equals to the tail of the list
        }
    }
}

// postFixSum
// Evaluates a sum expression: the sum or difference of one or more products
// Also deals with negative integers
void postFixSum(ListIterator &iter, TokenList &t, TokenList &listPostFix, TokenList &operStack)
{
    char oper = 0;          // possible operation
    char operTest = 0;      // Check of precedence
    Token operStackToken;   // Token popped off of stack

    if (iter.tokenChar() == '-')                            // if negative
    {
        iter.advance();                                     // go past the negative sign
        if (listPostFix.empty()) {                          // If the postfix list is empty
            listPostFix.push_back(-iter.integerValue());    // Save the negative integer as the head of the list
        }
        else {
            listPostFix.push_front(-iter.integerValue());   // Otherise append it to the tail
        }
        iter.advance();
        postFixProduct(iter, t, listPostFix, operStack);    // Keep going through the list
    }
    else
        postFixProduct(iter, t, listPostFix, operStack);

    oper = iter.tokenChar();
    while (oper == '+' || oper == '-' && iter != t.end())
    {
        if (operStack.empty()) {                                // If the stack is empty
            operStack.push_back(iter.tokenChar());              // Add the operator to the front
        }
        else {
            ListIterator stackIter = operStack.begin();         // Look at the previous operator
            operTest = stackIter.tokenChar();
            if (operTest == '+' || operTest == '-') {           // If the previous token was of equal precedence (+ or -)
                operStackToken = operStack.pop_front();         // Pop off that operator
                listPostFix.push_front(operStackToken);         // And push it onto the postfix stack
            }
            else if (operTest == '*' || operTest == '/' || operTest == '%') {
                operStackToken = operStack.pop_front();
                listPostFix.push_front(operStackToken);
            }
            operStack.push_back(iter.tokenChar());              // Add the operator to the front
        }

        iter.advance();     // get past the operator
        postFixProduct(iter, t, listPostFix, operStack);

        oper = iter.tokenChar();
    }
    while (!operStack.empty()) {
        operStackToken = operStack.first();
        if (operStackToken.tokenChar() == '(') {
            operStackToken = operStack.pop_front();
        }
        else {
            operStackToken = operStack.pop_front();
            listPostFix.push_front(operStackToken);
        }
    }
}


// postFixProduct
// Processes *, /, and %, making sure that it takes precedence over + and -
void postFixProduct(ListIterator &iter, TokenList &t, TokenList &listPostFix, TokenList &operStack)
{
    char oper = 0;          // possible operation
    char operTest = 0;      // Check of precedence
    Token operStackToken;   // Token popped off of stack

    postFixFactor(iter, t, listPostFix, operStack);
    oper = iter.tokenChar();
    while (oper == '*' || oper == '/' || oper == '%' && iter != t.end())
    {
        if (operStack.empty()) {                                // If the stack is empty
            operStack.push_back(iter.tokenChar());              // Add the operator to the front
        }
        else {
            ListIterator stackIter = operStack.begin();
            operTest = stackIter.tokenChar();
            if (operTest == '+' || operTest == '-') {           // If the top of the stack is of lower precedence
                operStack.push_back(iter.tokenChar());          // Push the higher precedence operator on top
            }
            else if (operTest == '(') {                         // If there is a parenthesis already on the stack
                operStack.push_back(iter.tokenChar());          // Push the value on
            }
            else {                                              // If the top of the stack is also a *,/, or %
                operStackToken = operStack.pop_front();         // Pop off that operator
                listPostFix.push_front(operStackToken);         // And push it onto the postfix stack
            }
        }
        iter.advance(); // get past the operator
        postFixFactor(iter, t, listPostFix, operStack);
        oper = iter.tokenChar();
    }
}

// postFixFactor
// Processes numbers or parenthsized expressions
// Pre-condition: the current place in iter is either a number or a parenthesis
void postFixFactor(ListIterator &iter, TokenList &t, TokenList &listPostFix, TokenList &operStack)
{
    if (iter.currentIsInteger() && iter != t.end())
    {
        if (listPostFix.empty()) {
            listPostFix.push_back(iter.integerValue());
        }
        else {
            listPostFix.push_front(iter.integerValue());
        }
        iter.advance();     // get past the digit
    }
    else
    {
        operStack.push_back(iter.tokenChar());
        iter.advance();     // go past assumed (
        postFixVar(iter, t, listPostFix, operStack);
        iter.advance();     // go past assumed )
    }
}

// EvaluatePostfix
// Evaluates a TokenList converted to postfix notation
// Precondtion: the TokenList is already converted to postfix
int evaluatePostfix(TokenList &t, VarTree &vars) {

    ListIterator iter = t.begin();      // Used to traverse the postfix expression
    TokenList evalStack = TokenList();  // Used in the calculation of the expression
    int tokenType = 0;                  // Used to determine if the token is a variable, an equals, an operator, or a number
    Token evalToken;                    // Temporary save of the token, later on convers to an integer
    string varToken;                    // Temporary save of a variable
    string varToken2;                   // Temporary save of a second variable

    int number1;        // Operand 1
    int number2;        // Operand 2
    int number3;        // Result of number 1 +,-,*,/,% 2, or a number being saved into a variable
    char oper;          // Operator being performed on number1 and number2

    while (iter != t.end()) {
        oper = iter.tokenChar();
        switch (oper) {     // Cannot possibly be a space or any parenthesis, since these were previously taken out
        case '+':
        case '-':
        case '/':
        case '*':
        case '%':
            tokenType = 1;      // A 1 indicates an operator
            break;
        case '=':               // A 3 indicates an assignment operator
            tokenType = 3;
            break;
        default:                // A 2 (number), a 4 (part of a variable name), or a 0 (unknown token type)
            if (iter.currentIsInteger()) {
                tokenType = 2;  // A 2 indicates a number
            }
            else
                tokenType = 4;  // A 4 (part of a variable name)
        }
        switch (tokenType) {
        case 1:         // An operator, assumed to follow two integers
            oper = iter.tokenChar();
            evalToken = evalStack.pop_front();
            if (evalToken.isInteger())                          // If the eval token is a number
                number2 = evalToken.integerValue();             // Save the number of that token
            else                                                // Otherwise if the token is a variable
                number2 = vars.lookup(evalToken.tokenText());   // Lookup the value of that variable (nonexisting variable will be assigned a 0 automatically)
            evalToken = evalStack.pop_front();
            if (evalToken.isInteger())                          // If the eval token is a number
                number1 = evalToken.integerValue();             // Save the number of that token
            else                                                // Otherwise if the token is a variable
                number1 = vars.lookup(evalToken.tokenText());   // Lookup the value of that variable (nonexisting variable will be assigned a 0 automatically)
            switch (oper) {
                case '+':
                    number3 = number1 + number2;
                    break;
                case '-':
                    number3 = number1 - number2;
                    break;
                case '*':
                    number3 = number1 * number2;
                    break;
                case '/':
                    number3 = number1 / number2;
                    break;
                case '%':
                    number3 = number1 % number2;
                    break;
            }
            evalStack.push_back(number3);
            break;
        case 3:     // An equals, assumed to be at the end of the postfix expression (or in a separate area that used to have parenthesis)
            evalToken = evalStack.pop_front();              // Pop off the first token
            if (evalToken.isInteger()) {                    // If the first token is a number
                number3 = evalToken.integerValue();             // Save that number
                evalToken = evalStack.pop_front();              // Pop off the next token
                if (evalToken.isInteger())                      // If it is a number (which it can't be, here for robustness)
                    number3 = evalToken.integerValue();             // Save that number
                else                                            // If it is a variable
                    varToken = evalToken.tokenText();               // Save the name of that variable
                vars.assign(varToken, number3);                 // Assign the number to the variable
            }
            else {                                          // If it is a variable
                varToken = evalToken.tokenText();               // Save the name of that variable
                evalToken = evalStack.pop_front();              // Pop off the next token
                if (evalToken.isInteger()) {                    // If it is a number
                    number3 = evalToken.integerValue();             // Save that number
                    vars.assign(varToken, number3);                 // Assign the number to the variable
                }
                else {                                          // If it is a variable (A variable being assigned to another variable)
                    varToken2 = evalToken.tokenText();              // Save the name of the LH variable
                    number3 = vars.lookup(varToken);                // Find the value of the RH variable
                    vars.assign(varToken2, number3);                // Assign the value of the RH variable to the LH variable
                }
            }
            break;
        case 2:     // A number
            evalStack.push_back(iter.integerValue());   // Push it on the stack
            break;
        case 4:     // A variable
            evalToken = iter.token();                   // Save the token
            varToken = evalToken.tokenText();           // Save the variable
            evalStack.push_back(varToken);              // And push it on the stack
            break;
        }
        iter.advance();
    }
    return number3;
}