Evaluating Prefix expressions

This is a discussion on Evaluating Prefix expressions within the C Programming forums, part of the General Programming Boards category; Hi does anyone know how to evaluate prefix expressions when the initial infix expression had negative numbers? for example the ...

  1. #1
    Registered User
    Join Date
    May 2007
    Posts
    2

    Unhappy [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

  2. #2
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,248
    Quote Originally Posted by deane034 View Post
    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.
    The bigger question is, how do you know to parse 345 as three numbers, instead of the single number 345? This is inherently ambiguous.

    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.

  3. #3
    Mad OnionKnight's Avatar
    Join Date
    Jan 2005
    Location
    Umeň, Sweden
    Posts
    555
    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.

  4. #4
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,248
    Quote Originally Posted by OnionKnight View Post
    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.

  5. #5
    Mad OnionKnight's Avatar
    Join Date
    Jan 2005
    Location
    Umeň, Sweden
    Posts
    555
    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

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.

  7. #7
    Registered User
    Join Date
    May 2007
    Posts
    2
    Yeah, figured it out. thanks everyone!

    its Quzah's solution. you just push a 0 !

    -4 = (0-4) so.. um that way.

  8. #8
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,248
    Quote Originally Posted by deane034 View Post
    its Quzah's solution. you just push a 0 !
    Show me how that method applies to evaluation of this expression:

    +++++++++++++++++++++-1111111111111111111111

    When you reach "-11" how do you tell if the minus is a negation or a subtraction?

  9. #9
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,248
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 5
    Last Post: 12-04-2008, 07:15 PM
  2. Evaluating multiple expressions in an If statement.
    By bitslap in forum C Programming
    Replies: 4
    Last Post: 11-01-2008, 04:38 AM
  3. algorithm for this fucntion ?
    By qubit67 in forum C Programming
    Replies: 28
    Last Post: 09-29-2007, 02:24 PM
  4. Regular expressions [Boost]
    By Desolation in forum C++ Programming
    Replies: 8
    Last Post: 12-30-2006, 09:10 PM
  5. Prefix Expressions
    By mannyginda2g in forum C++ Programming
    Replies: 4
    Last Post: 03-19-2004, 12:30 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21