Parsing/RPN to infix conversion
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 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.
RPN input sample output 3 4 2 * 1 5 - 2 3 ^ ^ / +3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 31 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'
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)