Parsing/RPN to infix conversion: Difference between revisions

* 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

|- || align="center"

 

* Operator precedence and operator associativity is given in this table:

 

! operator !! [[wp:Order_of_operations|precedence]] !! [[wp:Operator_associativity|associativity]] !! operation

*   [http://www.rubyquiz.com/quiz148.html Postfix to infix]   from the RubyQuiz site.

<br><br>

 

=={{header|Ada}}==

Using the solution of the task [[stack]]:

type Priority is range 1..4;

type Infix is record

end;

end Convert;

The test program:

with Ada.Strings.Unbounded; use Ada.Strings.Unbounded;

with Ada.Text_IO; use Ada.Text_IO;

Put_Line (Convert ("1 2 + 3 4 + ^ 5 6 + ^"));

end RPN_to_Infix;

should produce the following output

<pre>

{{works with|ALGOL 68G|Any - tested with release 2.8.win32}}

Recursively parses the RPN string backwards to build a parse tree which is then printed.

# rpn to infix - parses an RPN expression and generates the equivalent #

# infix expression #

 

)

{{out}}<pre>

parsing expression from: 3 4 2 * 1 5 - 2 3 ^ ^ / +

1 2 + 3 4 + ^ 5 6 + ^: ( ( 1 + 2 ) ^ ( 3 + 4 ) ) ^ ( 5 + 6 )

</pre>

 

=={{header|AWK}}==

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.

 

 

BEGIN {

return s

}

 

Output:

Infix: (moon * (stars + mud)) ^ (fire * soup)

 

=={{header|C}}==

Takes RPN string from command line, string must be enclosed in double quotes. This is necessary since / and ^ are control characters for the command line. The second string, which can be any valid string, is optional and if supplied, the expression tree is printed out as it is built. The final expression is printed out in both cases.

#include<stdlib.h>

#include<string.h>

return 0;

}

Output, both final and traced outputs are shown:

<pre>

Final infix expression : (( 1 + 2 ) ^ ( 3 + 4 )) ^ ( 5 + 6 )

</pre>

=={{header|C++}}==

Very primitive implementation, doesn't use any parsing libraries which would shorten this greatly.

#include <iostream>

#include <stack>

}

}

Output :

<pre>

=={{header|Common Lisp}}==

Tested on ABCL.

;;;; Parsing/RPN to infix conversion

(defstruct (node (:print-function print-node)) opr infix)

(format t "~%Parsing:\"~A\"~%" expr)

(format t "RPN:\"~A\" INFIX:\"~A\"~%" expr (parse expr)))))

 

{{out}}

=={{header|D}}==

{{trans|Go}}

 

void parseRPN(in string e) {

"1 2 + 3 4 + ^ 5 6 + ^"])

parseRPN(test);

{{out}}

<pre>

 

===Alternative Version===

 

void rpmToInfix(in string str) @safe {

"3 4 2 * 1 5 - 2 3 ^ ^ / +".rpmToInfix;

"1 2 + 3 4 + ^ 5 6 + ^".rpmToInfix;

{{out}}

<pre>=================

-----------------

( ( 1 + 2 ) ^ ( 3 + 4 ) ) ^ ( 5 + 6 )</pre>

 

=={{header|EchoLisp}}==

For convenience, modularity, reusability, and the fun of it, we split the task into two parts. '''rpn->infix''' checks the rpn expression and builds an infix - lisp - tree (which can be the input of an infix calculator). '''infix->string''' takes a tree in input and builds the required string.

 

(require 'hash)

(string-delimiter "")

(when (right-par? node) (set! rhs (string-append "(" rhs ")")))

(string-append lhs " " node.op " " rhs))]))

{{out}}

<pre>

 

