Unary prefix operators and the infix to postfix algorithm lazarus / 62-General ---------------------------------------------------------------------- grawlix · 2021-10-06 10:41 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. ---------------------------------------------------------------------- MarkMLl · 2021-10-06 11:17 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 ---------------------------------------------------------------------- marcov · 2021-10-06 11:32 Quote from: grawlix on October 06, 2021, 12:41:35 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][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i  If (OperationNr=psub) then  {Minus(x) or x-y?}       begin        IsMinus:=False;        if I=1 then  // first token of string         IsMinus:=true        else         If Expr[I-1] IN ['+','(','*','/','-','^'] then  // previous token binary operator or opening parenthesis          IsMinus:=true;        If IsMinus then       OperationNr:=PMinus;   // change token to unary minus rather than binary minus.       end;  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 · 2021-10-06 14:28 Quote from: MarkMLl on October 06, 2021, 01:17:05 pmSo 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 · 2021-10-06 14:44 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 · 2021-10-06 14:56 Quote from: grawlix on October 06, 2021, 04:44:12 pmI'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 · 2021-10-06 15:05 Quote from: grawlix on October 06, 2021, 04:28:49 pmDoes 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 ---------------------------------------------------------------------- grawlix · 2021-10-06 15:22 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 · 2021-10-06 15:52 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... ---------------------------------------------------------------------- MarkMLl · 2021-10-06 16:02 Quote from: grawlix on October 06, 2021, 05:22:54 pmMake 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 ---------------------------------------------------------------------- marcov · 2021-10-06 16:13 FPC(the compiler) also gives -1, while symbolic gives "1". The division test seems to be ok though. Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i uses symbolic,math; begin  writeln(-1**2);  writeln(quickevaluate('3+-1^2',[],[]));  writeln(quickevaluate('18/6/3',[],[])); end. ---------------------------------------------------------------------- VTwin · 2021-10-06 16:40 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 ---------------------------------------------------------------------- marcov · 2021-10-06 17:16 Quote from: VTwin on October 06, 2021, 06:40:12 pm2^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. ---------------------------------------------------------------------- MarkMLl · 2021-10-06 17:58 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 ---------------------------------------------------------------------- VTwin · 2021-10-06 18:29 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.