Parsing/RPN to infix conversion: Difference between revisions
(Ada solution added) |
No edit summary |
||
Line 605: | Line 605: | ||
+-+-----------------------------+ |
+-+-----------------------------+ |
||
3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3</lang> |
3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3</lang> |
||
=={{header|Perl}}== |
|||
<lang perl> |
|||
# RPN to infix conversion |
|||
# |
|||
# Nigel Galloway April 1st., 2012 |
|||
# |
|||
$WSb = '(?:^|\s+)'; |
|||
$WSa = '(?:\s+|$)'; |
|||
$num = '([+-/$]?(?:\.\d+|\d+(?:\.\d*)?))'; |
|||
$op = '([-+*/^])'; |
|||
while (<>) { |
|||
$n = -1; |
|||
while (s/$WSb$num\s+$num\s+$op$WSa/' '.('$'.++$n).' '/e) {@elems[$n] = '('.$1.$3.$2.')';} |
|||
while (s!(\$)(\d+)!@elems[$2]!e) {} |
|||
print(substr($_,2,-2)."\n"); |
|||
} |
|||
</lang> |
|||
Produces: |
|||
<pre> |
|||
>rpn.pl |
|||
1 2 + 3 4 + ^ 5 6 + ^ |
|||
((1+2)^(3+4))^(5+6) |
|||
3 4 2 * 1 5 - 2 3 ^ ^ / + |
|||
3+((4*2)/((1-5)^(2^3))) |
|||
</pre> |
|||
=={{header|Perl 6}}== |
=={{header|Perl 6}}== |
||
<lang perl6>my @tests = '3 4 2 * 1 5 - 2 3 ^ ^ / +', |
<lang perl6>my @tests = '3 4 2 * 1 5 - 2 3 ^ ^ / +', |
Revision as of 12:53, 1 April 2012
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.
Ada
Using the solution of the task stack: <lang Ada>
type Priority is range 1..4; type Infix is record Precedence : Priority; Expression : Unbounded_String; end record; package Expression_Stack is new Generic_Stack (Infix); use Expression_Stack;
function Convert (RPN : String) return String is Arguments : Stack; procedure Pop ( Operation : Character; Precedence : Priority; Association : Priority ) is Right, Left : Infix; Result : Infix; begin Pop (Right, Arguments); Pop (Left, Arguments); Result.Precedence := Association; if Left.Precedence < Precedence then Append (Result.Expression, '('); Append (Result.Expression, Left.Expression); Append (Result.Expression, ')'); else Append (Result.Expression, Left.Expression); end if; Append (Result.Expression, ' '); Append (Result.Expression, Operation); Append (Result.Expression, ' '); if Right.Precedence < Precedence then Append (Result.Expression, '('); Append (Result.Expression, Right.Expression); Append (Result.Expression, ')'); else Append (Result.Expression, Right.Expression); end if; Push (Result, Arguments); end Pop; Pointer : Integer := RPN'First; begin while Pointer <= RPN'Last loop case RPN (Pointer) is when ' ' => Pointer := Pointer + 1; when '0'..'9' => declare Start : constant Integer := Pointer; begin loop Pointer := Pointer + 1; exit when Pointer > RPN'Last or else RPN (Pointer) not in '0'..'9'; end loop; Push ( ( 4, To_Unbounded_String (RPN (Start..Pointer - 1)) ), Arguments ); end; when '+' | '-' => Pop (RPN (Pointer), 1, 1); Pointer := Pointer + 1; when '*' | '/' => Pop (RPN (Pointer), 2, 2); Pointer := Pointer + 1; when '^' => Pop (RPN (Pointer), 4, 3); Pointer := Pointer + 1; when others => raise Constraint_Error with "Syntax"; end case; end loop; declare Result : Infix; begin Pop (Result, Arguments); return To_String (Result.Expression); end; end Convert;
</lang> The test program: <lang Ada> with Ada.Strings.Unbounded; use Ada.Strings.Unbounded; with Ada.Text_IO; use Ada.Text_IO; with Generic_Stack;
procedure RPN_to_Infix is
-- The code above
begin
Put_Line ("3 4 2 * 1 5 - 2 3 ^ ^ / + = "); Put_Line (Convert ("3 4 2 * 1 5 - 2 3 ^ ^ / +")); Put_Line ("1 2 + 3 4 + ^ 5 6 + ^ = "); Put_Line (Convert ("1 2 + 3 4 + ^ 5 6 + ^"));
end RPN_to_Infix; </lang> should produce the following 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)
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'
Go
No error checking. <lang go>package main
import (
"fmt" "strings"
)
var tests = []string{
"3 4 2 * 1 5 - 2 3 ^ ^ / +", "1 2 + 3 4 + ^ 5 6 + ^",
}
var opa = map[string]struct {
prec int rAssoc bool
}{
"^": {4, true}, "*": {3, false}, "/": {3, false}, "+": {2, false}, "-": {2, false},
}
const nPrec = 9
func main() {
for _, t := range tests { parseRPN(t) }
}
func parseRPN(e string) {
fmt.Println("\npostfix:", e) type sf struct { prec int expr string } var stack []sf for _, tok := range strings.Fields(e) { fmt.Println("token:", tok) if op, isOp := opa[tok]; isOp { rhs := &stack[len(stack)-1] stack = stack[:len(stack)-1] lhs := &stack[len(stack)-1] if lhs.prec < op.prec || (lhs.prec == op.prec && op.rAssoc) { lhs.expr = "(" + lhs.expr + ")" } lhs.expr += " " + tok + " " if rhs.prec < op.prec || (rhs.prec == op.prec && !op.rAssoc) { lhs.expr += "(" + rhs.expr + ")" } else { lhs.expr += rhs.expr } lhs.prec = op.prec } else { stack = append(stack, sf{nPrec, tok}) } for _, f := range stack { fmt.Printf(" %d %q\n", f.prec, f.expr) } } fmt.Println("infix:", stack[0].expr)
}</lang> Output:
postfix: 3 4 2 * 1 5 - 2 3 ^ ^ / + token: 3 9 "3" token: 4 9 "3" 9 "4" token: 2 9 "3" 9 "4" 9 "2" token: * 9 "3" 3 "4 * 2" token: 1 9 "3" 3 "4 * 2" 9 "1" token: 5 9 "3" 3 "4 * 2" 9 "1" 9 "5" token: - 9 "3" 3 "4 * 2" 2 "1 - 5" token: 2 9 "3" 3 "4 * 2" 2 "1 - 5" 9 "2" token: 3 9 "3" 3 "4 * 2" 2 "1 - 5" 9 "2" 9 "3" token: ^ 9 "3" 3 "4 * 2" 2 "1 - 5" 4 "2 ^ 3" token: ^ 9 "3" 3 "4 * 2" 4 "(1 - 5) ^ 2 ^ 3" token: / 9 "3" 3 "4 * 2 / (1 - 5) ^ 2 ^ 3" token: + 2 "3 + 4 * 2 / (1 - 5) ^ 2 ^ 3" infix: 3 + 4 * 2 / (1 - 5) ^ 2 ^ 3 postfix: 1 2 + 3 4 + ^ 5 6 + ^ token: 1 9 "1" token: 2 9 "1" 9 "2" token: + 2 "1 + 2" token: 3 2 "1 + 2" 9 "3" token: 4 2 "1 + 2" 9 "3" 9 "4" token: + 2 "1 + 2" 2 "3 + 4" token: ^ 4 "(1 + 2) ^ (3 + 4)" token: 5 4 "(1 + 2) ^ (3 + 4)" 9 "5" token: 6 4 "(1 + 2) ^ (3 + 4)" 9 "5" 9 "6" token: + 4 "(1 + 2) ^ (3 + 4)" 2 "5 + 6" token: ^ 4 "((1 + 2) ^ (3 + 4)) ^ (5 + 6)" infix: ((1 + 2) ^ (3 + 4)) ^ (5 + 6)
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>
Perl
<lang perl>
- RPN to infix conversion
- Nigel Galloway April 1st., 2012
$WSb = '(?:^|\s+)'; $WSa = '(?:\s+|$)'; $num = '([+-/$]?(?:\.\d+|\d+(?:\.\d*)?))'; $op = '([-+*/^])'; while (<>) {
$n = -1; while (s/$WSb$num\s+$num\s+$op$WSa/' '.('$'.++$n).' '/e) {@elems[$n] = '('.$1.$3.$2.')';} while (s!(\$)(\d+)!@elems[$2]!e) {} print(substr($_,2,-2)."\n");
} </lang> Produces:
>rpn.pl 1 2 + 3 4 + ^ 5 6 + ^ ((1+2)^(3+4))^(5+6) 3 4 2 * 1 5 - 2 3 ^ ^ / + 3+((4*2)/((1-5)^(2^3)))
Perl 6
<lang perl6>my @tests = '3 4 2 * 1 5 - 2 3 ^ ^ / +',
'1 2 + 3 4 + ^ 5 6 + ^';
say rpm-to-infix($_) for @tests;
sub p ($pair, $prec) {
$pair.key < $prec ?? "( $pair.value() )" !! $pair.value
} sub rpm-to-infix($string) {
say "=================\n$string"; my @stack; for $string.words { when /\d/ { @stack.push: 9 => $_ } my $y = @stack.pop; my $x = @stack.pop; when '^' { @stack.push: 4 => ~(p($x,5), $_, p($y,4)) } when '*' | '/' { @stack.push: 3 => ~(p($x,3), $_, p($y,3)) } when '+' | '-' { @stack.push: 2 => ~(p($x,2), $_, p($y,2)) } LEAVE { say @stack } } say "-----------------"; @stack».value;
}</lang>
- Output:
================= 3 4 2 * 1 5 - 2 3 ^ ^ / + 9 => "3" 9 => "3" 9 => "4" 9 => "3" 9 => "4" 9 => "2" 9 => "3" 3 => "4 * 2" 9 => "3" 3 => "4 * 2" 9 => "1" 9 => "3" 3 => "4 * 2" 9 => "1" 9 => "5" 9 => "3" 3 => "4 * 2" 2 => "1 - 5" 9 => "3" 3 => "4 * 2" 2 => "1 - 5" 9 => "2" 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 2 + 3 4 + ^ 5 6 + ^ 9 => "1" 9 => "1" 9 => "2" 2 => "1 + 2" 2 => "1 + 2" 9 => "3" 2 => "1 + 2" 9 => "3" 9 => "4" 2 => "1 + 2" 2 => "3 + 4" 4 => "( 1 + 2 ) ^ ( 3 + 4 )" 4 => "( 1 + 2 ) ^ ( 3 + 4 )" 9 => "5" 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 )
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
@(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: [@rpn]
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)
(each ((term rpn))
(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))
(format t "stack: ~s\n" stack))
(if (rest stack)
(return-from error "*excess stack elements*"))
(pop 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)
$ ./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