Recent

Author Topic: Unary prefix operators and the infix to postfix algorithm  (Read 2487 times)

grawlix

  • New member
  • *
  • Posts: 7
Unary prefix operators and the infix to postfix algorithm
« on: October 06, 2021, 12:41:35 pm »
Hello all,

I've been working on an algebraic symbol manipulator that handles numerics and binary operators like +-*/ and ^.  It uses the the well-worn algorithm:

while more infix terms do
begin
  infix = next term

  if infix is operand then
    send infix to output

  else begin // infix is operator
    while operator stack not empty do
    begin
      top = top operator on operator stack

      if top.precedence > infix.precedence then
        pop top to output
      else if (top.precedence = infix.precedence) and top.associative then
        pop top to output
      else
        break while loop
    end

    push operator to stack
  end   
end

while operator stack is not empty do
  pop operator to output


I hope I've sufficiently described that algorithm.  It seems to work well enough, but I cannot find any direct discussion of how prefixing unary operators should be handled.  Is this algorithm sufficient?  I'm unsure.

The most obvious unary prefix operator would be arithmetic negation, 2 * -3, for instance.  In my case, that has been permuted to binary multiplication with -1 as the other operand.  That solves it, I guess, so as another example, the logical not operator, seen in object pascal.  It has a very high operator precedence, and there's no binary ^ operator, so I cannot see how they interact to test the algorithm.

This is getting long-winded now, so I'll close with the request for any adjacent commentary on this as I've overworked it in my mind and need a clean take.
« Last Edit: October 09, 2021, 04:56:46 pm by grawlix »

MarkMLl

  • Hero Member
  • *****
  • Posts: 6676
Re: Unary prefix operators and the infix to postfix algorithm
« Reply #1 on: October 06, 2021, 01:17:05 pm »
So what are you basing this on: a variant of the Shunting Yard algorithm? I normally simply use recursive descent for this sort of thing, where negation etc. is handled at the factor level.

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11383
  • FPC developer.
Re: Unary prefix operators and the infix to postfix algorithm
« Reply #2 on: October 06, 2021, 01:32:18 pm »
  if infix is operand then
    send infix to output

When I solved this in 2002-3, I considered the following for unary minus (-x=minus(x))
There are two cases for unary minus or plus, one is such a sign as the very first token of a string, or the token before the current one is a binary operator or an opening parenthesis.   If one of two cases are true, I change the operation to unary minus. The unary minus has a higher priority in the precedence than the binary minus.

