How to resolve the algorithm Parsing/RPN to infix conversion step by step in the PicoLisp programming language
Published on 12 May 2024 09:40 PM
How to resolve the algorithm Parsing/RPN to infix conversion step by step in the PicoLisp programming language
Table of Contents
Problem Statement
Create a program that takes an RPN representation of an expression formatted as a space separated sequence of tokens and generates the equivalent expression in infix notation.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Parsing/RPN to infix conversion step by step in the PicoLisp programming language
Source code in the picolisp programming language
(de leftAssoc (Op)
(member Op '("*" "/" "+" "-")) )
(de precedence (Op)
(case Op
("\^" 4)
(("*" "/") 3)
(("+" "-") 2) ) )
(de rpnToInfix (Str)
(let Stack NIL
(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")) ) ) )
: (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)"
You may also check:How to resolve the algorithm Number names step by step in the VBA programming language
You may also check:How to resolve the algorithm Brace expansion step by step in the Common Lisp programming language
You may also check:How to resolve the algorithm Bitwise IO step by step in the J programming language
You may also check:How to resolve the algorithm GUI/Maximum window dimensions step by step in the Tcl programming language
You may also check:How to resolve the algorithm Arrays step by step in the BBC BASIC programming language