Hi guys, I've built an expression parser a week or two ago 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 finished what I had started, but now I want to port the code to a microcontroller to build a simple calculator (to make more use of it than just a boring Windows App). 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 == '\0'); i++)
	{
		token = inputString;

		// 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

Aside from optimizations to the algorithm itself (which I can't speculate on, not being familiar with the algorithm in question), any optimization you want to do is going to depend very, very heavily on three things:

• Target hardware. Microcontrollers come in a truly massive array of shapes, sizes, and capabilities. Naming the actual chipset you want to target would be nice, because chances are there's someone around here who has experience with it (unless of course you're talking about something really obscure). What kind of memory solution are you wanting to set up? Does your microcontroller come with integrated RAM or would you need a secondary chipset for external storage? etc.
  


• Target operating system. If there's a platform underneath your code - i.e. you are not coding against bare metal - then its quirks and behaviours will affect how you write optimal code.
  


• Target compiler. If you're using a microcontroller setup, chances are there's a dedicated compiler for it. In this case, the optimization capabilities are totally up in the air - every compiler will have different strong and weak areas in the arena of automatic optimizations. That will also affect how you do manual (i.e. assembly-level) optimization.

It's certainly possible to do what you want, but we'll need quite a few more details on your plans in order to truly get your code to an optimal condition.

If you are looking for an unsigned integer sqrt source, faster then the standard one, the following is what I use (no divisions done):



I have not written it, I once found it on the internet.
Maybe it's of some help to you ;-)

As to 'e'. It's just a number so you can get a good approximation.
With 'e' you can get sin and cos...not sure how you'd implement the imaginary 'i'...or you can get a Taylor serie to get a fairly good approximation on sin and cos.

Thanks, but I wont have any problems implementing any of the fundamental functions except for maybe hyperbolic functions as I'm not too familiar with them..then again they're not THAT fundamental.

What I am currently using:

ATmega2560: http://shop.myavr.com/index.php?sp=download.sp.php&suchwort=dl89

It's got 8kB of Ram (SRAM), 256kB of Flash and I'm not sure how much EEPROM, but it says somewhere in there. Anyone with experience in programming with AVR here, I would gladly take tips.

I'm just scared that eventually the stack and heap will collide with all of those function calls, local variables and that stack class allocating memory like a mad man (well not really). If I program my own stack class, I think I'll settle for a fixed size as I'm not sure how well the malloc function of the avr-libc fills freed gaps. Right now the stack size would get too big imo, though I think it would be worse if I would implement the Token type as a struct since those function calls aren't really my biggest concern, what do you think? It may be a bit slower, but it's not like I'm using recursion or function with a lot of local variables, so these function calls shouldn't be to heavy on the stack.

External Ram would be great, I'd just slap the heap in there.