|
#include "MathExpression.h"
#include "MatException.h"
#include "MathExpressionDefOps.h"
#include <tchar.h>
#define OPEN_BRACKET '('
#define CLOSE_BRACKET ')'
#define OPEN_BRACKET_PRECEDENCE -1
#define FUNCARG_SEPARATOR ','
MathExpression::MathExpression()
{
m_isExpressionOk = false;
// add default operators and functions
defineOp(new AddOp());
defineOp(new MinusOp());
defineOp(new MultOp());
defineOp(new DivOp());
defineOp(new ExpOp());
defineFunc(new SinFct());
defineFunc(new CosFct());
defineFunc(new TanFct());
defineFunc(new SqrtFct());
defineFunc(new MinFct());
defineFunc(new MaxFct());
defineFunc(new AbsFct());
defineFunc(new RandFct());
defineFunc(new ProbRandFct());
}
MathExpression::~MathExpression()
{
// delete owned operators
int nbOps = m_opList.size();
for( int t=0; t<nbOps; t++ )
{
if( m_opList[t].canDelete )
{
delete m_opList[t].pOp;
m_opList[t].pOp = NULL;
}
}
// delete owned functions
int nbFuncs = m_funcList.size();
for( t=0; t<nbFuncs; t++ )
{
if( m_funcList[t].canDelete )
{
delete m_funcList[t].pFunc;
m_funcList[t].pFunc = NULL;
}
}
clearVariables();
}
void MathExpression::defineOp(class IMathOperator *pOp, bool canDelete)
{
SOperatorInfo opInfo;
opInfo.pOp = pOp;
opInfo.canDelete = canDelete;
m_opList.push_back(opInfo);
}
void MathExpression::defineFunc( class IMathFunction *pFunc, bool canDelete)
{
SFunctionInfo funcInfo;
funcInfo.pFunc = pFunc;
funcInfo.canDelete = canDelete;
m_funcList.push_back(funcInfo);
}
bool MathExpression::setExpression(const wchar_t *expr)
{
m_isExpressionOk = false;
m_expression = expr;
m_isExpressionOk = buildExpr(expr);
return m_isExpressionOk;
}
// clear all defined variables
void MathExpression::clearVariables()
{
int nbVars = m_variableList.size();
// delete all variable evaluator objects
for( int t=0; t<nbVars; t++ )
{
delete m_variableList[t].pVarEvaluator;
m_variableList[t].pVarEvaluator = NULL;
}
m_variableList.clear();
}
bool MathExpression::buildExpr(const wchar_t *expr)
{
std::wstring tmpExpr = expr;
tmpExpr = removeSpace(tmpExpr.c_str());
parseExpression(tmpExpr.c_str());
return true;
}
// remove all space caracters
std::wstring MathExpression::removeSpace(const wchar_t *expr)const
{
int length = lstrlen(expr);
std::wstring res = _T("");
wchar_t car[2] = {0};
for( int t=0; t<length; t++ )
{
if( expr[t] != ' ' )
{
car[0] = expr[t];
res += car;
}
}
return res;
}
void MathExpression::parseExpression(const wchar_t *expr)
{
m_exprStack.clear();
int length = lstrlen(expr);
std::wstring curWord = _T("");
int opID;
wchar_t curChar = 0;
wchar_t car[2] = {0};
// Algorithm
// two stacks: one for operators and functions (opStack)
// and one for the ordered expression items (exprStack). The last item will be
// evaluated last.
// We want to place each expression item (op, function and value) in the correct
// order to be evaluated later, using the operator precedence to do so.
// The opStack is a temp stack used during the parsing step.
std::vector<SOPSTACKITEM> opStack;
bool isFct;
for( int t=0; t<length; t++ )
{
curChar = expr[t];
bool isOp = isAnOp(curChar, &opID);
// separator character?
if( isOp ||
curChar == FUNCARG_SEPARATOR ||
curChar == OPEN_BRACKET||
curChar == CLOSE_BRACKET)
{
// parse the current word
if( curWord.size() > 0 )
{
SExprInfo exprInfo = parseWord(curWord.c_str(), curChar, &isFct);
// if its a value, add it to the exprStack
if( !isFct )
{
m_exprStack.push_back(exprInfo);
}
else
{
// this is a function
SOPSTACKITEM item;
item.precedence = MATHOP_PREC_FCT;
item.pEval = exprInfo.pEval;
opStack.push_back(item);
}
curWord = _T("");
}
if( isOp )
{
if( opStack.size() > 0 )
{
int prevOpPrecedence = opStack[opStack.size()-1].precedence;
int curOpPrecedence;
if( prevOpPrecedence != OPEN_BRACKET_PRECEDENCE )
{
curOpPrecedence = getOp(opID)->getPrecedence();
// destack op until op precedence > previous op.
// the destasked op will be evaluated before.
// if the precedence is equal, the rule is to evaluate
// from left to right, so the previous op has greater precedence also
while( curOpPrecedence <= prevOpPrecedence )
{
SExprInfo exprInfo;
exprInfo.pEval = opStack[opStack.size()-1].pEval;
addAndValidateToExprStack(exprInfo);
// remove the last op
opStack.erase(opStack.begin()+opStack.size()-1);
if( opStack.size() > 0 )
{
prevOpPrecedence = opStack[opStack.size()-1].precedence;
if( prevOpPrecedence == OPEN_BRACKET_PRECEDENCE )
{
break; // open bracket halts the destacking process
}
}
else
{
break; // no more op in the stack
}
}
}
}
SOPSTACKITEM item;
item.precedence = getOp(opID)->getPrecedence();
item.pEval = getOp(opID);
opStack.push_back(item);
}
else if( curChar == FUNCARG_SEPARATOR ||
curChar == CLOSE_BRACKET)
{
// destack until open bracket is found
int curOpPrecedence = opStack[opStack.size()-1].precedence;
while( curOpPrecedence != OPEN_BRACKET_PRECEDENCE )
{
SExprInfo exprInfo;
exprInfo.pEval = opStack[opStack.size()-1].pEval;
addAndValidateToExprStack(exprInfo);
// remove the last op
opStack.erase(opStack.begin()+opStack.size()-1);
if( opStack.size() == 0 )
{
std::wstring msg = _T("Missing open bracket");
EXCEP(msg.c_str(), _T(""))
}
curOpPrecedence = opStack[opStack.size()-1].precedence;
}
// only if we got a close bracket, we erase the open bracket.
if( curChar == CLOSE_BRACKET )
{
// erase the open bracket
opStack.erase(opStack.begin()+opStack.size()-1);
}
}
else if( curChar == OPEN_BRACKET )
{
SOPSTACKITEM item;
item.precedence = OPEN_BRACKET_PRECEDENCE;
opStack.push_back(item);
}
}
else
{
car[0] = curChar;
curWord += car;
}
}
// parse the last word
if( curWord.size() > 0 )
{
m_exprStack.push_back(parseWord(curWord.c_str(), curChar, &isFct));
if( isFct )
{
// an expression cannot end with a function?! there is no argument following
std::wstring msg = _T("Expression cannot end with a function: ");
msg += curWord;
EXCEP(msg.c_str(), _T(""))
}
}
// destack remaining operators, beginning by the end
int nbOps = opStack.size();
for( t=opStack.size()-1; t>=0; t-- )
{
int curOpPrecedence = opStack[t].precedence;
if( curOpPrecedence == OPEN_BRACKET_PRECEDENCE )
{
std::wstring msg = _T("Missing closing bracket");
EXCEP(msg.c_str(), _T(""))
}
SExprInfo exprInfo;
exprInfo.pEval = opStack[t].pEval;
addAndValidateToExprStack(exprInfo);
}
}
// add an operator or a function on the expression stack
// Validation: evaluate the current expressionStack and see if
// some arguments are missing
void MathExpression::addAndValidateToExprStack(const SExprInfo &info )
{
m_exprStack.push_back(info);
try
{
m_isExpressionOk = true; // force the evaluation
evaluate();
m_isExpressionOk = false;
}
catch( MATExceptions )
{
m_isExpressionOk = false;
std::wstring str = _T("Invalid usage, use: ");
str += info.pEval->getHelpString();
EXCEP(str.c_str(), _T(""))
}
}
// check if this character is an operator symbol
bool MathExpression::isAnOp(wchar_t c, int *pOpID)const
{
int nbOps = m_opList.size();
for( int t=0; t<nbOps; t++ )
{
if( c == m_opList[t].pOp->getSymbol() )
{
*pOpID = t;
return true;
}
}
return false; // not an operator
}
// parse a word
// It can be a function, a variable or a value
MathExpression::SExprInfo MathExpression::parseWord(const wchar_t *word, wchar_t nextChar, bool *pIsFct )
{
SExprInfo exprInfo;
*pIsFct = false;
// only functions are followed by an open bracket
if( nextChar == OPEN_BRACKET )
{
// it's a function
int funcID;
if( !isAFunction(word, &funcID) )
{
std::wstring msg = _T("Undefined function: ");
msg += word;
EXCEP(msg.c_str(), _T(""))
}
exprInfo.isEvaluated = false;
exprInfo.pEval = m_funcList[funcID].pFunc;
*pIsFct = true;
}
// if only numerical characters -> value
// so a variable name cannot be composed of numbers only
else if( isOnlyNum(word) )
{
exprInfo.isEvaluated = true;
strToVal(word, &exprInfo.val);
}
else
{
// its a variable
exprInfo.isEvaluated = false;
int varID;
varID = getVarID(word);
if( varID == -1 )
{
std::wstring msg = _T("Undefined variable: ");
msg += word;
EXCEP(msg.c_str(), _T(""))
}
exprInfo.pEval = m_variableList[varID].pVarEvaluator;
}
return exprInfo;
}
// check if this word contains only numerical characters
bool MathExpression::isOnlyNum(const wchar_t *word)const
{
int length = lstrlen(word);
for( int t=0; t<length; t++ )
{
if( iswalpha(word[t]) )
{
return false; // alpha character
}
}
return true;
}
// convert a string value to a double value
void MathExpression::strToVal(const wchar_t *val, double *pVal)const
{
wchar_t **pEnd=NULL;
*pVal = wcstod(val,pEnd);
}
// check if this name corresponds to a defined function
bool MathExpression::isAFunction(const wchar_t *word, int *pFuncID)const
{
int nbFuncs = m_funcList.size();
for( int t=0; t<nbFuncs; t++ )
{
if( wcscmp(word, m_funcList[t].pFunc->getSymbol().c_str())==0 )
{
*pFuncID = t;
return true;
}
}
return false; // not a function
}
bool MathExpression::defineVar(const wchar_t *name, EXPR_VALTYPE *pVal)
{
if( getVarID(name) != -1 )
{
return false; // already defined
}
if( isOnlyNum(name) )
{
return false; // invalid variable name: contains only numbers
}
SVariableInfo varInfo;
varInfo.isValueSet = false;
varInfo.name = name;
VariableEvaluator *pVarEvaluator = new VariableEvaluator();
pVarEvaluator->setVal(pVal);
varInfo.pVarEvaluator = pVarEvaluator;
m_variableList.push_back(varInfo);
return true;
}
int MathExpression::getVarID(const wchar_t *varName)const
{
int nbVars = m_variableList.size();
for( int t=0; t<nbVars; t++ )
{
if( wcscmp(varName, m_variableList[t].name.c_str()) == 0 )
{
return t;
}
}
return -1; // variable not found
}
IMathOperator* MathExpression::getOp(int opID)const
{
return m_opList[opID].pOp;
}
IMathFunction* MathExpression::getFunc(int funcID)const
{
return m_funcList[funcID].pFunc;
}
EXPR_VALTYPE MathExpression::evaluate()
{
if( m_exprStack.size() == 0 || !m_isExpressionOk )
{
return 0; // empty expression or expression not set!
}
m_workExprStack = m_exprStack;
// recursively evaluate each item, beginning by the last (it will
// also be the last to be evaluated)
return evaluate( m_workExprStack.size()-1);
}
EXPR_VALTYPE MathExpression::evaluate(int node)
{
SExprInfo *pExpr = &m_workExprStack[node];
if( pExpr->isEvaluated)
{
return pExpr->val;
}
m_popPtr = node-1;
EXPR_VALTYPE val = pExpr->pEval->evaluate(this);
pExpr->isEvaluated = true;
return val;
}
EXPR_VALTYPE MathExpression::pop()
{
if( m_popPtr < 0 )
{
EXCEP(_T("stack is empty"), _T(""))
}
EXPR_VALTYPE val;
SExprInfo *pExpr = &m_workExprStack[m_popPtr];
if( pExpr->isEvaluated )
{
val = pExpr->val;
m_popPtr--;
}
else
{
val = evaluate(m_popPtr);
}
return val;
}
std::wstring MathExpression::longToS(long val)
{
wchar_t str[20];
return _ltow(val, str, 10);
}
|
By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.
If a file you wish to view isn't highlighted, and is a text file (not binary), please
let us know and we'll add colourisation support for it.