10

Is there a better way to handle unary "-" in converting a infix expression to a postfix one?

The obvious one would be prefix every unary "-" with a 0. Does anyone know better implementation? Thanks!

Guy Coder
  • 24,501
  • 8
  • 71
  • 136
JASON
  • 7,371
  • 9
  • 27
  • 40
  • There are several solutions to this problem, afaik all of them are hackish to some extend. – harold Nov 27 '13 at 15:52
  • Two years after your post, I just had the same question. It's the sort of question which always be relevant. Here's an observation: Adding a zero (which I considered, too) won't always work: Example: --3 would be converted to 0 - 3 -3 = -6 Most parsers would apply the minus as a times minus one product, which would be: - (-3) = 6. Cheers, – MrVelez Jan 07 '16 at 22:19
  • @MrVelez: You are correct that prefixing a zero doesn't work, but for a different reason. Preprocessing '--3' by prefixing zeros should yield '0-0-3' (not '0-3-3', where would the second 3 come from?). Ie ',--3' --> '0-,-3' --> '0-0-,3' --> '0-0-3,' which results in the postfix '0 0 - 3 -'. This evaluates to -3, which probably is not what we want from --3. \ If we could get '0-0-3' to translate to the postfix '0 0 3 - -' then it would evaluate to the desired 3. – A. I. Breveleri Oct 28 '17 at 21:12

2 Answers2

11

The way I did this years ago was invent a new operator for my postfix expression. So when I encountered a unary minus in the infix, I'd convert it to #. So my postfix for a + -b became ab#+.

And, of course, my evaluator had to know that # only popped one operand.

Kind of depends on how you're using the postfix expression once it's built. If you want to display it then your special # operator would probably confuse people. But if you're just using it internally (which I was), then it works great.

Jim Mischel
  • 131,090
  • 20
  • 188
  • 351
  • 1
    I do this too. The only way I can determine that I've "encountered a unary minus in the infix" is to maintain a boolean context that defines whether an operator or an operand is expected next. I'd like to know what others have done to decide when a hyphen is unary or binary. – A. I. Breveleri Nov 27 '13 at 18:07
  • @A.I.Breveleri: If you use a recursive-descent parser for the infix, you can recognize the unary operator without explicitly maintaining the state. See, for example, http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm. – Jim Mischel Nov 27 '13 at 19:25
0

Traverse through the string, and replace all unary minus operators with 0- and surround the result with parenthesis. For example, given -20 + (-2 * 50), transform it to (0-20) + ((0-2) * 50).

pmadhu
  • 3,373
  • 2
  • 11
  • 23
Michael Jordan
  • 1
  • 2
  • This fails on e.g. '--20'. Preprocessing this by prefixing zeros yields '0-0-20'. which results in the postfix '0 0 - 20 -'. This evaluates to -20, which probably is not what we want from '--20'. – A. I. Breveleri Jan 01 '22 at 19:19
  • @A.I.Breveleri if you also parenthesize it, then it will evaluate to `(0-(0-20))` which is correct – Balázs Kovacsics Jun 19 '22 at 23:02