Calculation Program

[Ken2000]

Hi, I'm working on my calculator program(the code was originaly writen by our instructor and we suppose to modify so it will work with exponent) that basically evaluates a string of expression: for instance 3+4*2^2-8, the result shoud equal to 11 but my program output was -13. This should evaluates '^' then '*' then '+ and -' but mines was kind of wierd. It evaluates 2^2 then -8 then *4 and +3. basically it pushback the tempresult to the vector but it keep going from left to right after the exponent.

here is my implementation of evaluation.cpp

#include "Evaluator.h"

Evaluator :: Evaluator() : result(0.0),expression(""),token()
{
	//token default values are = "" and 0.0;
}

void Evaluator :: evaluate(string expr)
{
	expression = expr;
	parser.init(expression);

	double operand;
	char operator_;

	while(parser.has_tokens())
	{
		token = parser.next_token();

		if (token.kind == TERMINATOR)
		{
			//operator is a string of one character -- need [0] element
			cout << "end of the expression: " << endl;
			process_terminator();
			return;
		}
		else
		if (token.kind == OPERAND)
		{
			operand = atof((token.value).c_str());//convert string to numbers
			operands.push_back(operand);		//store operand in vector
			
		}
		else
		if (token.kind == OPERATOR)
		{
			//send operator to evaluator
			//operator is a string of one character -- need [0] element
			operator_ = (token.value).at(0);		
			process_operator(operator_);
		}

	}//endwhile
}

void Evaluator :: process_operator(char oper)
{
	if ( oper == LP )
	{
		operators.push_back(oper);
	}
	else
	if ( oper == RP )
	{
		//now it's time to pop out all the operands and do the operations up to the RP
		processRP();
	}
	else
	if ( operators.size()==0 )		//if vector empty, push the operator
		operators.push_back(oper);
	else
	if ( precedence(oper) > precedence(operators.back()) )		//if greater than last operator pushed
	{															//it's not time to evaluate this operator
		operators.push_back(oper);
	}
	else
	if ( precedence(oper) <= precedence(operators.back()) )		//evaluate the operators that have higher priority now
	{
		doAnOperation();
		operators.push_back(oper);								//push the current operator into vector
	}
}

int Evaluator :: precedence(char oper)
{
	int prec;
	switch(oper) {
		case '+': case '-':  
			prec = 1;
			break;
		case '*': case '/':	 
			prec = 2;
			break;
		case '^':
			prec=3;
			break;
		case LP:			 
			prec = 0;			//lowest priority when in the stack
			break;
		default: 
			break;
	}
	return prec;
}

void Evaluator :: process_terminator()
{
	//while operand vector is not empty, do an operation on two operands and an operator; 
	//Put final result back in operand vector.
	

	while (!operators.empty())		//empty vectors until result remains in operators vector
	{
		doAnOperation();
	}
	result = operands.back();		//result should be only thing left in the vector
}

void Evaluator :: processRP()
{
	//process all operands until LP operator isfound
		do
		{
			doAnOperation();
		}while (operators.back() != LP);
		operators.pop_back();					//remove the LP
}


void Evaluator :: doAnOperation()
{
	//pop two operands and an operator; perform operation and put result in
	//operand vector
	double first_op, second_op;
	char oper;
	double tempResult;

	first_op = operands.back();	         //get operand from the vector
	operands.pop_back();				 
	second_op = operands.back();		//get operand from the vector
	operands.pop_back();					 
	oper = operators.back();		   //get an operator from the vector
	operators.pop_back();
	
	try{
		tempResult = performOperation(second_op,first_op,oper); //get the result of binary operation using terms taken from vector
		operands.push_back(tempResult);	//put result back into the vector
	
	}
	
	catch(int)
	{
		//throw exception back to main so program can terminate
		throw;
	}
	
}

double Evaluator :: performOperation(double op1,double op2,char oper) 
{
	double result;
	try
	{
		switch(oper){
			case PLUS:
				result = op1+op2; break;
			case MINUS:
				result = op1-op2; break;
			case MULT:
				result = op1*op2; break;
			case DIV:
				if (op2 == 0) throw 0;
				result = op1/op2; break;
			case POW:
				result = pow(op1, op2); break;

			default: break;
		}
		return result;
	}
	catch(int)
	{
		//throw back to caller (doAnOperation())
		throw;
	}
}


double Evaluator :: getResult()
{
	//result is only number left in the operand vector
	return result;
}

[LB]

You should split the string by the lowest precedence operator found in the string first, then the next, etc. until you have a tree:

3+4*2^2-8

Expression
   / \
  +   -
 / \ / \
3   *   8
   / \
  ^   4
 / \
2   2

I think recursive polymorphism would help here:

class Operator
{
    Operator *left;
    Operator *right;
public:
    enum Type {Exponent, Multiply, Add, Subtract, None};
private:
    Type type;
protected:
    Operator() : type(None), left(0), right(0) {}
public:
    Operator(Type typ) : left(0), right(0), type(typ) {}
    void Left(Operator *lft){ left = lft; }
    void Right(Operator *rght){ right = rght; }
    virtual int Evaluate()
    {
        if(!left || !right) return 0;
        if(type == Exponent) return std::pow(left->Evaluate(), right->Evaluate());
        if(type == Multiply) return left->Evaluate() * right->Evaluate();
        if(type == Add) return left->Evaluate() + right->Evaluate();
        if(type == Subtract) return left->Evaluate() - right->Evaluate();
    };
    virtual ~Operator()
    {
        delete left;
        delete right;
    }
};
class Constant : private Operator
{
    int c;
public:
    Constant(int val) : c(val) {}
    virtual int Evaluate()
    {
        return c;
    }
    virtual ~Constant(){}
};

EDIT: here is some sample usage with 3+4*2^2-8:

Operator *TwoPowTwo = new Operator(Operator::Exponent);
TwoPowTwo->Left(new Constant(2));
TwoPowTwo->Right(new Constant(2));

Operator *FourTimesExpression = new Operator(Operator::Multiply);
FourTimesExpression->Left(new Constant(4));
FourTimesExpression->Right(TwoPowTwo);

Operator *ThreePlusExpression = new Operator(Operator::Add);
ThreePlusExpression->Left(new Constant(3));
ThreePlusExpression->Right(FourTimesExpression);

Operator *ExpressionMinusEight = new Operator(Operator::Subtract);
ExpressionMinusEight->Left(ThreePlusExpression);
ExpressionMinusEight->Right(new Constant(8));

int Result = ExpressionMinusEight->Evaluate();
delete ExpressionMinusEight; //recursively deletes all the other stuff we created with new above,
                             //see Operator::~Operator()