Can anybody help me with a small function in lisp.
The function takes a list as its argument that is in postfix notation and
returns the list converted to infix notation.
For example if the list '( a b + c d + * )
is passed in the list ( ( a + b ) * ( c + d ) )
or if the list '( a b c d e f g + - + - + - )
is passed then ( a - ( b + ( c - ( d + ( e - ( f + g ) )))))
The function cannot use any iterative constructs like ( prog , do or loop ).
Any help will be appreciated .
Thank You
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
Looks suspiciously like a homework problem, so I'll give you a hint that
should at the very least get you started. For future reference, if it is a
homework problem and you don't say so, you're unlikely to get a very
friendly response from the newsgroup.
Think of an infix expression as a tree:
a+b => +
/ \
a b
Now, do a tree traversal on this tree in-order, and you get your infix
expression. Do it post-order, and you get post-fix notation. Do it
pre-order, and you get prefix notation. So, your assignment can be looked
upon as reconstructing the expression tree, then doing a traversal. I
suspect you don't actually have to construct the tree, but your program
will have to work with this traversal idea at some level.
Sunil
·······@rit.edu writes:
> Can anybody help me with a small function in lisp.
> The function takes a list as its argument that is in postfix notation and
> returns the list converted to infix notation.
>
> For example if the list '( a b + c d + * )
> is passed in the list ( ( a + b ) * ( c + d ) )
>
> or if the list '( a b c d e f g + - + - + - )
> is passed then ( a - ( b + ( c - ( d + ( e - ( f + g ) )))))
>
> The function cannot use any iterative constructs like ( prog , do or loop ).
> Any help will be appreciated .
>
> Thank You
>
> -----------== Posted via Deja News, The Discussion Network ==----------
> http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
·······@rit.edu writes:
> For example if the list '( a b + c d + * )
> is passed in the list ( ( a + b ) * ( c + d ) )
> or if the list '( a b c d e f g + - + - + - )
> is passed then ( a - ( b + ( c - ( d + ( e - ( f + g ) )))))
...
> The function cannot use any iterative constructs like ( prog , do or loop ).
(defun transmogrify (postfix)
(let ((stack ()))
(loop for element in postfix
if (member element '(+ * - /))
do (push (reverse (list (pop stack) element (pop stack))) stack)
else
do (push element stack))
(first stack)))
Replacing the LOOP is left as an exercise for the reader.
Extra credits for thorough error-checking.
Stig Hemmer,
Jack of a Few Trades.