=={{header|F Sharp|F#}}==

| Num of int

| Add of ast * ast | Sub of ast * ast

Seq.iter (printf " %s") (infix 0 tree); printfn ""

0

Input is given via the command line.

Output includes the abstract syntax tree generated for the input.

=={{header|Go}}==

No error checking.

 

import (

}

fmt.Println("infix:", stack[0].expr)

Output:

<pre>

infix: ((1 + 2) ^ (3 + 4)) ^ (5 + 6)

</pre>

 

=={{header|Haskell}}==

This solution is a rough translation of the solution provided on RubyQuiz, as linked above.

 

data Expression = Const String | Exp Expression String Expression

 

 

leftAssoc :: Expression -> Bool

leftAssoc (Const _) = False

 

rightAssoc :: Expression -> Bool

rightAssoc (Const _) = False

 

 

1 2 + 3 4 + ^ 5 6 + ^

( ( 1 + 2 ) ^ ( 3 + 4 ) ) ^ ( 5 + 6 )

( 1 + 4 ) * ( 5 + 3 ) * 2 * 3

1 * 2 * 3 * 4

 

=={{header|Icon}} and {{header|Unicon}}==

every rpn := ![

"3 4 2 * 1 5 - 2 3 ^ ^ / +", # reqd

else x) || " "

return s || "]"

 

{{libheader|Icon Programming Library}}

Implementation:

 

 

ops=: ;:'+ - * / ^'

stack=: stack,_;y

smoutput stack

 

The stack structure has two elements for each stack entry: expression precedence and expression characters.

Required example:

 

pushing: 3

+-+-+

|2|3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3|

+-+-----------------------------+

 

=={{header|Java}}==

{{works with|Java|7}}

 

public static void main(String[] args) {

return expr.peek().ex;

}

 

Output:

Needs EcmaScript 6 support (e.g. Chrome).

 

/** a / b / c = (a / b) / c */

left: 0,

const realOup = rpnToTree(inp).toString();

console.log(realOup === oup ? "Correct!" : "Incorrect!");

 

Output:

read +, stack = [1 + 2 + 3]

Correct!</pre>

=={{header|Nim}}==

{{trans|Go}}

 

const nPrec = 9

 

for test in ["3 4 2 * 1 5 - 2 3 ^ ^ / +", "1 2 + 3 4 + ^ 5 6 + ^"]:

Output:

<pre>postfix: 3 4 2 * 1 5 - 2 3 ^ ^ / +

 

=={{header|Perl}}==

 

 

{{out}}

 

=={{header|Phix}}==

{{out}}

<pre>

=={{header|PicoLisp}}==

We maintain a stack of cons pairs, consisting of precedences and partial expressions. Numbers get a "highest" precedence of '9'.

(member Op '("*" "/" "+" "-")) )

 

(println Stack) )

(prog1 (cdr (pop 'Stack))

Test (note that the top-of-stack is in the left-most position):

Token Stack

3 ((9 . 3))

+ ((2 . "5 + 6") (4 . "(1 + 2) \^ (3 + 4)"))

^ ((4 . "((1 + 2) \^ (3 + 4)) \^ (5 + 6)"))

 

=={{header|PL/I}}==

/* Uses a push-down pop-up stack for the stack (instead of array) */

cvt: procedure options (main); /* 10 Sept. 2012 */

 

end cvt;

Outputs:

<pre>

 

=={{header|Python}}==

"""

print ("Input: ",strTest)

print ("Output:",strResult)

Output:

<pre>

=={{header|Racket}}==

{{trans|AWK}}

#lang racket

(require racket/dict)

(if (eq? +inf.0 p) (printf "[~a] " s) (printf "[~a {~a}] " s p)))

(newline))

 

Output:

"(moon * (stars + mud)) ^ (fire * soup)"

</pre>

 

=={{header|REXX}}==

{{trans|AWK}}

{{trans|Tcl}}

A Yen symbol &nbsp; '''¥''' &nbsp; was used instead of a &nbsp; '''9''' &nbsp; to make it apparenet that it's just a placeholder.

say "infix: " toInfix( "3 4 2 * 1 5 - 2 3 ^ ^ / +" )

say "infix: " toInfix( "Mond Sterne Schlamm + * Feur Suppe * ^" )

 

 

───────────────────────────────────────────────────────────────────────────────

RPN: 3 4 2 * 1 5 - 2 3 ^ ^ / +

Suppe ──► {3 Mond * ( Sterne + Schlamm)} {¥ Feur} {¥ Suppe}

* ──► {3 Mond * ( Sterne + Schlamm)} {3 Feur * Suppe}

infix: ( Mond * ( Sterne + Schlamm)) ^ ( Feur * Suppe)

</pre>

 

See [[Parsing/RPN/Ruby]]

 

infix = rpn.to_infix

outputs

<pre>for RPN expression: 3 4 2 * 1 5 - 2 3 ^ ^ / +

 

=={{header|Sidef}}==

pair[0] < prec ? "( #{pair[1]} )" : pair[1]

}

]

 

{{out}}

<pre>

 

=={{header|Tcl}}==

 

# Helpers

 

puts [rpn2infix {3 4 2 * 1 5 - 2 3 ^ ^ / +}]

Output:

<pre>

The <code>lisp-to-infix</code> filter then takes advantage of this non-associativity in minimizing the parentheses.

 

(defvar exp (intern "^"))

 

((a b . c) "*excess args*")

((a) (lisp-to-infix (rpn-to-lisp (string-to-rpn a))))

 

{{out}}

[ .. ]

infix: 3 + (1 - 1)</pre>

 

=={{header|zkl}}==

{{trans|Go}}

var opa=D(

}

println("infix:", stack[0][1])

{{out}}

<pre>