Parsing/RPN to infix conversion: Difference between revisions

From Rosetta Code
Content added Content deleted
m (→‎{{header|Ruby}}: update output to correspond with updated tests)
m (→‎{{header|Ruby}}: show code that generates output)
Line 262: Line 262:
See [[Parsing/RPN/Ruby]]
See [[Parsing/RPN/Ruby]]


<lang ruby>rpn = RPNExpression.new("3 4 2 * 1 5 - 2 3 ^ ^ / +")
The relevant output from testing is
infix = rpn.to_infix
ruby = rpn.to_ruby</lang>
outputs
<pre>for RPN expression: 3 4 2 * 1 5 - 2 3 ^ ^ / +
<pre>for RPN expression: 3 4 2 * 1 5 - 2 3 ^ ^ / +
Term Action Stack
Term Action Stack

Revision as of 15:40, 6 December 2011

Parsing/RPN to infix conversion is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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 input RPN string '3 4 2 * 1 5 - 2 3 ^ ^ / +' then print and display the output here.
  • 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

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

  1. Helpers

proc precedence op { 

   dict get {^ 4 * 3 / 3 + 2 - 2} $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 set prec [precedence $token] if {$aprec < $prec} {set a "($a)"} if {$bprec < $prec} {set b "($b)"} lappend stack [list $prec "$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 ^ ^ / +}]</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
Retrieved from "https://rosettacode.org/wiki/Parsing/RPN_to_infix_conversion?oldid=209373"