Hi Christof,

I understood the principle in general, but somehow since I started writing it from the different angle, it was easier for me to continue to work it out using the original idea.

In fact, the algorithm I currently have (with few extra fixes I added later) works for all kind of the expressions I tried.

I'll see if I would be able to break it again before finally throwing my code and starting to write it from fresh.


>Hi Naomi,
>
>>I'm trying to work out an algorithm for expression parser. A while ago I read something about it in Knut, but I could not find this book at the moment, besides, my expressions are much easier.
>
>You need two stacks, one for values, one for operators. Then you go through the expression token by token. Values are pushed onto the value stack, operators on the operator stack. You start with "(" on the operator stack and an empty value stack.
>
>When you push an operator onto the stack, there are three cases. "(" is always only pushed. ")" evaluates the operator stack and removes the "(". For all other operators you determine the priority. If the operator on the stack has a higher priority than the one on the stack, you evaluate the stack and push the new operator.
>
>Evaluating the stack means, you pop the current operator from the stack. Depending on the operator you pop one or two values from the stack, calculate the result and push it back onto the value stack. This step is repeated until you reach a "(" operator. You always leave this operator on the stack. It's removed when you encounter ")".
>
>As you go through the expression, you determine for every token whether the next one is a value or an operator. Usually those follow each other with a pattern of value operator value operator. "(" is treated as a values, but pushed on the operator stack. ")" is a operator. When you get "(", another value follows. When you expect a value and find "-" you push -1 and * onto the stack, then expect another value. When you hit ")" another operator follows.
>
>When you reach the end of the expression, you push another ")" onto the stack and evaluate the stack. Pop the result from the value stack.