Parsing/RPN to infix conversion: Difference between revisions
(Added PicoLisp) |
m ('Fmt' is not needed) |
||
Line 355: | Line 355: | ||
(de rpnToInfix (Str) |
(de rpnToInfix (Str) |
||
(let |
(let Stack NIL |
||
(prinl "Token Stack") |
(prinl "Token Stack") |
||
(for Token (str Str "_") |
(for Token (str Str "_") |
Revision as of 14:05, 21 December 2011
You are encouraged to solve this task according to the task description, using any language you may know.
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.
- Assume an input of a correct, space separated, string of tokens
- Generate a space separated output string representing the same expression in infix notation
- Show how the major datastructure of your algorithm changes with each new token parsed.
- Test with the following input RPN strings then print and display the output here.
RPN input sample output 3 4 2 * 1 5 - 2 3 ^ ^ / +
3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
1 2 + 3 4 + ^ 5 6 + ^
( ( 1 + 2 ) ^ ( 3 + 4 ) ) ^ ( 5 + 6 )
- Operator precedence is given in this table:
operator precedence associativity ^ 4 Right * 3 Left / 3 Left + 2 Left - 2 Left
- Note
- '^' means exponentiation.
- See also
- Parsing/Shunting-yard algorithm for a method of generating an RPN from an infix expression.
- Parsing/RPN calculator algorithm for a method of calculating a final value from this output RPN expression.
- Postfix to infix from the RubyQuiz site.
AutoHotkey
<lang AHK>expr := "3 4 2 * 1 5 - 2 3 ^ ^ / +"
stack := {push: func("ObjInsert"), pop: func("ObjRemove")} out := "TOKEN`tACTION STACK (comma separated)`r`n" Loop Parse, expr, %A_Space% { token := A_LoopField if token is number stack.push([0, token]) if isOp(token) { b := stack.pop(), a := stack.pop(), p := b.1 > a.1 ? b.1 : a.1 p := Precedence(token) > p ? precedence(token) : p if (a.1 < b.1) and isRight(token) stack.push([p, "( " . a.2 " ) " token " " b.2]) else if (a.1 > b.1) and isLeft(token) stack.push([p, a.2 token " ( " b.2 " ) "]) else stack.push([p, a.2 . " " . token . " " . b.2]) } out .= token "`t" (isOp(token) ? "Push Partial expression " : "Push num" space(16)) disp(stack) "`r`n" } out .= "`r`n The final output infix expression is: '" disp(stack) "'" clipboard := out isOp(t){
return (!!InStr("+-*/^", t) && t)
} IsLeft(o){
return !!InStr("*/+-", o)
} IsRight(o){
return o = "^"
} Precedence(o){
return (InStr("+-/*^", o)+3)//2
} Disp(obj){
for each, val in obj
if val[2] o .= ", " val[2]
return SubStr(o,3)
} Space(n){
return n>0 ? A_Space Space(n-1) : ""
}</lang>
- Output
TOKEN ACTION STACK (comma separated) 3 Push num 3 4 Push num 3, 4 2 Push num 3, 4, 2 * Push Partial expression 3, 4 * 2 1 Push num 3, 4 * 2, 1 5 Push num 3, 4 * 2, 1, 5 - Push Partial expression 3, 4 * 2, 1 - 5 2 Push num 3, 4 * 2, 1 - 5, 2 3 Push num 3, 4 * 2, 1 - 5, 2, 3 ^ Push Partial expression 3, 4 * 2, 1 - 5, 2 ^ 3 ^ Push Partial expression 3, 4 * 2, ( 1 - 5 ) ^ 2 ^ 3 / Push Partial expression 3, 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 + Push Partial expression 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 The final output infix expression is: '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3'
Icon and Unicon
<lang Icon>procedure main() every rpn := ![
"3 4 2 * 1 5 - 2 3 ^ ^ / +", # reqd "1 2 + 3 4 + 5 6 + ^ ^", "1 2 + 3 4 + 5 6 + ^ ^", "1 2 + 3 4 + ^ 5 6 + ^" # reqd ] do { printf("\nRPN = %i\n",rpn) printf("infix = %i\n",RPN2Infix(rpn,show)) show := 1 # turn off inner working display }
end
link printf
procedure RPN2Infix(expr,show) #: RPN to Infix conversion static oi initial {
oi := table([9,"'"]) # precedence & associativity every oi[!"+-"] := [2,"l"] # 2L every oi[!"*/"] := [3,"l"] # 3L oi["^"] := [4,"r"] # 4R } show := if /show then printf else 1 # to show inner workings or not stack := [] expr ? until pos(0) do { # Reformat as a tree tab(many(' ')) # consume previous seperator token := tab(upto(' ')|0) # get token if token := numeric(token) then { # ... numeric push(stack,oi[token]|||[token]) show("pushed numeric %i : %s\n",token,list2string(stack)) } else { # ... operator every b|a := pop(stack) # pop & reverse operands pr := oi[token,1] as := oi[token,2] if a[1] < pr | (a[1] = pr & oi[token,2] == "r") then a[3] := sprintf("( %s )",a[3]) if b[1] < pr | (b[1] == pr & oi[token,2] == "l") then b[3] := sprintf("( %s )",b[3]) s := sprintf("%s %s %s",a[3],token,b[3]) push(stack,[pr,as,s]) # stack [prec, assoc, expr] show("applied operator %s : %s\n",token,list2string(stack)) } } if *stack ~= 1 then stop("Parser failure") return stack[1,3]
end
procedure list2string(L) #: format list as a string
s := "[ " every x := !L do s ||:= ( if type(x) == "list" then list2string(x) else x) || " " return s || "]"
end</lang>
printf.icn provides formatting
Output:
RPN = "3 4 2 * 1 5 - 2 3 ^ ^ / +" pushed numeric 3 : [ [ 9 ' 3 ] ] pushed numeric 4 : [ [ 9 ' 4 ] [ 9 ' 3 ] ] pushed numeric 2 : [ [ 9 ' 2 ] [ 9 ' 4 ] [ 9 ' 3 ] ] applied operator * : [ [ 3 l 4 * 2 ] [ 9 ' 3 ] ] pushed numeric 1 : [ [ 9 ' 1 ] [ 3 l 4 * 2 ] [ 9 ' 3 ] ] pushed numeric 5 : [ [ 9 ' 5 ] [ 9 ' 1 ] [ 3 l 4 * 2 ] [ 9 ' 3 ] ] applied operator - : [ [ 2 l 1 - 5 ] [ 3 l 4 * 2 ] [ 9 ' 3 ] ] pushed numeric 2 : [ [ 9 ' 2 ] [ 2 l 1 - 5 ] [ 3 l 4 * 2 ] [ 9 ' 3 ] ] pushed numeric 3 : [ [ 9 ' 3 ] [ 9 ' 2 ] [ 2 l 1 - 5 ] [ 3 l 4 * 2 ] [ 9 ' 3 ] ] applied operator ^ : [ [ 4 r 2 ^ 3 ] [ 2 l 1 - 5 ] [ 3 l 4 * 2 ] [ 9 ' 3 ] ] applied operator ^ : [ [ 4 r ( 1 - 5 ) ^ 2 ^ 3 ] [ 3 l 4 * 2 ] [ 9 ' 3 ] ] applied operator / : [ [ 3 l 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 ] [ 9 ' 3 ] ] applied operator + : [ [ 2 l 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 ] ] infix = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3" RPN = "1 2 + 3 4 + 5 6 + ^ ^" infix = "( 1 + 2 ) ^ ( 3 + 4 ) ^ ( 5 + 6 )" RPN = "1 2 + 3 4 + 5 6 + ^ ^" infix = "( 1 + 2 ) ^ ( 3 + 4 ) ^ ( 5 + 6 )" RPN = "1 2 + 3 4 + ^ 5 6 + ^" infix = "( ( 1 + 2 ) ^ ( 3 + 4 ) ) ^ ( 5 + 6 )"
J
Implementation:
<lang j>tokenize=: ' ' <;._1@, deb
ops=: ;:'+ - * / ^' doOp=: plus`minus`times`divide`exponent`push@.(ops&i.) parse=:3 :0
stack=: i.0 2 for_token.tokenize y do.doOp token end. 1{:: ,stack
)
parens=:4 :0
if. y do. '( ',x,' )' else. x end.
)
NB. m: precedence, n: is right associative, y: token op=:2 :0
L=. m - n R=. m - -.n smoutput;'operation: ';y 'Lprec left Rprec right'=. ,_2{.stack expr=. ;(left parens L > Lprec);' ';y,' ';right parens R > Rprec stack=: (_2}.stack),m;expr smoutput stack
)
plus=: 2 op 0 minus=: 2 op 0 times=: 3 op 0 divide=: 3 op 0 exponent=: 4 op 1
push=:3 :0
smoutput;'pushing: ';y stack=: stack,_;y smoutput stack
)</lang>
The stack structure has two elements for each stack entry: expression precedence and expression characters.
Required example:
<lang j> parse '3 4 2 * 1 5 - 2 3 ^ ^ / +' pushing: 3 +-+-+ |_|3| +-+-+ pushing: 4 +-+-+ |_|3| +-+-+ |_|4| +-+-+ pushing: 2 +-+-+ |_|3| +-+-+ |_|4| +-+-+ |_|2| +-+-+ operation: * +-+-----+ |_|3 | +-+-----+ |3|4 * 2| +-+-----+ pushing: 1 +-+-----+ |_|3 | +-+-----+ |3|4 * 2| +-+-----+ |_|1 | +-+-----+ pushing: 5 +-+-----+ |_|3 | +-+-----+ |3|4 * 2| +-+-----+ |_|1 | +-+-----+ |_|5 | +-+-----+ operation: - +-+-----+ |_|3 | +-+-----+ |3|4 * 2| +-+-----+ |2|1 - 5| +-+-----+ pushing: 2 +-+-----+ |_|3 | +-+-----+ |3|4 * 2| +-+-----+ |2|1 - 5| +-+-----+ |_|2 | +-+-----+ pushing: 3 +-+-----+ |_|3 | +-+-----+ |3|4 * 2| +-+-----+ |2|1 - 5| +-+-----+ |_|2 | +-+-----+ |_|3 | +-+-----+ operation: ^ +-+-----+ |_|3 | +-+-----+ |3|4 * 2| +-+-----+ |2|1 - 5| +-+-----+ |4|2 ^ 3| +-+-----+ operation: ^ +-+-----------------+ |_|3 | +-+-----------------+ |3|4 * 2 | +-+-----------------+ |4|( 1 - 5 ) ^ 2 ^ 3| +-+-----------------+ operation: / +-+-------------------------+ |_|3 | +-+-------------------------+ |3|4 * 2 / ( 1 - 5 ) ^ 2 ^ 3| +-+-------------------------+ operation: + +-+-----------------------------+ |2|3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3| +-+-----------------------------+ 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3</lang>
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 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")) ) ) )</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>
Python
<lang python>from collections import namedtuple
OpInfo = namedtuple('OpInfo', 'prec assoc') L, R = 'Left Right'.split()
ops = {
'^': OpInfo(prec=4, assoc=R), '*': OpInfo(prec=3, assoc=L), '/': OpInfo(prec=3, assoc=L), '+': OpInfo(prec=2, assoc=L), '-': OpInfo(prec=2, assoc=L), ')': OpInfo(prec=9, assoc=L), #NUM: OpInfo(prec=0, assoc=L) }
numinfo = OpInfo(prec=9, assoc=L)
NUM, LPAREN, RPAREN = 'NUMBER ( )'.split()
def get_input(inp = None):
'Inputs a space separated expression and returns list of tokens' if inp is None: inp = input('expression: ') return inp.strip().split()
def rpn2infix(tokens):
stack = [] # [ (partial_expr, (prec, assoc)), ... ] table = ['TOKEN,ACTION,STACK (comma separated)'.split(',')] for token in tokens: if token in ops: action = 'Push partial expression' opinfo = ops[token] b = stack.pop(); a = stack.pop() if b[1].prec < opinfo.prec: b = '( %s )' % b[0], ops[')'] if a[1].prec < opinfo.prec: a = '( %s )' % a[0], ops[')'] stack.append( ('%s %s %s' % (a[0], token, b[0]), opinfo) ) else: action = 'Push num' stack.append((token, numinfo)) row = (token, action, ', '.join(str(s[0]) for s in stack)) #pp(row, width=120) table.append( row )
return table
if __name__ == '__main__':
rpn = '3 4 2 * 1 5 - 2 3 ^ ^ / +' print( 'For RPN expression: %r\n' % rpn ) infix = rpn2infix(get_input(rpn)) maxcolwidths = [len(max(x, key=lambda y: len(y))) for x in zip(*infix)] row = infix[0] print( ' '.join('{cell:^{width}}'.format(width=width, cell=cell) for (width, cell) in zip(maxcolwidths, row))) for row in infix[1:]: print( ' '.join('{cell:<{width}}'.format(width=width, cell=cell) for (width, cell) in zip(maxcolwidths, row)))
print('\n The final output infix expression is: %r' % infix[-1][2])</lang>
- Sample output
For RPN expression: '3 4 2 * 1 5 - 2 3 ^ ^ / +' TOKEN ACTION STACK (comma separated) 3 Push num 3 4 Push num 3, 4 2 Push num 3, 4, 2 * Push partial expression 3, 4 * 2 1 Push num 3, 4 * 2, 1 5 Push num 3, 4 * 2, 1, 5 - Push partial expression 3, 4 * 2, 1 - 5 2 Push num 3, 4 * 2, 1 - 5, 2 3 Push num 3, 4 * 2, 1 - 5, 2, 3 ^ Push partial expression 3, 4 * 2, 1 - 5, 2 ^ 3 ^ Push partial expression 3, 4 * 2, ( 1 - 5 ) ^ 2 ^ 3 / Push partial expression 3, 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 + Push partial expression 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 The final output infix expression is: '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3'
Ruby
See Parsing/RPN/Ruby
<lang ruby>rpn = RPNExpression.new("3 4 2 * 1 5 - 2 3 ^ ^ / +") infix = rpn.to_infix ruby = rpn.to_ruby</lang> outputs
for RPN expression: 3 4 2 * 1 5 - 2 3 ^ ^ / + Term Action Stack 3 PUSH [node[3]] 4 PUSH [node[3], node[4]] 2 PUSH [node[3], node[4], node[2]] * MUL [node[3], node[*]<left=node[4], right=node[2]>] 1 PUSH [node[3], node[*]<left=node[4], right=node[2]>, node[1]] 5 PUSH [node[3], node[*]<left=node[4], right=node[2]>, node[1], node[5]] - SUB [node[3], node[*]<left=node[4], right=node[2]>, node[-]<left=node[1], right=node[5]>] 2 PUSH [node[3], node[*]<left=node[4], right=node[2]>, node[-]<left=node[1], right=node[5]>, node[2]] 3 PUSH [node[3], node[*]<left=node[4], right=node[2]>, node[-]<left=node[1], right=node[5]>, node[2], node[3]] ^ EXP [node[3], node[*]<left=node[4], right=node[2]>, node[-]<left=node[1], right=node[5]>, node[^]<left=node[2], right=node[3]>] ^ EXP [node[3], node[*]<left=node[4], right=node[2]>, node[^]<left=node[-]<left=node[1], right=node[5]>, right=node[^]<left=node[2], right=node[3]>>] / DIV [node[3], node[/]<left=node[*]<left=node[4], right=node[2]>, right=node[^]<left=node[-]<left=node[1], right=node[5]>, right=node[^]<left=node[2], right=node[3]>>>] + ADD [node[+]<left=node[3], right=node[/]<left=node[*]<left=node[4], right=node[2]>, right=node[^]<left=node[-]<left=node[1], right=node[5]>, right=node[^]<left=node[2], right=node[3]>>>>] Infix = 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 Ruby = 3 + 4 * 2.to_f / ( 1 - 5 ) ** 2 ** 3
Tcl
<lang tcl>package require Tcl 8.5
- Helpers
proc precassoc op {
dict get {^ {4 right} * {3 left} / {3 left} + {2 left} - {2 left}} $op
} proc pop stk {
upvar 1 $stk s set val [lindex $s end] set s [lreplace $s end end] return $val
}
proc rpn2infix rpn {
foreach token $rpn {
switch $token { "^" - "/" - "*" - "+" - "-" { lassign [pop stack] bprec b lassign [pop stack] aprec a lassign [precassoc $token] p assoc if {$aprec < $p || ($aprec == $p && $assoc eq "right")} { set a "($a)" } if {$bprec < $p || ($bprec == $p && $assoc eq "left")} { set b "($b)" } lappend stack [list $p "$a $token $b"] } default { lappend stack [list 9 $token] } } puts "$token -> $stack"
} return [lindex $stack end 1]
}
puts [rpn2infix {3 4 2 * 1 5 - 2 3 ^ ^ / +}] puts [rpn2infix {1 2 + 3 4 + ^ 5 6 + ^}]</lang> Output:
3 -> {9 3} 4 -> {9 3} {9 4} 2 -> {9 3} {9 4} {9 2} * -> {9 3} {3 {4 * 2}} 1 -> {9 3} {3 {4 * 2}} {9 1} 5 -> {9 3} {3 {4 * 2}} {9 1} {9 5} - -> {9 3} {3 {4 * 2}} {2 {1 - 5}} 2 -> {9 3} {3 {4 * 2}} {2 {1 - 5}} {9 2} 3 -> {9 3} {3 {4 * 2}} {2 {1 - 5}} {9 2} {9 3} ^ -> {9 3} {3 {4 * 2}} {2 {1 - 5}} {4 {2 ^ 3}} ^ -> {9 3} {3 {4 * 2}} {4 {(1 - 5) ^ 2 ^ 3}} / -> {9 3} {3 {4 * 2 / (1 - 5) ^ 2 ^ 3}} + -> {2 {3 + 4 * 2 / (1 - 5) ^ 2 ^ 3}} 3 + 4 * 2 / (1 - 5) ^ 2 ^ 3 1 -> {9 1} 2 -> {9 1} {9 2} + -> {2 {1 + 2}} 3 -> {2 {1 + 2}} {9 3} 4 -> {2 {1 + 2}} {9 3} {9 4} + -> {2 {1 + 2}} {2 {3 + 4}} ^ -> {4 {(1 + 2) ^ (3 + 4)}} 5 -> {4 {(1 + 2) ^ (3 + 4)}} {9 5} 6 -> {4 {(1 + 2) ^ (3 + 4)}} {9 5} {9 6} + -> {4 {(1 + 2) ^ (3 + 4)}} {2 {5 + 6}} ^ -> {4 {((1 + 2) ^ (3 + 4)) ^ (5 + 6)}} ((1 + 2) ^ (3 + 4)) ^ (5 + 6)
TXR
<lang txr>@(next :args) @(define space)@/ */@(end) @(define number (nod))@\
@(local n)@(space)@{n /[0-9]+/}@(space)@\ @(bind nod @(int-str n 10))@\
@(end) @(define op (nod))@\
@(local op)@\ @(space)@\ @(cases)@\ @{op /[+\-*^]/}@\ @(bind nod @(intern op *user-package*))@\ @(or)@\ /@\ @(bind nod @(intern "\\" *user-package*))@\ @(end)@\ @(space)@\
@(end) @(define term (nod))@(cases)@(number nod)@(or)@(op nod)@(end)@(end) @(define rpn (list))@(coll :gap 0 :vars (list))@(term list)@(end)@(end) @(freeform) @(rpn rpn)@junk@\n @(output) rpn tokens: [@(rep)@rpn @(last)@rpn@(end)] trailing junk: [@junk] @(end) @(do (defvar *prec* '((^ . 4)
(* . 3) (\ . 3) (+ . 2) (- . 2))) (defvar *asso* '((^ . :right) (* . :left) (\ . :left) (+ . :left) (- . :left))) (defun rpn-to-lisp (rpn) (let (stack) (for ((iter rpn)) (iter (if (rest stack) (return-from error "*excess stack elements*") (first stack))) ((set iter (cdr iter)) (format t "stack: ~s\n" stack)) (let ((term (car iter))) (format t "rpn term: ~s\n" term) (if (symbolp term) (let ((right (pop stack)) (left (pop stack))) (push '(,term ,left ,right) stack)) (push term stack)))))) (defun prec (term) (cond ((null term) 99) ((symbolp term) (cdr (assoc term *prec*))) ((atom term) 99) (t (prec (car term))))) (defun asso (term) (cond ((null term) :none) ((symbolp term) (cdr (assoc term *asso*))) ((atom term) :none) (t (asso (car term))))) (defun inf-op (op) (if (eq op '\) "/" op)) (defun inf-term (op term left-or-right) (let ((pt (prec term)) (po (prec op)) (at (asso term)) (ao (asso op))) (cond ((< pt po) `(@(lisp-to-infix term))`) ((> pt po) `@(lisp-to-infix term)`) ((and (eq at ao) (eq left-or-right ao)) `@(lisp-to-infix term)`) (t `(@(lisp-to-infix term))`)))) (defun lisp-to-infix (lisp) (if (atom lisp) (if (null lisp) (return-from error "*stack underflow*") (if (eq lisp '\) "/" `@lisp`)) (let ((op (first lisp)) (left (second lisp)) (right (third lisp))) (let ((left-inf (inf-term op left :left)) (right-inf (inf-term op right :right))) `@{left-inf} @(inf-op op) @{right-inf}`)))))
@(bind infix @(block error (lisp-to-infix (rpn-to-lisp rpn)))) @(output) infix: @infix @(end)</lang>
$ ./txr rosetta/rpn.txr '3 4 2 * 1 5 - 2 3 ^ ^ / +' rpn tokens: [3 4 2 * 1 5 - 2 3 ^ ^ \ +] trailing junk: [] rpn term: 3 stack: (3) rpn term: 4 stack: (4 3) rpn term: 2 stack: (2 4 3) rpn term: * stack: ((* 4 2) 3) rpn term: 1 stack: (1 (* 4 2) 3) rpn term: 5 stack: (5 1 (* 4 2) 3) rpn term: - stack: ((- 1 5) (* 4 2) 3) rpn term: 2 stack: (2 (- 1 5) (* 4 2) 3) rpn term: 3 stack: (3 2 (- 1 5) (* 4 2) 3) rpn term: ^ stack: ((^ 2 3) (- 1 5) (* 4 2) 3) rpn term: ^ stack: ((^ (- 1 5) (^ 2 3)) (* 4 2) 3) rpn term: \ stack: ((\ (* 4 2) (^ (- 1 5) (^ 2 3))) 3) rpn term: + stack: ((+ 3 (\ (* 4 2) (^ (- 1 5) (^ 2 3))))) infix: 3 + 4 * 2 / (1 - 5) ^ 2 ^ 3 $ ./txr rosetta/rpn.txr '1 2 + 3 4 + ^ 5 6 + ^' rpn tokens: [1 2 + 3 4 + ^ 5 6 + ^] trailing junk: [] rpn term: 1 stack: (1) rpn term: 2 stack: (2 1) rpn term: + stack: ((+ 1 2)) rpn term: 3 stack: (3 (+ 1 2)) rpn term: 4 stack: (4 3 (+ 1 2)) rpn term: + stack: ((+ 3 4) (+ 1 2)) rpn term: ^ stack: ((^ (+ 1 2) (+ 3 4))) rpn term: 5 stack: (5 (^ (+ 1 2) (+ 3 4))) rpn term: 6 stack: (6 5 (^ (+ 1 2) (+ 3 4))) rpn term: + stack: ((+ 5 6) (^ (+ 1 2) (+ 3 4))) rpn term: ^ stack: ((^ (^ (+ 1 2) (+ 3 4)) (+ 5 6))) infix: ((1 + 2) ^ (3 + 4)) ^ (5 + 6)
Associativity tests (abbreviated output):
$ ./txr rosetta/rpn.txr '1 2 3 + +' [ ... ] infix: 1 + (2 + 3) $ ./txr rosetta/rpn.txr '1 2 + 3 +' [ ... ] infix: 1 + 2 + 3 $ ./txr rosetta/rpn.txr '1 2 3 ^ ^' rpn tokens: [1 2 3 ^ ^] [ ... ] infix: 1 ^ 2 ^ 3 $ ./txr rosetta/rpn.txr '1 2 ^ 3 ^' [ ... ] infix: (1 ^ 2) ^ 3