Parsing/RPN to infix conversion: Difference between revisions

{{trans|Java}}

 

 

F postfix_to_infix(postfix)

print(‘Postfix : ’e)

print(‘Infix : ’postfix_to_infix(e))

 

{{out}}

=={{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 ^ ^ / +

=={{header|AutoHotkey}}==

{{works with|AutoHotkey_L}}

 

stack := {push: func("ObjInsert"), pop: func("ObjRemove")}

Space(n){

return n>0 ? A_Space Space(n-1) : ""

;Output

<pre style="height:30ex;overflow:scroll;">TOKEN ACTION STACK (comma separated)

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:

=={{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>

=={{header|C sharp|C#}}==

{{trans|Java}}

using System.Collections.Generic;

using System.Linq;

}

}

<pre>3 -> [3]

4 -> [3, 4]

=={{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===

{{trans|Raku}}

 

void rpmToInfix(in string str) @safe {

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

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

{{out}}

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

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>

=={{header|Groovy}}==

{{trans|Java}}

static class Expression {

final static String ops = "-+/*^"

}

}

{{out}}

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

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

 

 

data Expression = Const String | Exp Expression String Expression

| op `elem` ["*", "/"] = 3

| op `elem` ["+", "-"] = 2

{{Out}}

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

 

=={{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 class PostfixToInfix {

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:

 

=={{header|Julia}}==

function parseRPNstring(rpns)

infix = []

println("The final infix result: ", parseRPNstring("3 4 2 * 1 5 - 2 3 ^ ^ / +") |> unany, "\n")

println("The final infix result: ", parseRPNstring("1 2 + 3 4 + ^ 5 6 + ^") |> unany)

{{output}}

<pre>

=={{header|Kotlin}}==

{{trans|Java}}

 

import java.util.Stack

println("Infix : ${postfixToInfix(e)}\n")

}

 

{{out}}

=={{header|Lua}}==

The ouput contains more parenthesis then in strictly nessicary, but otherwise seems to read correctly

local out = {}

local cnt = 0

end

 

{{out}}

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

 

=={{header|M2000 Interpreter}}==

Module Rpn_2_Infix {

Rem Form 80,60

}

Rpn_2_Infix

 

{{out}}

=={{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}}==

use warnings;

use feature 'say';

) { say } # track progress

say '=>' . substr($_,2,-2)."\n";

{{out}}

<pre> ($2^$3)

 

=={{header|Phix}}==

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #004080;">bool</span> <span style="color: #000000;">show_workings</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>

<span style="color: #000000;">parseRPN</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"4 2 * 1 5 - 2 ^ /"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"4 * 2 / (1 - 5) ^ 2"</span><span style="color: #0000FF;">)</span>

<span style="color: #000000;">parseRPN</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"3 4 2 * 1 5 - 2 3 ^ ^ / +"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"3 + 4 * 2 / (1 - 5) ^ 2 ^ 3"</span><span style="color: #0000FF;">)</span>

{{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:

=={{header|Raku}}==

(formerly Perl 6)

 

sub rpm-to-infix($string) {

say rpm-to-infix $_ for

'3 4 2 * 1 5 - 2 3 ^ ^ / +',

{{out}}

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

 

The same reasoning was used for the ''operator associations'' &nbsp; (the left &nbsp; ◄ &nbsp; and right &nbsp; ► &nbsp; arrow symbols).

showAction = 1 /* 0 if no showActions wanted. */

# = 0 /*initialize stack pointer to 0 (zero).*/

end /*N*/

 

{{out|output|text=&nbsp; when using the default inputs: &nbsp; &nbsp; &nbsp; [Output is very similar to AWK's output.]}}

<pre>

See [[Parsing/RPN/Ruby]]

 

infix = rpn.to_infix

outputs

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

=={{header|Sidef}}==

{{trans|Raku}}

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}}

=={{header|Visual Basic .NET}}==

{{trans|C#}}

 

Imports System.Text.RegularExpressions

End Sub

 

{{out}}

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

{{libheader|Wren-seq}}

{{libheader|Wren-pattern}}

import "/pattern" for Pattern

 

System.print("Postfix : %(e)")

System.print("Infix : %(postfixToInfix.call(e))\n")

 

{{out}}

=={{header|zkl}}==

{{trans|Go}}

var opa=D(

}

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

{{out}}

<pre>