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 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 ^ 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.
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
This example can also handle variables (x, y, pi, e, ...), variable negations('5 -4 +' -> '5 - 4' and '5 -4 -' -> '5 + 4'), and unary operators (abs, sqrt, exp, ln, log, sin, cos, tan).
The unary operators have the highest precedence.
To maintain consistency with Python '**' is used instead of '^'. <lang python>from math import log as ln from math import sqrt, log, exp, sin, cos, tan, pi, e
""" >>> # EXAMPLE USAGE >>> result = rpn_to_infix('3 4 2 * 1 -5 - ln 2 3 ** ** / +', VERBOSE=True) TOKEN STACK 3 ['3'] 4 ['3', '4'] 2 ['3', '4', '2']
- ['3', Node('2','*','4')]
1 ['3', Node('2','*','4'), '1'] -5 ['3', Node('2','*','4'), '1', '-5'] - ['3', Node('2','*','4'), Node('-5','-','1')] ln ['3', Node('2','*','4'), Node(Node('-5','-','1'),'ln',None)] 2 ['3', Node('2','*','4'), Node(Node('-5','-','1'),'ln',None), '2'] 3 ['3', Node('2','*','4'), Node(Node('-5','-','1'),'ln',None), '2', '3']
- ['3', Node('2','*','4'), Node(Node('-5','-','1'),'ln',None), Node('3','**','2')]
- ['3', Node('2','*','4'), Node(Node('3','**','2'),'**',Node(Node('-5','-','1'),'ln',None))]
/ ['3', Node(Node(Node('3','**','2'),'**',Node(Node('-5','-','1'),'ln',None)),'/',Node('2','*','4'))] + [Node(Node(Node(Node('3','**','2'),'**',Node(Node('-5','-','1'),'ln',None)),'/',Node('2','*','4')),'+','3')] >>> result """
prec_dict = {'abs':5, 'sqrt':5, 'exp':5, 'log':5, 'ln':5,
'sin':5, 'cos':5, 'tan':5,
'**':4, '*':3, '/':3, '+':2, '-':2}
assoc_dict = {'abs':0, 'sqrt':0, 'exp':0, 'log':0, 'ln':0,
'sin':0, 'cos':0, 'tan':0,
'**':1, '*':0, '/':0, '+':0, '-':0}
arity_dict = {'abs':1, 'sqrt':1, 'exp':1, 'log':1, 'ln':1,
'sin':1, 'cos':1, 'tan':1,
'**':2, '*':2, '/':2, '+':2, '-':2}
class Node:
def __init__(self,x,op,y=None):
global prec_dict,assoc_dict,arity_dict
self.precedence = prec_dict[op]
self.assocright = assoc_dict[op]
self.arity = arity_dict[op]
self.op = op
if not self.assocright and self > x and \
isinstance(x, Node) and self.arity == 2:
self.x = x.x
self.y = Node(x.y, x.op, y)
else:
self.x,self.y = x,y
def __str__(self):
# easy case, Node is unary
if self.y == None:
return '%s(%s)'%(self.op,str(self.x))
# determine left side string
str_y = str(self.y)
if self.y < self or \
(self.y == self and self.assocright) or \
(str_y[0] is '-' and self.assocright):
str_y = '(%s)'%str_y
# determine right side string and operator
str_x = str(self.x)
str_op = self.op
if self.op is '+' and not isinstance(self.x, Node) and str_x[0] is '-':
str_x = str_x[1:]
str_op = '-'
elif self.op is '-' and not isinstance(self.x, Node) and str_x[0] is '-':
str_x = str_x[1:]
str_op = '+'
elif self.x < self or \
(self.x == self and not self.assocright and \
getattr(self.x, 'op', 1) != getattr(self, 'op', 2)):
str_x = '(%s)'%str_x
return ' '.join([str_y, str_op, str_x])
def __repr__(self):
"""
>>> repr(Node('3','+','4')) == repr(eval(repr(Node('3','+','4'))))
True
"""
return 'Node(%s,%s,%s)'%(repr(self.x), repr(self.op), repr(self.y))
def __cmp__(self, other):
"""
polymorphic comparisons to determine precedence
>>> Node('3','+','4') < Node('6','*','7') < Node('3','**','4')
True
>>> Node('3','+','4') == Node('6','+','7')
True
>>> Node('3','+','4') == '-'
True
>>> Node('3','**','4') < '1'
True
"""
if isinstance(other, Node):
return cmp(self.precedence, other.precedence)
return cmp(self.precedence, prec_dict.get(other,9))
def rpn_to_infix(s, VERBOSE=False):
""" converts rpn notation to infix notation for string s
"^" are replaced with "**"
>>> rpn_to_infix('5 4 +')
'5 + 4'
>>> rpn_to_infix('5 -4 +')
'5 - 4'
>>> rpn_to_infix('5 -4 -')
'5 + 4'
>>> rpn_to_infix('5 -4.2 +')
'5 - 4.2'
>>> rpn_to_infix('-4 2 **')
'(-4) ** 2'
>>> rpn_to_infix('x y +')
'x + y'
>>> rpn_to_infix('x -y +')
'x - y'
>>> rpn_to_infix('5 4 3 2 ** ** **')
'5 ** 4 ** 3 ** 2'
>>> rpn_to_infix('5 6 ** 7 **')
'(5 ** 6) ** 7'
>>> rpn_to_infix('1 2 3 + -')
'1 - (2 + 3)'
>>> rpn_to_infix('4 3 2 + +')
'4 + 3 + 2'
>>> rpn_to_infix('5 4 3 2 + + +')
'5 + 4 + 3 + 2'
>>> rpn_to_infix('5 4 3 2 * * *')
'5 * 4 * 3 * 2'
>>> rpn_to_infix('5 4 3 2 + - +')
'5 + (4 - (3 + 2))'
>>> rpn_to_infix('3 4 5 * -')
'3 - 4 * 5'
>>> rpn_to_infix('3 4 5 - *')
'(3 - 4) * 5'
>>> rpn_to_infix('4 2 * 1 5 - +')
'4 * 2 + (1 - 5)'
>>> rpn_to_infix('4 2 * 1 5 - 2 ** /')
'4 * 2 / (1 - 5) ** 2'
>>> rpn_to_infix('3 4 2 * 1 5 - 2 3 ** ** / +')
'3 + 4 * 2 / (1 - 5) ** 2 ** 3'
>>> rpn_to_infix('1 2 + 3 4 + ** 5 6 + **')
'((1 + 2) ** (3 + 4)) ** (5 + 6)'
>>> rpn_to_infix('x sin')
'sin(x)'
>>> rpn_to_infix('5 4 3 2 + sqrt - +')
'5 + (4 - sqrt(3 + 2))'
>>> rpn_to_infix('5 4 3 2 + sqrt ln - +')
'5 + (4 - ln(sqrt(3 + 2)))'
>>> rpn_to_infix('5 sin 4 cos *')
'sin(5) * cos(4)'
>>> rpn_to_infix('5 4 cos * sin')
'sin(5 * cos(4))'
>>> rpn_to_infix('3 4 2 * 1 -5 - ln 2 3 ** ** / +')
'3 + 4 * 2 / ln(1 + 5) ** 2 ** 3'
"""
global prec_dict, arity_dict
if VERBOSE : print('TOKEN STACK')
stack=[]
for token in s.replace('^','**').split():
if token in prec_dict:
if arity_dict[token] == 1:
stack.append(Node(stack.pop(),token))
elif arity_dict[token] == 2:
stack.append(Node(stack.pop(),token,stack.pop()))
else:
stack.append(token)
# can't use \t in order to make global docstring pass doctest
if VERBOSE : print(token+' '*(7-len(token))+repr(stack))
return str(stack[0])
def rpn_eval(s):
""" computes the value of an rpn string
>>> rpn_eval('5 4 +') == eval(rpn_to_infix('5 4 +'))
True
>>> rpn_eval('-4 2 **') == eval(rpn_to_infix('-4 2 **'))
True
>>> round(rpn_eval('3 4 2 * 1 -5 - ln 2 3 ** ** / +'),7) == \
round(eval(rpn_to_infix('3 4 2 * 1 -5 - ln 2 3 ** ** / +')),7)
True
>>> round(rpn_eval('5 4 3 2 + sqrt ln - +'),7) == \
round(eval(rpn_to_infix('5 4 3 2 + sqrt ln - +')),7)
True
"""
global prec_dict, arity_dict
stack=[]
for token in s.replace('^','**').split():
if token in prec_dict:
if arity_dict[token] == 1:
stack.append(eval('%s(%s)'%(token,stack.pop())))
elif arity_dict[token] == 2:
x,y=stack.pop(),stack.pop()
stack.append(eval('(%s) %s %s'%(y,token,x)))
else:
stack.append(token)
return stack[0]
if __name__ == "__main__":
import doctest doctest.testmod()</lang>
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