Need some tips to optimize my code...

[BrickInTheWall]

Hi guys,
I've built an expression parser to perform mathematical operations by implementing the shunting-yard-algorithm. But instead of converting to RPN I evaluate immediately. You don't really have to understand how the algorithm works, the problems with my implementation are quite obvious. I want to port the code to a microcontroller to build a simple calculator. Here is the function that implements the algorithm found at http://en.wikipedia.org/wiki/Shunting-yard_algorithm :


double EvaluateExpression(char* inputString)
{
stack<double> operandStack;
stack<Token> operatorStack;
char token;
Token lastToken = Void;
Token currentToken = Void;

for (int i = 0; !(inputString[i] == '\0'); i++)
{
token = inputString[i];

// If token is a number, push it onto the operandStack.
if (IsNumber(token))
{
currentToken = Number;

operandStack.push(ExtractNumber(inputString, &i));
}

if (IsFunction(inputString, i))
{
currentToken = GetFunctionType(inputString, &i);
operatorStack.push(currentToken);
}

// If the token is an operator, check the operatorStack.
if (IsOperator(token))
{
currentToken = GetOperatorType(token, lastToken);

// Is there an operator at the top? IMPORTANT: Parenthesis are excluded here!
// You can't compare two unary or a unary to a binary operator in terms of associativity.
while (!operatorStack.empty() && !(operatorStack.top() == LeftParenthesis) && !IsUnary(currentToken))
{
// There is another operator (o2) on the stack.
if (IsLeftAssociate(currentToken) && Precedence(currentToken) <= Precedence(operatorStack.top()) ||
IsRightAssociate(currentToken) && Precedence(currentToken) < Precedence(operatorStack.top()))
{
// Perform the operation.
// Push result of operation back onto the stack.
operandStack.push(PerformOperation(operatorStack.top(), &operandStack, &operatorStack));
}
else
break;
}

// Push o1 onto the stack.
operatorStack.push(currentToken);
}

// If token is a left parenthesis, push to the stack.
if (IsLeftParenthesis(token))
{
currentToken = LeftParenthesis;
operatorStack.push(currentToken);
}

// If the token is a right parenthesis,
// pop the operatorStack and perform operations until left parenthesis is found.
if (IsRightParenthesis(token))
{
currentToken = RightParenthesis;

while (!(operatorStack.top() == LeftParenthesis))
{
// Push result of operation back onto the stack.
operandStack.push(PerformOperation(operatorStack.top(), &operandStack, &operatorStack));
}

// Now there is a left parenthesis on top of the operatorStack. Simply pop.
operatorStack.pop();

// If the top operator is now a function (which is possible due to parenthesis syntax), then evaluate the result of it.
// Only do the check if the stack isn't empty.
if (!operatorStack.empty())
{
if (IsFunction(operatorStack.top()))
operandStack.push(PerformOperation(operatorStack.top(), &operandStack, &operatorStack));
}
}

if (!operandStack.empty())
cout << operandStack.top() << " // ";

if (!operatorStack.empty())
cout << operatorStack.top();

cout << " (" << i << ")" << endl;

lastToken = currentToken;
}

// There are no more tokens left to read. Perform operations until operatorStack is empty.
while (!operatorStack.empty())
{
if (!operandStack.empty())
cout << operandStack.top() << " // ";

if (!operatorStack.empty())
cout << operatorStack.top();

cout << endl;

// Push result of operation back onto the stack.
operandStack.push(PerformOperation(operatorStack.top(), &operandStack, &operatorStack));
}

return operandStack.top();
}


I see several problems when porting this code to a microcontroller:
-Look at all of those function calls. Would it be a better idea to make the Token-Type (which is an enum at the moment) to a struct and simply set a bunch of bool struct members when initializing them? For example members like: _isUnary, _isLeftAssociate etc. thus making most of those function calls unnecessary and saving processor cycles. Or would it actually be inefficient from a memory point of view to create a bunch of structs and deleting them again when popping them off the stack?

-The stack class. I'm using two instances right now, I'll probably have to write my own.

-Fundamental functions such as sin, cos, e, ln, sqrt etc. I'll probably have to write those myself too, which isn't much of a problem, but I could spend that time doing something else.

-No error handling yet.

I would appreciate any tips on how to optimize this code so that I wont flood my memory and don't use unnecessary processor cycles.

Cheers,
Chris