(see fpcsrc/packages/symbolic/src/parsexpr.inc around line 333:
Code: Pascal  [Select][+][-]
  1.  If (OperationNr=psub) then  {Minus(x) or x-y?}
  2.        begin
  3.         IsMinus:=False;
  4.         if I=1 then  // first token of string
  5.          IsMinus:=true
  6.         else
  7.          If Expr[I-1] IN ['+','(','*','/','-','^'] then  // previous token binary operator or opening parenthesis
  8.           IsMinus:=true;
  9.         If IsMinus then
  10.          OperationNr:=PMinus;   // change token to unary minus rather than binary minus.
  11.        end;
  12.  

I based myself originally on a simple example from Thrai Tran from SWAG, which might be simpler to review than unit symbolic, but iirc it is quite basic, and might not implement this.

grawlix

  • New member
  • *
  • Posts: 7
Re: Unary prefix operators and the infix to postfix algorithm
« Reply #3 on: October 06, 2021, 04:28:49 pm »
So what are you basing this on: a variant of the Shunting Yard algorithm? I normally simply use recursive descent for this sort of thing, where negation etc. is handled at the factor level.

MarkMLl

Yes.  I did not know that name until you've mentioned it, but the algorithm above is an expansion of that original logic to take operator precedence and associativity into account.  Your posting led me to a wikipedia article that reinforces my suspicion--that the algorithm cannot handle arbitrary unary prefix operators.  Thank you for that.

Does recursive descent mean you evaluate the operators as you encounter them?  I can't really do that in my scenario.

grawlix

  • New member
  • *
  • Posts: 7
Re: Unary prefix operators and the infix to postfix algorithm
« Reply #4 on: October 06, 2021, 04:44:12 pm »
Good information.  Thanks for your response.

My hope is that I can figure out the simplest logic that produces a proper (given the rules) postfix steam to be evaulated later.  With unary prefix arithmetic negation, it does appear to go one of two ways:

-1^2

Method 1: Convert unary to binary operator

Infix: -1 * 1^2
Postfix: -1, 1, 2, ^, *
Evaluation: -1

Method 2: Keep it unary, but with the highest precedence

Infix: -1 ^ 2
Postfix: 1, -, 2, ^
Evaluation: +1

I'm looking for a Method 3, I guess, which would allow for unary prefix operators of any precedence to be properly placed into the postfix queue.

marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11383
  • FPC developer.
Re: Unary prefix operators and the infix to postfix algorithm
« Reply #5 on: October 06, 2021, 04:56:39 pm »
I'm looking for a Method 3, I guess, which would allow for unary prefix operators of any precedence to be properly placed into the postfix queue.

So what if you use the unary method but with a lower precedence than ^ ?

MarkMLl

  • Hero Member
  • *****
  • Posts: 6676
Re: Unary prefix operators and the infix to postfix algorithm
« Reply #6 on: October 06, 2021, 05:05:15 pm »
Does recursive descent mean you evaluate the operators as you encounter them?  I can't really do that in my scenario.

Broadly speaking: yes. I think you'll find https://en.wikipedia.org/wiki/META_II useful as a discussion of one of the earliest tools... and my own experience is that the earliest implementations are the easiest to understand.

If you look at the rule that defines an expr with a couple of extra pairs of parentheses:

Code: [Select]
expr = term $( ('+' term .OUT('ADD'))
             / ('-' term .OUT('SUB'))
             );

i.e. it's a term, followed by zero-or-more ocurrences of either + term or - term, which is interpreted as a term being pushed onto the stack, a second term being pushed onto the stack, and then an operation applied leaving a single result on the stack.

But you can trivially expand that to

Code: [Select]
expr = ('-' term .OUT ('NEG')) |
             ( term $( ('+' term .OUT('ADD'))
             / ('-' term .OUT('SUB'))
             ) );

So at the point where you're expecting a term, which might in practice be a literal number, if you find - then you negate the term... and you'll find things just work with the right priority :-)

I'd throw in at this point that one of the weirder languages of the last 60 years actually had two negation operators: - applied to the entire item that followed it (which was often a list, which wasn't delimited by any form of bracket) while ¯ applied only to the first element.

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

grawlix

  • New member
  • *
  • Posts: 7
Re: Unary prefix operators and the infix to postfix algorithm
« Reply #7 on: October 06, 2021, 05:22:54 pm »
Thanks, Mark, I'll check out multiple topics you've mentioned.  At this point, I suspect the choice to be made is between "highest priority unary" and "convert to binary," and it's a matter of taste.

Just as a small survey, can I ask what you expect would expect evaluating this expression: -1^2


VTwin

  • Hero Member
  • *****
  • Posts: 1215
  • Former Turbo Pascal 3 user
Re: Unary prefix operators and the infix to postfix algorithm
« Reply #8 on: October 06, 2021, 05:52:52 pm »
MATLAB and R both evaluate

-1^2

as

-1

I believe in Fortran and Python -1**2 gives -1 as well.

I'd go with that, although spreadsheets may differ...
« Last Edit: October 06, 2021, 06:14:22 pm by VTwin »
“Talk is cheap. Show me the code.” -Linus Torvalds

Free Pascal Compiler 3.2.2
macOS 12.1: Lazarus 2.2.6 (64 bit Cocoa M1)
Ubuntu 18.04.3: Lazarus 2.2.6 (64 bit on VBox)
Windows 7 Pro SP1: Lazarus 2.2.6 (64 bit on VBox)

MarkMLl

  • Hero Member
  • *****
  • Posts: 6676
