[Resolved] Evaluating Prefix expressions
Hi does anyone know how to evaluate prefix expressions when the initial infix expression had negative numbers?
for example the infix expression (-3 +4) +5 would be converted to ++-345 in prefix notation.
does anyone know an easy way to evaluate this?
cheers
Deane.
Last edited by deane034; 05-03-2007 at 11:57 PM. Reason: RESOLVED
The bigger question is, how do you know to parse 345 as three numbers, instead of the single number 345? This is inherently ambiguous.Originally Posted by deane034
You either need to separate tokens with whitespace, or invent a new symbol which means "negate" instead of "subtract". A much less preferred option would be to implement some crazy backtracking which would try to apply the minus sign both ways and see which one leads to a correct parse. But in complex expressions this is, again, ambiguous.
You just can't overload a prefix operator to be both binary and unary without having problems like this.
If you're just reading numbers to a stack I don't see the problem, you know you've run into a unary minus when there was no ("free") number before it.
I don't think so. Suppose you've looked at "++-34" so far. There is no way to know without lookahead that there is another number coming. So you have no idea whether to interpret the minus as negation or subtraction.
And the answer isn't "Just look ahead," because what about an expression like ++++++++++++++-3456789.... (etc)? You have to look ahead potentially all the way to infinity.
I wasn't thinking of the converted calculation, but during the conversion process. By that time you shouldn't have any problem determining the operators.
However if OP wanted to store the minus sign as an operator instead of treating it as a part of the number (like how it's mostly done in math) then there would be a problem with having an operator that does different things depending on context.
The solution as I see it would be to simply have the unary minus separated from the binary version.
Say you use dot for unary, and the usual dash for the binary.
An equation like (-6 + 2) - 5 would then become -+.625
When you're reading it in, if you see the negative before you see the number, push a zero. That work?
Quzah.
Hope is the first step on the road to disappointment.
Yeah, figured it out. thanks everyone!
its Quzah's solution. you just push a 0 !
-4 = (0-4) so.. um that way.
Show me how that method applies to evaluation of this expression:its Quzah's solution. you just push a 0 !
+++++++++++++++++++++-1111111111111111111111
When you reach "-11" how do you tell if the minus is a negation or a subtraction?
Quzah, I did not mean "eleven." All the 1 digits in my example were intended to mean 1. My question is how you can determine what role the minus sign is playing without looking all the way to the end of the expression.
EDIT: And I'm talking about evaluation, not converting from infix to prefix -- inserting a phantom zero obviously solves it, but what if you can't do that? The original question was in regard to EVALUATION, not conversion.
EDIT EDIT: Ok, slightly different example because I think I'm not being clear. Expression:
+++-1111
Is the '-' a negation or a subtraction? You can't tell without counting all the digits to the right of it.
Last edited by brewbuck; 05-04-2007 at 03:33 PM.
