CMPSC 122 Homework 3 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"

// Conversion to postfix function
TokenList convertToPostfix(TokenList);
void convertToPostfixSum(ListIterator &, TokenList, TokenList &, TokenList &);
void convertToPostfixProduct(ListIterator &, TokenList, TokenList &, TokenList &);
void convertToPostfixFactor(ListIterator &, TokenList, TokenList &, TokenList &);

int evaluatePostfix(TokenList);

// Evaluate
// Begins to tokenize the string, and then recursively evaluates it.
int evaluate(const char str[])
{
    TokenList list = TokenList(str);                    // Conversion from character array to TokenList

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

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

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

    return 0;
}

// ConvertToPostfix
// Converts the TokenList to a TokenList in the postfix notation
TokenList convertToPostfix(TokenList t) {
    TokenList newT = TokenList();
    TokenList operStack = TokenList();
    ListIterator iter = t.begin();          // Create iterator for list

    if (iter.currentIsInteger())
        cout << iter.integerValue() << " " << "convertToPostFix" << endl;
    else
        cout << iter.tokenChar() << " " << "convertToPostFix" << endl;

    if (iter.currentIsInteger()){           // Sets the first token in the postfix list
        newT.push_back(iter.integerValue());
        iter.advance();
        if (iter.currentIsInteger())
            cout << iter.integerValue() << " " << "convertToPostFix" << endl;
        else
            cout << iter.tokenChar() << " " << "convertToPostFix" << endl;
    }
    else {                                  // Accounts for the first number being a negative (e.g. -4)
        iter.advance();
        if (iter.currentIsInteger())
            cout << iter.integerValue() << " " << "convertToPostFix" << endl;
        else
            cout << iter.tokenChar() << " " << "convertToPostFix" << endl;;
        newT.push_back(-iter.integerValue());
        iter.advance();
        if (iter.currentIsInteger())
            cout << iter.integerValue() << " " << "convertToPostFix" << endl;
        else
            cout << iter.tokenChar() << " " << "convertToPostFix" << endl;
    }

    convertToPostfixSum(iter, t, newT, operStack);  // Move on to recursion algorithm

    cout << "End of: " << "convertToPostFix" << endl;

    return newT;
}

// ConvertToPostfixSum
// Converts a sum expression: the sum or difference of one or more products
// There may be the possibility of a leading - that would be implicitly
// subtracting the first product from zero.
void convertToPostfixSum(ListIterator &iter, TokenList t, TokenList &newT, TokenList &operStack)
{
    char oper = 0;                                  // possible operation
    if (iter.tokenChar() == '-')                    // if negative
    {
        iter.advance();                             // go past the negative sign
        if (iter.currentIsInteger())
            cout << iter.integerValue() << " " << "convertToPostFixSum" << endl;
        else
            cout << iter.tokenChar() << " " << "convertToPostFixSum" << endl;
        newT.push_front(-iter.integerValue());      // and change the token to a negative integer
    }

    oper = iter.tokenChar();
    while (oper == '+' || oper == '-')
    {
        if (operStack.empty()) {
            operStack.push_back(oper);
        }
        else {
            operStack.push_front(oper);
        }

        iter.advance();     // get past the operator
        if (iter.currentIsInteger())
            cout << iter.integerValue() << " " << "convertToPostFixSum" << endl;
        else
            cout << iter.tokenChar() << " " << "convertToPostFixSum" << endl;
        convertToPostfixProduct(iter, t, newT, operStack);
        oper = iter.tokenChar();
    }
    cout << "End of: " << "convertToPostFixSum" << endl;
}


// ConvertToPostfixProduct
// Converts a product expression: the product or quotient of factors
void convertToPostfixProduct(ListIterator &iter, TokenList t, TokenList &newT, TokenList &operStack)
{
    char oper = 0;      // possible operation

    convertToPostfixFactor(iter, t, newT, operStack);

    oper = iter.tokenChar();
    while (oper == '*' || oper == '/' || oper == '%')
    {
        iter.advance(); // get past the operator
        if (iter.currentIsInteger())
            cout << iter.integerValue() << " " << "convertToPostFixProduct" << endl;
        else
            cout << iter.tokenChar() << " " << "convertToPostFixProduct" << endl;
        if (oper == '*')        // multiplication
            convertToPostfixFactor(iter, t, newT, operStack);
        else if (oper == '/')       // division
            convertToPostfixFactor(iter, t, newT, operStack);
        else                // remainder
            convertToPostfixFactor(iter, t, newT, operStack);
        oper = iter.tokenChar();
    }
    cout << "End of: " << "convertToPostFixProduct" << endl; // It crashes somewhere after this line
}

// ConvertToPostfixFactor
// A factor may either be a single-digit number
// or a parenthsized expression.
void convertToPostfixFactor(ListIterator &iter, TokenList t, TokenList &newT, TokenList &operStack)
{
    if (iter.currentIsInteger())
    {
        newT.push_front(iter.integerValue());
        iter.advance();
    }
    else
    {
        iter.advance();     // go past assumed (
        if (iter.currentIsInteger())
            cout << iter.integerValue() << " " << "convertToPostFixFactor" << endl;
        else
            cout << iter.tokenChar() << " " << "convertToPostFixFactor" << endl;
        convertToPostfixSum(iter, t, newT, operStack);
        iter.advance();     // go past assumed )
        if (iter.currentIsInteger())
            cout << iter.integerValue() << " " << "convertToPostFixFactor" << endl;
        else
            cout << iter.tokenChar() << " " << "convertToPostFixFactor" << endl;
    }
    cout << "End of: " << "convertToPostFixFactor" << endl;
}

int evaluatePostfix(TokenList t) {

    return 0; // Temporary, ya dangus
}