Re: Unary prefix operators and the infix to postfix algorithm
« Reply #9 on: October 06, 2021, 06:02:27 pm »
Make sure that you read the paper at the bottom of the Meta-II article, it's widely regarded to be a classic.

Just as a small survey, can I ask what you expect would expect evaluating this expression: -1^2

The best I can do there is direct you to the discussion at https://en.wikipedia.org/wiki/Order_of_operations#Unary_minus_sign , and to say that recursive descent can accommodate either case by organising the rules appropriately. I would say that I'm very dubious about the example in the Wp Meta-II article, and would again urge you to read the paper.

Another classic example is 18 / 6 / 3, which should return 1 but can be easily got wrong.

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11383
  • FPC developer.
Re: Unary prefix operators and the infix to postfix algorithm
« Reply #10 on: October 06, 2021, 06:13:48 pm »
FPC(the compiler) also gives -1, while symbolic gives "1".

The division test seems to be ok though.
Code: Pascal  [Select][+][-]
  1. uses symbolic,math;
  2.  
  3. begin
  4.   writeln(-1**2);
  5.   writeln(quickevaluate('3+-1^2',[],[]));
  6.   writeln(quickevaluate('18/6/3',[],[]));
  7.  
  8. end.

VTwin

  • Hero Member
  • *****
  • Posts: 1215
  • Former Turbo Pascal 3 user
Re: Unary prefix operators and the infix to postfix algorithm
« Reply #11 on: October 06, 2021, 06:40:12 pm »
2^2^3

is another tricky one. 64 or 256?

It depends on the choice of associative behavior, left or right:

https://codeplea.com/exponentiation-associativity-options

“Talk is cheap. Show me the code.” -Linus Torvalds

Free Pascal Compiler 3.2.2
macOS 12.1: Lazarus 2.2.6 (64 bit Cocoa M1)
Ubuntu 18.04.3: Lazarus 2.2.6 (64 bit on VBox)
Windows 7 Pro SP1: Lazarus 2.2.6 (64 bit on VBox)

marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11383
  • FPC developer.
Re: Unary prefix operators and the infix to postfix algorithm
« Reply #12 on: October 06, 2021, 07:16:42 pm »
2^2^3

is another tricky one. 64 or 256?

64 both.

Personally I don't care that much, but the unary minus thing being unequal between symbolic and fpc doesn't sit right. 
« Last Edit: October 06, 2021, 07:22:59 pm by marcov »

MarkMLl

  • Hero Member
  • *****
  • Posts: 6676
Re: Unary prefix operators and the infix to postfix algorithm
« Reply #13 on: October 06, 2021, 07:58:12 pm »
Painful. I'd vote for -2**2 being equivalent to (-2)**2 i.e. 4, because having the potential of a different result depending on whether the lexer permits - as part of a numeric pattern (which by analogy it should, if 1.0E-3 is to be valid) would be too painful to contemplate.

And particularly if ** is used for exponentiation rather than ^, I'd vote for left-to-right evaluation since the most popular convention is that * used for multiplication evaluates left-to-right unless guided by parentheses.

Or to misquote Torvalds: "Code is cheap. Show me the parentheses." :-)

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

VTwin

  • Hero Member
  • *****
  • Posts: 1215
  • Former Turbo Pascal 3 user
Re: Unary prefix operators and the infix to postfix algorithm
« Reply #14 on: October 06, 2021, 08:29:54 pm »
I tend to be biased in favor of Matlab/Octave (64), but clearly there is not a consensus.  R, Python, and Fortran give 256.

I agree, parentheses are cheap, use them!  :)

I also agree that symbolic and fpc should agree.
« Last Edit: October 06, 2021, 08:32:03 pm by VTwin »
“Talk is cheap. Show me the code.” -Linus Torvalds

Free Pascal Compiler 3.2.2
macOS 12.1: Lazarus 2.2.6 (64 bit Cocoa M1)
Ubuntu 18.04.3: Lazarus 2.2.6 (64 bit on VBox)
Windows 7 Pro SP1: Lazarus 2.2.6 (64 bit on VBox)

 

TinyPortal © 2005-2018