Received: by 10.66.85.136 with SMTP id h8mr1787190paz.46.1350798638731;
        Sat, 20 Oct 2012 22:50:38 -0700 (PDT)
Path: s9ni28015pbb.0!nntp.google.com!border1.nntp.dca.giganews.com!border4.nntp.dca.giganews.com!border2.nntp.dca.giganews.com!nntp.giganews.com!novia!news-hub.siol.net!news.mi.ras.ru!goblin3!goblin2!goblin1!goblin.stu.neva.ru!eternal-september.org!feeder.eternal-september.org!mx04.eternal-september.org!.POSTED!not-for-mail
From: "luser.droog" <luser.dr...@gmail.com>
Newsgroups: comp.lang.postscript
Subject: Re: How to do Algebraic Mode in PS like the HP does?
Date: Sun, 14 Oct 2012 04:43:10 -0500
Organization: unorganized
Lines: 297
Message-ID: <k5e1fp$our$1@dont-email.me>
References: <ae22e8f0-ad4a-491d-9255-155b04c7aa66@j25g2000yqn.googlegroups.com> <988c7d8d-49db-4d82-b878-a0466503a0c6@googlegroups.com> <k0b0js$nqu$1@reader1.panix.com> <ef3f384c-2a6e-4850-8286-7d75b4b63179@googlegroups.com> <k3ou4d$c8i$1@reader1.panix.com> <k45r3i$5ki$1@dont-email.me> <k48n03$98q$1@dont-email.me> <k5b2de$5m2$1@dont-email.me> <k5djt7$q0k$1@dont-email.me>
Mime-Version: 1.0
Injection-Info: mx04.eternal-september.org; posting-host="744e40ad726a36842c02abb0656cbad1";
	logging-data="25563"; mail-complaints-to="ab...@eternal-september.org";	posting-account="U2FsdGVkX1/jpSoyxieTWsBooWxpqM6qaF9Sp76E9CI="
User-Agent: KNode/0.10.9
Cancel-Lock: sha1:PqTsq/A76m2hRRU4lrt/tWyLrzI=
Bytes: 9547
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7Bit

luser.droog wrote:

> luser.droog wrote:
> 
>>>  
>>> A little more searching led me to this:
>>>
>>
>
http://devmaster.net/posts/2866/processing-arithmetic-expressions-with-the-shunting-yard-algorithm
>>> 
>>> Looks very promising.
>> 
>> Another draft.
>> This one uses `token` to consume the string,
>> and evaluates instead of generating a postfix representation.
>> 
>> But I think this makes for a simple, extensible base.  ?maybe?
>> 
> 
> Added boolean and relational ops, and unary + and -.
> Variable assignment seems like a bitch. Could use `def`
> but then we have to juggle the eval dict off the dictstack.
> Could require that it be defined in an outer scope and use
> `store`. But then we're "requiring things": ie, not ideal.
> And functions seems like more pain, since we can't easily
> snag the left paren using `token` this way.
> 

Don't need to! We can snag the whole substring. Then look
backwards to the previous token to see if it was (once) 
a function name. 

Added function calls (must be defined in the /func dictionary),
prefix/postfix ops. And reprise the snazzy argument helper,
give it a name that reminds you to `end` later, and Presto!

And Comments!

531(1)04:35 AM:ps 0> cat infix4.ps
%!
%infix4.ps
% Implementation of the Shunting-Yard Algorithm
% for (infix) algebraic formula evaluation in PS
%Caveats:
% Since it uses the PS `token` operator to scan
% the string, all elements must be separated by spaces
% except (balanced parens) which are "self-delimiting".
% This is why we cannot use '<' or '>' because
% `token` considers them to be balanced delimiters
% enclosing a hex-string. So we use 'lt' and 'gt' and
% just map them to the same names.
% In particular , commas must be "fully-articulated":
% (atan(a , - b)) eval     % ie.: a b neg atan

%a helper procedure
/factorial { 1 exch cvi abs -1 1 {mul} for } def

