Parsing/RPN to infix conversion
Create a program that takes an RPN representation of an expression formatted as a space separated sequence of tokens and generates the same expression in infix notation and using a minimum of parenthesis.
- 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.
You are encouraged to solve this task according to the task description, using any language you may know.
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>
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)