Anonymous user
Parsing/Shunting-yard algorithm: Difference between revisions
Added PicoLisp
m (→{{header|Icon}} and {{header|Unicon}}: fix bug in tail code simplification) |
(Added PicoLisp) |
||
Line 542:
: 3 4 2 * 1 5 - 2 3 ^ ^ / + : [ ]
RPN = "3 4 2 * 1 5 - 2 3 ^ ^ / + "</pre>
=={{header|PicoLisp}}==
Note: "^" is a meta-character and must be escaped in strings
<lang PicoLisp>(de operator (Op)
(member Op '("\^" "*" "/" "+" "-")) )
(de leftAssoc (Op)
(member Op '("*" "/" "+" "-")) )
(de precedence (Op)
(case Op
("\^" 4)
(("*" "/") 3)
(("+" "-") 2) ) )
(de shuntingYard (Str)
(make
(let (Fmt (-7 -30 -4) Stack)
(tab Fmt "Token" "Output" "Stack")
(for Token (str Str "_")
(cond
((num? Token) (link @))
((= "(" Token) (push 'Stack Token))
((= ")" Token)
(until (= "(" (car Stack))
(unless Stack
(quit "Unbalanced Stack") )
(link (pop 'Stack)) )
(pop 'Stack) )
(T
(while
(and
(operator (car Stack))
((if (leftAssoc (car Stack)) <= <)
(precedence Token)
(precedence (car Stack)) ) )
(link (pop 'Stack)) )
(push 'Stack Token) ) )
(tab Fmt Token (glue " " (made)) Stack) )
(while Stack
(when (= "(" (car Stack))
(quit "Unbalanced Stack") )
(link (pop 'Stack))
(tab Fmt NIL (glue " " (made)) Stack) ) ) ) )</lang>
Output:
<lang PicoLisp>: (shuntingYard "3 + 4 * 2 / (1 - 5) \^ 2 \^ 3")
Token Output Stack
3 3
+ 3 +
4 3 4 +
* 3 4 *+
2 3 4 2 *+
/ 3 4 2 * /+
( 3 4 2 * (/+
1 3 4 2 * 1 (/+
- 3 4 2 * 1 -(/+
5 3 4 2 * 1 5 -(/+
) 3 4 2 * 1 5 - /+
^ 3 4 2 * 1 5 - ^/+
2 3 4 2 * 1 5 - 2 ^/+
^ 3 4 2 * 1 5 - 2 ^^/+
3 3 4 2 * 1 5 - 2 3 ^^/+
3 4 2 * 1 5 - 2 3 ^ ^/+
3 4 2 * 1 5 - 2 3 ^ ^ /+
3 4 2 * 1 5 - 2 3 ^ ^ / +
3 4 2 * 1 5 - 2 3 ^ ^ / +
-> (3 4 2 "*" 1 5 "-" 2 3 "\^" "\^" "/" "+")</lang>
=={{header|Python}}==
| |||