Parsing/RPN to infix conversion: Difference between revisions
m (→{{header|AWK}}: Oops. Forgot to exit program, which might be needed on some old versions?) |
m (→{{header|AWK}}: Factored out tail() calls -- nobodies perfect.) |
||
| Line 190: | Line 190: | ||
push(VALPREC tok) |
push(VALPREC tok) |
||
} |
} |
||
else { |
else { |
||
b = pop() |
b = pop() |
||
bp = prec(b) |
bp = prec(b) |
||
b = tail(b) |
|||
a = pop() |
a = pop() |
||
ap = prec(a) |
ap = prec(a) |
||
a = tail(a) |
|||
tp = tokPrec(tok) |
tp = tokPrec(tok) |
||
ta = tokAssoc(tok) |
ta = tokAssoc(tok) |
||
if (ap < tp || (ap == tp && ta == RIGHT)) { |
if (ap < tp || (ap == tp && ta == RIGHT)) { |
||
a = " |
a = "(" a ")" |
||
} |
} |
||
if (bp < tp || (bp == tp && ta == LEFT)) { |
if (bp < tp || (bp == tp && ta == LEFT)) { |
||
b = " |
b = "(" b ")" |
||
} |
} |
||
push(tp |
push(tp a " " tok " " b) |
||
} |
} |
||
print " " tok " -> " stackToStr() |
print " " tok " -> " stackToStr() |
||
Revision as of 04:01, 20 July 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 ^ 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)
AWK
Slavishly (mostly) follows TCL example, but instead of lists it uses strings. Except for the stack, which uses an array, of course.
The kludge is prepending the precedence on the front of the expressions stored on the stack. This shows up when the tail() function is used, and when 'x' is prepended as a placeholder when adding parenthesis.
<lang awk>#!/usr/bin/awk -f
BEGIN {
initStack()
initOpers()
print "Infix: " toInfix("3 4 2 * 1 5 - 2 3 ^ ^ / +")
print ""
print "Infix: " toInfix("1 2 + 3 4 + ^ 5 6 + ^")
print ""
print "Infix: " toInfix("moon stars mud + * fire soup * ^")
exit
}
function initStack() {
delete stack stackPtr = 0
}
function initOpers() {
VALPREC = "9" LEFT = "l" RIGHT = "r" operToks = "+" "-" "/" "*" "^" operPrec = "2" "2" "3" "3" "4" operAssoc = LEFT LEFT LEFT LEFT RIGHT
}
function toInfix(rpn, t, toks, tok, a, ap, b, bp, tp, ta) {
print "Postfix: " rpn
split(rpn, toks, / +/)
for (t = 1; t <= length(toks); t++) {
tok = toks[t]
if (!isOper(tok)) {
push(VALPREC tok)
}
else {
b = pop()
bp = prec(b)
b = tail(b)
a = pop()
ap = prec(a)
a = tail(a)
tp = tokPrec(tok)
ta = tokAssoc(tok)
if (ap < tp || (ap == tp && ta == RIGHT)) {
a = "(" a ")"
}
if (bp < tp || (bp == tp && ta == LEFT)) {
b = "(" b ")"
}
push(tp a " " tok " " b)
}
print " " tok " -> " stackToStr()
}
return tail(pop())
}
function push(expr) {
stack[stackPtr] = expr stackPtr++
}
function pop() {
stackPtr-- return stack[stackPtr]
}
function isOper(tok) {
return index(operToks, tok) != 0
}
function prec(expr) {
return substr(expr, 1, 1)
}
function tokPrec(tok) {
return substr(operPrec, operIdx(tok), 1)
}
function tokAssoc(tok) {
return substr(operAssoc, operIdx(tok), 1)
}
function operIdx(tok) {
return index(operToks, tok)
}
function tail(s) {
return substr(s, 2)
}
function stackToStr( s, i, t, p) {
s = ""
for (i = 0; i < stackPtr; i++) {
t = stack[i]
p = prec(t)
if (index(t, " ")) t = "{" tail(t) "}"
else t = tail(t)
s = s "{" p " " t "} "
}
return s
} </lang>
Output:
Postfix: 3 4 2 * 1 5 - 2 3 ^ ^ / +
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}}
Infix: 3 + 4 * 2 / (1 - 5) ^ 2 ^ 3
Postfix: 1 2 + 3 4 + ^ 5 6 + ^
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)}}
Infix: ((1 + 2) ^ (3 + 4)) ^ (5 + 6)
Postfix: moon stars mud + * fire soup * ^
moon -> {9 moon}
stars -> {9 moon} {9 stars}
mud -> {9 moon} {9 stars} {9 mud}
+ -> {9 moon} {2 {stars + mud}}
* -> {3 {moon * (stars + mud)}}
fire -> {3 {moon * (stars + mud)}} {9 fire}
soup -> {3 {moon * (stars + mud)}} {9 fire} {9 soup}
* -> {3 {moon * (stars + mud)}} {3 {fire * soup}}
^ -> {4 {(moon * (stars + mud)) ^ (fire * soup)}}
Infix: (moon * (stars + mud)) ^ (fire * soup)
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):
"""
Building an infix string that evaluates correctly is easy.
Building an infix string that looks pretty and evaluates
correctly requires more effort.
"""
# 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