CODEWITHSUNDEEP
c++treeexpressioninfix-notationpostfix-notation
user1325578
user1325578

Reputation: 51

Evaluating expression tree using std::map

I am using abstract data types to evaluate an expression tree as oppposed to a different way previously and i am not sure how to use the map function exactly.

Okay so this function 

int arithmetic_expression::evaluate_Expression(std::map< std::string, int > ipMap)
{
if (tree != NULL){
    return(tree->evaluate(ipMap));
}
else
    return(0);
}

calls this function, and in this function i am not sure what to return

int Tree::evaluate(std::map< std::string, int > ipMap){

//not sure what to put in return to evaluate the expression
if(NodeType==TYPE_OPERATOR)
{
    return())
}

I previously did this a different way like this 

int arithmetic_expression::evaluate_Expression()
{
if (topPtr != NULL)
    return(evaluateTree(topPtr));
else
{
    std::cout<< "Invalid expression: returning 0"<< std::endl;
    return(0);
}
}
}
}


int arithmetic_expression::evaluateTree(TreeNodePtr rootPtr)
{
if ((rootPtr->Op=="+") | (rootPtr->Op=="-")|(rootPtr->Op=="*")|(rootPtr->Op== "/")) 
{
    if (rootPtr->Op=="+")
        {
            return(evaluateTree(rootPtr->leftPtr)+ evaluateTree(rootPtr->rightPtr));
        }
    if (rootPtr->Op=="-")
    {
        return(evaluateTree(rootPtr->leftPtr)- evaluateTree(rootPtr->rightPtr));
    }
    if (rootPtr->Op=="*")
    {
        return(evaluateTree(rootPtr->leftPtr)* evaluateTree(rootPtr->rightPtr));
    }
    if (rootPtr->Op=="/")
    {
        return(evaluateTree(rootPtr->leftPtr)/ evaluateTree(rootPtr->rightPtr));
    }
}
else
{
    int Number;
    std::istringstream(rootPtr->Op) >> Number;
    return(Number);
}

Upvotes: 0

Views: 560

Answers (1)

MSalters
MSalters

Reputation: 179799

You do want a tree for the expression evaluation, and std::map uses a tree internally. That doesn't mean they're a natural match.

In particular, a std::map<std::string, int> can hold only one occurance of each string, and is ordered by those strings. Your expression tree can hold multiple identical subexpressions, and is ordered by the arithmetic rules for expression evaluation.

Upvotes: 1

Related Questions