Parsing/RPN to infix conversion: Difference between revisions
m
syntax highlighting fixup automation
m (→{{header|Phix}}: syntax coloured, replaced a \t to correct the spacing under pwa/p2js) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 43:
{{trans|Java}}
<
F postfix_to_infix(postfix)
Line 89:
print(‘Postfix : ’e)
print(‘Infix : ’postfix_to_infix(e))
print()</
{{out}}
Line 126:
=={{header|Ada}}==
Using the solution of the task [[stack]]:
<syntaxhighlight lang="ada">
type Priority is range 1..4;
type Infix is record
Line 209:
end;
end Convert;
</syntaxhighlight>
The test program:
<syntaxhighlight lang="ada">
with Ada.Strings.Unbounded; use Ada.Strings.Unbounded;
with Ada.Text_IO; use Ada.Text_IO;
Line 224:
Put_Line (Convert ("1 2 + 3 4 + ^ 5 6 + ^"));
end RPN_to_Infix;
</syntaxhighlight>
should produce the following output
<pre>
Line 236:
{{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 #
Line 468:
)
</syntaxhighlight>
{{out}}<pre>
parsing expression from: 3 4 2 * 1 5 - 2 3 ^ ^ / +
Line 525:
=={{header|AutoHotkey}}==
{{works with|AutoHotkey_L}}
<
stack := {push: func("ObjInsert"), pop: func("ObjRemove")}
Line 570:
Space(n){
return n>0 ? A_Space Space(n-1) : ""
}</
;Output
<pre style="height:30ex;overflow:scroll;">TOKEN ACTION STACK (comma separated)
Line 595:
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 {
Line 697:
return s
}
</syntaxhighlight>
Output:
Line 745:
=={{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.
<syntaxhighlight lang="c">
#include<stdlib.h>
#include<string.h>
Line 871:
return 0;
}
</syntaxhighlight>
Output, both final and traced outputs are shown:
<pre>
Line 914:
=={{header|C sharp|C#}}==
{{trans|Java}}
<
using System.Collections.Generic;
using System.Linq;
Line 1,014:
}
}
}</
<pre>3 -> [3]
4 -> [3, 4]
Line 1,046:
=={{header|C++}}==
Very primitive implementation, doesn't use any parsing libraries which would shorten this greatly.
<syntaxhighlight lang="cpp">
#include <iostream>
#include <stack>
Line 1,125:
}
}
</syntaxhighlight>
Output :
<pre>
Line 1,134:
=={{header|Common Lisp}}==
Tested on ABCL.
<
;;;; Parsing/RPN to infix conversion
(defstruct (node (:print-function print-node)) opr infix)
Line 1,194:
(format t "~%Parsing:\"~A\"~%" expr)
(format t "RPN:\"~A\" INFIX:\"~A\"~%" expr (parse expr)))))
</syntaxhighlight>
{{out}}
Line 1,293:
=={{header|D}}==
{{trans|Go}}
<
void parseRPN(in string e) {
Line 1,335:
"1 2 + 3 4 + ^ 5 6 + ^"])
parseRPN(test);
}</
{{out}}
<pre>
Line 1,427:
===Alternative Version===
{{trans|Raku}}
<
void rpmToInfix(in string str) @safe {
Line 1,461:
"3 4 2 * 1 5 - 2 3 ^ ^ / +".rpmToInfix;
"1 2 + 3 4 + ^ 5 6 + ^".rpmToInfix;
}</
{{out}}
<pre>=================
Line 1,499:
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 "")
Line 1,560:
(when (right-par? node) (set! rhs (string-append "(" rhs ")")))
(string-append lhs " " node.op " " rhs))]))
</syntaxhighlight>
{{out}}
<pre>
Line 1,601:
=={{header|F Sharp|F#}}==
<
| Num of int
| Add of ast * ast | Sub of ast * ast
Line 1,649:
Seq.iter (printf " %s") (infix 0 tree); printfn ""
0
</syntaxhighlight>
Input is given via the command line.
Output includes the abstract syntax tree generated for the input.
Line 1,661:
=={{header|Go}}==
No error checking.
<
import (
Line 1,723:
}
fmt.Println("infix:", stack[0].expr)
}</
Output:
<pre>
Line 1,816:
=={{header|Groovy}}==
{{trans|Java}}
<
static class Expression {
final static String ops = "-+/*^"
Line 1,874:
}
}
}</
{{out}}
<pre>Postfix : 3 4 2 * 1 5 - 2 3 ^ ^ / +
Line 1,911:
This solution is a rough translation of the solution provided on RubyQuiz, as linked above.
<
data Expression = Const String | Exp Expression String Expression
Line 1,985:
| op `elem` ["*", "/"] = 3
| op `elem` ["+", "-"] = 2
| otherwise = 0</
{{Out}}
<pre>3 4 2 * 1 5 - 2 3 ^ ^ / +
Line 2,056:
=={{header|Icon}} and {{header|Unicon}}==
<
every rpn := ![
"3 4 2 * 1 5 - 2 3 ^ ^ / +", # reqd
Line 2,113:
else x) || " "
return s || "]"
end</
{{libheader|Icon Programming Library}}
Line 2,148:
Implementation:
<
ops=: ;:'+ - * / ^'
Line 2,183:
stack=: stack,_;y
smoutput stack
)</
The stack structure has two elements for each stack entry: expression precedence and expression characters.
Line 2,189:
Required example:
<
pushing: 3
+-+-+
Line 2,290:
|2|3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3|
+-+-----------------------------+
3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3</
=={{header|Java}}==
{{works with|Java|7}}
<
public class PostfixToInfix {
Line 2,357:
return expr.peek().ex;
}
}</
Output:
Line 2,394:
Needs EcmaScript 6 support (e.g. Chrome).
<
/** a / b / c = (a / b) / c */
left: 0,
Line 2,452:
const realOup = rpnToTree(inp).toString();
console.log(realOup === oup ? "Correct!" : "Incorrect!");
}</
Output:
Line 2,492:
=={{header|Julia}}==
<
function parseRPNstring(rpns)
infix = []
Line 2,513:
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)
</syntaxhighlight>
{{output}}
<pre>
Line 2,534:
=={{header|Kotlin}}==
{{trans|Java}}
<
import java.util.Stack
Line 2,585:
println("Infix : ${postfixToInfix(e)}\n")
}
}</
{{out}}
Line 2,622:
=={{header|Lua}}==
The ouput contains more parenthesis then in strictly nessicary, but otherwise seems to read correctly
<
local out = {}
local cnt = 0
Line 2,706:
end
main()</
{{out}}
<pre>3 + ((4 * 2) / ((1 - 5) ^ (2 ^ 3)))
Line 2,712:
=={{header|M2000 Interpreter}}==
<syntaxhighlight lang="m2000 interpreter">
Module Rpn_2_Infix {
Rem Form 80,60
Line 2,769:
}
Rpn_2_Infix
</syntaxhighlight>
{{out}}
Line 2,851:
=={{header|Nim}}==
{{trans|Go}}
<
const nPrec = 9
Line 2,895:
for test in ["3 4 2 * 1 5 - 2 3 ^ ^ / +", "1 2 + 3 4 + ^ 5 6 + ^"]:
test.parseRPN</
Output:
<pre>postfix: 3 4 2 * 1 5 - 2 3 ^ ^ / +
Line 2,984:
=={{header|Perl}}==
<
use warnings;
use feature 'say';
Line 3,013:
) { say } # track progress
say '=>' . substr($_,2,-2)."\n";
}</
{{out}}
<pre> ($2^$3)
Line 3,031:
=={{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>
Line 3,104:
<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>
Line 3,155:
=={{header|PicoLisp}}==
We maintain a stack of cons pairs, consisting of precedences and partial expressions. Numbers get a "highest" precedence of '9'.
<
(member Op '("*" "/" "+" "-")) )
Line 3,187:
(println Stack) )
(prog1 (cdr (pop 'Stack))
(and Stack (quit "Garbage remained on stack")) ) ) )</
Test (note that the top-of-stack is in the left-most position):
<
Token Stack
3 ((9 . 3))
Line 3,219:
+ ((2 . "5 + 6") (4 . "(1 + 2) \^ (3 + 4)"))
^ ((4 . "((1 + 2) \^ (3 + 4)) \^ (5 + 6)"))
-> "((1 + 2) \^ (3 + 4)) \^ (5 + 6)"</
=={{header|PL/I}}==
<syntaxhighlight lang="pl/i">
/* Uses a push-down pop-up stack for the stack (instead of array) */
cvt: procedure options (main); /* 10 Sept. 2012 */
Line 3,277:
end cvt;
</syntaxhighlight>
Outputs:
<pre>
Line 3,322:
=={{header|Python}}==
<
"""
Line 3,441:
print ("Input: ",strTest)
print ("Output:",strResult)
</syntaxhighlight>
Output:
<pre>
Line 3,453:
=={{header|Racket}}==
{{trans|AWK}}
<
#lang racket
(require racket/dict)
Line 3,486:
(if (eq? +inf.0 p) (printf "[~a] " s) (printf "[~a {~a}] " s p)))
(newline))
</syntaxhighlight>
Output:
Line 3,531:
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku"
sub rpm-to-infix($string) {
Line 3,547:
say rpm-to-infix $_ for
'3 4 2 * 1 5 - 2 3 ^ ^ / +',
'1 2 + 3 4 + ^ 5 6 + ^';</
{{out}}
<pre>3 4 2 * 1 5 - 2 3 ^ ^ / +
Line 3,563:
The same reasoning was used for the ''operator associations'' (the left ◄ and right ► arrow symbols).
<
showAction = 1 /* 0 if no showActions wanted. */
# = 0 /*initialize stack pointer to 0 (zero).*/
Line 3,600:
end /*N*/
return space( substr( pop(), 2) )</
{{out|output|text= when using the default inputs: [Output is very similar to AWK's output.]}}
<pre>
Line 3,651:
See [[Parsing/RPN/Ruby]]
<
infix = rpn.to_infix
ruby = rpn.to_ruby</
outputs
<pre>for RPN expression: 3 4 2 * 1 5 - 2 3 ^ ^ / +
Line 3,675:
=={{header|Sidef}}==
{{trans|Raku}}
<
pair[0] < prec ? "( #{pair[1]} )" : pair[1]
}
Line 3,706:
]
tests.each { say rpm_to_infix(_).join(' ') }</
{{out}}
<pre>
Line 3,731:
=={{header|Tcl}}==
<
# Helpers
Line 3,769:
puts [rpn2infix {3 4 2 * 1 5 - 2 3 ^ ^ / +}]
puts [rpn2infix {1 2 + 3 4 + ^ 5 6 + ^}]</
Output:
<pre>
Line 3,808:
The <code>lisp-to-infix</code> filter then takes advantage of this non-associativity in minimizing the parentheses.
<
(defvar exp (intern "^"))
Line 3,870:
((a b . c) "*excess args*")
((a) (lisp-to-infix (rpn-to-lisp (string-to-rpn a))))
(else "*arg needed*"))))</
{{out}}
Line 3,962:
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<
Imports System.Text.RegularExpressions
Line 4,082:
End Sub
End Module</
{{out}}
<pre>Postfix : 3 4 2 * 1 5 - 2 3 ^ ^ / +
Line 4,118:
{{libheader|Wren-seq}}
{{libheader|Wren-pattern}}
<
import "/pattern" for Pattern
Line 4,171:
System.print("Postfix : %(e)")
System.print("Infix : %(postfixToInfix.call(e))\n")
}</
{{out}}
Line 4,208:
=={{header|zkl}}==
{{trans|Go}}
<
var opa=D(
Line 4,244:
}
println("infix:", stack[0][1])
}</
{{out}}
<pre>
|