Arithmetic evaluation: Difference between revisions
→{{header|RPL}}: real AST-based evaluator
(→{{header|RPL}}: real AST-based evaluator) |
|||
Line 5,573:
=={{header|RPL}}==
This expression evaluator generates the AST through an RPN converter based on the shunting-yard algorithm.
<code>LEXER</code> is defined at [[Parsing/Shunting-yard algorithm#RPL|Parsing/Shunting-yard algorithm]]
{{works with|HP|48}}
≪ '''IF''' OVER '''THEN'''
"^*/+-" DUP 5 PICK POS SWAP ROT POS
{ 4 3 3 2 2 } { 1 0 0 0 0 }
→ o2 o1 prec rasso
≪ '''IF''' o2 '''THEN'''
prec o1 GET prec o2 GET
'''IF''' rasso o1 GET '''THEN''' < '''ELSE''' ≤ '''END'''
'''ELSE''' 0 '''END'''
≫
'''ELSE''' DROP 0 '''END'''
≫ ‘<span style="color:blue>POPOP?</span>’ STO
<span style="color:grey>@ ''( op → Boolean )''</span>
≪ { } "" → infix postfix token
≪ 0
1 infix SIZE '''FOR''' j
infix j GET 'token' STO
1 SF
'''CASE'''
"^*/+-" token →STR POS '''THEN'''
1 CF
'''WHILE''' token <span style="color:blue>POPOP?</span> '''REPEAT'''
'postfix' ROT STO+ 1 - '''END'''
token SWAP 1 + '''END'''
"(" token == '''THEN'''
token SWAP 1 + '''END'''
")" token == '''THEN'''
'''WHILE''' DUP 1 FS? AND '''REPEAT'''
'''IF''' OVER "(" ≠ '''THEN'''
'postfix' ROT STO+
'''ELSE''' SWAP DROP 1 CF '''END'''
1 -
'''END'''
'''END'''
1 FS? '''THEN''' 'postfix' token STO+ '''END'''
'''END'''
'''NEXT'''
'''WHILE''' DUP '''REPEAT'''
'postfix' ROT STO+ 1 - '''END'''
DROP
≫ ≫ ‘<span style="color:blue>→RPN</span>’ STO
<span style="color:grey>@ ''( { infixed tokens } → { postfixed tokens )''</span>
≪ DUP SIZE → len
≪ '''IF''' len '''THEN'''
DUP len GET SWAP
'''IF''' len 1 ≠ '''THEN''' 1 len 1 - SUB '''ELSE''' DROP { } '''END'''
'''IF''' OVER TYPE '''THEN'''
<span style="color:blue>→AST</span> <span style="color:blue>→AST</span>
4 ROLLD ROT ROT 3 →LIST SWAP
'''END'''
'''ELSE''' "Err" SWAP '''END'''
≫ ≫ ‘<span style="color:blue>→AST</span>’ STO
<span style="color:grey>@ ''( { postfixed tokens } → { AST } )''</span>
≪ DUP 1 GET
'''IF''' DUP TYPE '''THEN''' <span style="color:blue>AST→N</span> '''END'''
OVER 3 GET
'''IF''' DUP TYPE '''THEN''' <span style="color:blue>AST→N</span> '''END'''
ROT 2 GET "≪" SWAP + "≫" + STR→ EVAL
≫ ‘<span style="color:blue>AST→N</span>' STO
<span style="color:grey>@ ''( { AST } → value )''</span>
≪ <span style="color:blue>LEXER</span> <span style="color:blue>→RPN</span>
<span style="color:blue>→AST</span> DROP DUP <span style="color:grey>@ DUP is just here to leave the AST in the stack</span>
<span style="color:blue>AST→N</span>
≫ ‘<span style="color:blue>AEVAL</span>’ STO
"3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3" <span style="color:blue>AEVAL</span>
{{out}}
<pre>
2: { 3 "+" { { 4 "*" 2 } "/" { { 1 "-" 5 } "^" { 2 "^" 3 } } } }
1: 3.00012207031
</pre>
| |||