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 =