Anonymous user
Parsing/RPN to infix conversion: Difference between revisions
Added PicoLisp
(→{{header|TXR}}: Use quasiliterals instead of formatting to a string stream.) |
(Added PicoLisp) |
||
Line 342:
+-+-----------------------------+
3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3</lang>
=={{header|PicoLisp}}==
We maintain a stack of cons pairs, consisting of precedences and partial expressions. Numbers get a "highest" precedence of '9'.
<lang PicoLisp>(de leftAssoc (Op)
(member Op '("*" "/" "+" "-")) )
(de precedence (Op)
(case Op
("\^" 4)
(("*" "/") 3)
(("+" "-") 2) ) )
(de rpnToInfix (Str)
(let (Fmt (-7 -30 -4) Stack)
(prinl "Token Stack")
(for Token (str Str "_")
(cond
((num? Token) (push 'Stack (cons 9 @))) # Highest precedence
((not (cdr Stack)) (quit "Stack empty"))
(T
(let (X (pop 'Stack) P (precedence Token))
(set Stack
(cons P
(pack
(if ((if (leftAssoc Token) < <=) (caar Stack) P)
(pack "(" (cdar Stack) ")")
(cdar Stack) )
" " Token " "
(if ((if (leftAssoc Token) <= <) (car X) P)
(pack "(" (cdr X) ")")
(cdr X) ) ) ) ) ) ) )
(prin Token)
(space 6)
(println Stack) )
(prog1 (cdr (pop 'Stack))
(and Stack (quit "Garbage remained on stack")) ) ) )</lang>
Test (note that the top-of-stack is in the left-most position):
<lang PicoLisp>: (rpnToInfix "3 4 2 * 1 5 - 2 3 \^ \^ / +")
Token Stack
3 ((9 . 3))
4 ((9 . 4) (9 . 3))
2 ((9 . 2) (9 . 4) (9 . 3))
* ((3 . "4 * 2") (9 . 3))
1 ((9 . 1) (3 . "4 * 2") (9 . 3))
5 ((9 . 5) (9 . 1) (3 . "4 * 2") (9 . 3))
- ((2 . "1 - 5") (3 . "4 * 2") (9 . 3))
2 ((9 . 2) (2 . "1 - 5") (3 . "4 * 2") (9 . 3))
3 ((9 . 3) (9 . 2) (2 . "1 - 5") (3 . "4 * 2") (9 . 3))
^ ((4 . "2 \^ 3") (2 . "1 - 5") (3 . "4 * 2") (9 . 3))
^ ((4 . "(1 - 5) \^ 2 \^ 3") (3 . "4 * 2") (9 . 3))
/ ((3 . "4 * 2 / (1 - 5) \^ 2 \^ 3") (9 . 3))
+ ((2 . "3 + 4 * 2 / (1 - 5) \^ 2 \^ 3"))
-> "3 + 4 * 2 / (1 - 5) \^ 2 \^ 3"
: (rpnToInfix "1 2 + 3 4 + \^ 5 6 + \^")
Token Stack
1 ((9 . 1))
2 ((9 . 2) (9 . 1))
+ ((2 . "1 + 2"))
3 ((9 . 3) (2 . "1 + 2"))
4 ((9 . 4) (9 . 3) (2 . "1 + 2"))
+ ((2 . "3 + 4") (2 . "1 + 2"))
^ ((4 . "(1 + 2) \^ (3 + 4)"))
5 ((9 . 5) (4 . "(1 + 2) \^ (3 + 4)"))
6 ((9 . 6) (9 . 5) (4 . "(1 + 2) \^ (3 + 4)"))
+ ((2 . "5 + 6") (4 . "(1 + 2) \^ (3 + 4)"))
^ ((4 . "((1 + 2) \^ (3 + 4)) \^ (5 + 6)"))
-> "((1 + 2) \^ (3 + 4)) \^ (5 + 6)"</lang>
=={{header|Python}}==
| |||