%the basis of the operator tables
%this array is sliced into 3 dictionaries
%relating the key to its various properties
[ %   oper  prec  left
[ /,  {/prev null def} 12 true ]
[ /fac {factorial}
             11   false  ]
[ /plus {}   10   true   ]
[ /neg {neg} 10   true   ]

[ /&   {and} 9     true   ]
[ /and {and} 9     true   ]
[ /|   {or}  8     true   ]
[ /or  {or}  8     true   ]
[ /^   {xor} 7     true   ]
[ /xor {xor} 7     true   ]

[ /eq {eq}  6     true   ]
[ /ne {ne}  6     true   ]
[ /gt {gt}  5     true   ]
[ /ge {ge}  5     true   ]
[ /lt {lt}  5     true   ]
[ /le {le}  5     true   ]

[ /** {exp} 4     false  ]
[ /*  {mul} 3     true   ]
%the single slash / is a sigil in PS
% which resolves to the empty name
[ /   {div} 3     true   ]
[ /+  {add} 2     true   ]
[ /-  {sub} 2     true   ]

]
dup /oper exch dup length dict begin {
    dup 0 get exch 1 get def
} forall currentdict end def
dup /prec exch dup length dict begin {
    dup 0 get exch 2 get def
} forall currentdict end def
dup /left exch dup length dict begin {
    dup 0 get exch 3 get def
} forall currentdict end def
pop

%prefix operators + (do nothing) and - (negate)
/preop 2 dict begin
    /+ /plus def
    /- /neg def
currentdict end def

%postfix operator ! (factorial)
/postop 1 dict begin
    /! /fac def
currentdict end def

%recognized function names
/func 10 dict begin
    /sin {sin} def
    /cos {cos} def
    /exp {exp} def
    /abs {abs} def
    /ceil {ceiling} def
    /floor {floor} def
    /round {round} def
    /trunc {truncate} def
    /sqrt {sqrt} def
    /ln {ln} def
    /log {log} def
    /atan {atan} def
currentdict end def

%opstack utilities
% push and pop to/from the operator stack array
% NB not well encapsulated. should provide 'isempty' or 'count'
/oppush {
    /opptr opptr 1 add def
    opptr opstack length eq { /stackoverflow signalerror } if
    opstack opptr 3 2 roll put
} def
/oppop {
    opptr -1 eq { /stackunderflow signalerror } if
    opstack opptr get
    /opptr opptr 1 sub def
} def

%We process the string left-to-right, using the normal
%PS scanner `token` and call these procedures upon encountering
%the various types in the object returned by `token`
/process { dup type exec } def
/booleantype { } def % "Data" types: leave on stack (do nothing)
/integertype { } def
/realtype { } def
/stringtype { % process substring
              % and perform function call depending upon /prev
    /prev load null ne { func /prev load known {
        exch pop %func name may have resolved to PS -operator-
    } if } if
    eval
    /prev load null ne { func /prev load known {
        func /prev load get exec
    } if } if
} def

/nametype { % process an operator or variable lookup
    %(name)= dup == flush

    %prev is oper or null: prefix
    /prev load null eq {
        unop
    }{

        oper /prev load known {
            unop
        }{ %prev is operand: postfix or binary
            dup postop exch known { %postfix
                    %load the postfix op from postop
                postop exch get cvx
                binop %"fall thru"
            }{ %binary
                binop
            } ifelse
        } ifelse

    } ifelse

} def

%process a prefix operator
/unop {
    %(pre)= dup == flush
    dup preop exch known {
        preop exch get cvx %load the prefix op frop preop
            % this resolves to a high-precedence operator
            % which, of course, "happens" to be unary.
            % There's no "stack-checking" going on anywhere.
        doop % pop opstack until prec(tos) <|<= prec(op)
    }{ %not an op
        dup where { exch get } if %load variable
            % It is this step which is WRONG for
            % function names. But we discard it and
            % check /prev to workaround.
    } ifelse
} def

/binop {
    %(bin)= dup == flush
    dup oper exch known { %it IS an operator
        doop % pop opstack until prec(tos) <|<= prec(op)
    }{ %not an op
        dup where { exch get } if %load variable
            % Ditto. ^^^^^ WRONG ^^^^
    } ifelse
} def

/doop {
    /op exch def % stash the op in /op
    {
        opptr 0 lt { exit } if %opstack empty: return
        prec opstack opptr get get % prec(tos)
        prec /op load get          % prec(tos) prec(op)
            left /op load get      % prec(tos) prec(op) left(op)
            { ge }{ gt }ifelse    % prec(tos)>|>=prec(op)
        { %prec(tos)>prec(op)
            oper oppop get exec %pop and apply
        }{
            exit %tos sufficiently popped for now
        } ifelse
    } loop
    /op load oppush % push the op
} def

% (infix-expression)  eval  result
%the main entry point
% expects a string (or other token source) on stack
% upon completion, yields the result of evaluation on the stack
/eval { 10 dict begin
    /opstack 50 array def
    /opptr -1 def
    /tok null def
    { %loop until no more tokens
        token {
            exch /rem exch def %stash the remainder
            /tok exch
            /prev /tok load def def %stash /tok and /prev
            /tok load process %process tok according to type
            rem
        }{
            exit %no more tokens: exit the loop
        } ifelse
    } loop
        %apply and pop the opstack until empty
    opptr 1 add { oper oppop get exec } repeat
end } def

%Some simplistic testing
/testeval {
    /a 2 def (a = )print a =
    /b 3 def (b = )print b =
    [
    (a + b)
    (a * b)
    (a + b * b)
    (a * b + b)
    (a + b / a * b)
    (b * b * b / a * b * a)
    ((b * b * b) / (a * b * a))
    (1 + 2 + 3 + 4)
    (1 * 2 * 3 * 4)
    (3 + 4 * 2 / ( 1 - 5 ) ** 2 ** 3)
    (b eq b)
    (a le b)
    (a gt b)
    ((a lt b) or (5 ne 5))
    (+ 5)
    (- 12 * b / a)
    (2 !)
    (3 !)
    (4 !)
    (5 !)
    (6 !)
    (3 ! !)
    (sin (30))
    (sin(b)** 2 + cos(b)** 2)
    (exp(10 , 5))
    (atan(b , - a))
    ] { dup print(=)= eval = } forall
} def
testeval

%argument assignment shortcut
/$begin { dup length dict begin { exch def } forall } def

%simple example
/dist { {/y/x}$begin (sqrt(x ** 2 + y ** 2)) eval end } def

(1 1 dist =)= 1 1 dist =