Parsing/RPN to infix conversion: Difference between revisions
m
→{{header|RPL}}: typo
Alextretyak (talk | contribs) m (→{{header|11l}}) |
m (→{{header|RPL}}: typo) |
||
(9 intermediate revisions by 7 users not shown) | |||
Line 43:
{{trans|Java}}
<
F postfix_to_infix(postfix)
T Expression
String op, ex
prec = 3
F (String e1,
I o == ‘’
.ex = e1
Line 90 ⟶ 89:
print(‘Postfix : ’e)
print(‘Infix : ’postfix_to_infix(e))
print()</
{{out}}
Line 127 ⟶ 126:
=={{header|Ada}}==
Using the solution of the task [[stack]]:
<syntaxhighlight lang="ada">
type Priority is range 1..4;
type Infix is record
Line 210 ⟶ 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 225 ⟶ 224:
Put_Line (Convert ("1 2 + 3 4 + ^ 5 6 + ^"));
end RPN_to_Infix;
</syntaxhighlight>
should produce the following output
<pre>
Line 237 ⟶ 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 469 ⟶ 468:
)
</syntaxhighlight>
{{out}}<pre>
parsing expression from: 3 4 2 * 1 5 - 2 3 ^ ^ / +
Line 526 ⟶ 525:
=={{header|AutoHotkey}}==
{{works with|AutoHotkey_L}}
<
stack := {push: func("ObjInsert"), pop: func("ObjRemove")}
Line 571 ⟶ 570:
Space(n){
return n>0 ? A_Space Space(n-1) : ""
}</
;Output
<pre style="height:30ex;overflow:scroll;">TOKEN ACTION STACK (comma separated)
Line 596 ⟶ 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 698 ⟶ 697:
return s
}
</syntaxhighlight>
Output:
Line 746 ⟶ 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 872 ⟶ 871:
return 0;
}
</syntaxhighlight>
Output, both final and traced outputs are shown:
<pre>
Line 915 ⟶ 914:
=={{header|C sharp|C#}}==
{{trans|Java}}
<
using System.Collections.Generic;
using System.Linq;
Line 1,015 ⟶ 1,014:
}
}
}</
<pre>3 -> [3]
4 -> [3, 4]
Line 1,047 ⟶ 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,126 ⟶ 1,125:
}
}
</syntaxhighlight>
Output :
<pre>
Line 1,135 ⟶ 1,134:
=={{header|Common Lisp}}==
Tested on ABCL.
<
;;;; Parsing/RPN to infix conversion
(defstruct (node (:print-function print-node)) opr infix)
Line 1,195 ⟶ 1,194:
(format t "~%Parsing:\"~A\"~%" expr)
(format t "RPN:\"~A\" INFIX:\"~A\"~%" expr (parse expr)))))
</syntaxhighlight>
{{out}}
Line 1,294 ⟶ 1,293:
=={{header|D}}==
{{trans|Go}}
<
void parseRPN(in string e) {
Line 1,336 ⟶ 1,335:
"1 2 + 3 4 + ^ 5 6 + ^"])
parseRPN(test);
}</
{{out}}
<pre>
Line 1,428 ⟶ 1,427:
===Alternative Version===
{{trans|Raku}}
<
void rpmToInfix(in string str) @safe {
Line 1,462 ⟶ 1,461:
"3 4 2 * 1 5 - 2 3 ^ ^ / +".rpmToInfix;
"1 2 + 3 4 + ^ 5 6 + ^".rpmToInfix;
}</
{{out}}
<pre>=================
Line 1,500 ⟶ 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,561 ⟶ 1,560:
(when (right-par? node) (set! rhs (string-append "(" rhs ")")))
(string-append lhs " " node.op " " rhs))]))
</syntaxhighlight>
{{out}}
<pre>
Line 1,602 ⟶ 1,601:
=={{header|F Sharp|F#}}==
<
| Num of int
| Add of ast * ast | Sub of ast * ast
Line 1,650 ⟶ 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,662 ⟶ 1,661:
=={{header|Go}}==
No error checking.
<
import (
Line 1,724 ⟶ 1,723:
}
fmt.Println("infix:", stack[0].expr)
}</
Output:
<pre>
Line 1,817 ⟶ 1,816:
=={{header|Groovy}}==
{{trans|Java}}
<
static class Expression {
final static String ops = "-+/*^"
Line 1,875 ⟶ 1,874:
}
}
}</
{{out}}
<pre>Postfix : 3 4 2 * 1 5 - 2 3 ^ ^ / +
Line 1,912 ⟶ 1,911:
This solution is a rough translation of the solution provided on RubyQuiz, as linked above.
<syntaxhighlight lang="haskell">import Debug.Trace
data Expression = Const String | Exp Expression String Expression
------------- INFIX EXPRESSION FROM RPN STRING -----------
infixFromRPN :: String -> Expression
infixFromRPN = head . foldl buildExp [] . words
buildExp :: [Expression] -> String -> [Expression]
buildExp stack x
| (not . isOp) x =
let v = Const x : stack
in trace (show v) v
| otherwise =
let v = Exp l x r : rest
in trace (show v) v
where
r : l : rest = stack
isOp = (`elem` ["^", "*", "/", "+", "-"])
--------------------------- TEST -------------------------
main :: IO ()
main =
mapM_
( \s ->
putStr (s <> "\n-->\n")
>> (print . infixFromRPN)
s
>> putStrLn []
)
[ "3 4 2 * 1 5 - 2 3 ^ ^ / +",
"1 2 + 3 4 + ^ 5 6 + ^",
"1 4 + 5 3 + 2 3 * * *",
"1 2 * 3 4 * *",
"1 2 + 3 4 + +"
]
---------------------- SHOW INSTANCE ---------------------
instance Show Expression where
show (Const x) = x
show exp@(Exp l op r) = left <> " " <> op <> " " <> right
where
left
| leftNeedParen = "( " <> show l <> " )"
| otherwise = show l
right
| rightNeedParen = "( " <> show r <> " )"
| otherwise = show r
leftNeedParen =
(leftPrec < opPrec)
|| ((leftPrec == opPrec) && rightAssoc exp)
rightNeedParen =
(rightPrec < opPrec)
|| ((rightPrec == opPrec) && leftAssoc exp)
leftPrec = precedence l
rightPrec = precedence r
opPrec = precedence exp
leftAssoc :: Expression -> Bool
leftAssoc (Const _) = False
leftAssoc (Exp _ op _) = op `notElem` ["^", "*", "+"]
rightAssoc :: Expression -> Bool
rightAssoc (Const _) = False
rightAssoc (Exp _ op _) = op
precedence (Exp _ op _)
| op == "^" = 4
| op `elem` ["*", "/"] = 3
| op `elem` ["+", "-"] = 2
| otherwise = 0</syntaxhighlight>
{{Out}}
<pre>3 4 2 * 1 5 - 2 3 ^ ^ / +
-->
[3]
[4,3]
[2,4,3]
[4 * 2,3]
[1,4 * 2,3]
[5,1,4 * 2,3]
[1 - 5,4 * 2,3]
[2,1 - 5,4 * 2,3]
[3,2,1 - 5,4 * 2,3]
[2 ^ 3,1 - 5,4 * 2,3]
[( 1 - 5 ) ^ 2 ^ 3,4 * 2,3]
[4 * 2 / ( 1 - 5 ) ^ 2 ^ 3,3]
[3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3]
3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
1 2 + 3 4 + ^ 5 6 + ^
-->
[1]
[2,1]
[1 + 2]
[3,1 + 2]
[4,3,1 + 2]
[3 + 4,1 + 2]
[5,( 1 + 2 ) ^ ( 3 + 4 )]
[6,5,( 1 + 2 ) ^ ( 3 + 4 )]
[5 + 6,( 1 + 2 ) ^ ( 3 + 4 )]
[( ( 1 + 2 ) ^ ( 3 + 4 ) ) ^ ( 5 + 6 )]
( ( 1 + 2 ) ^ ( 3 + 4 ) ) ^ ( 5 + 6 )
1 4 + 5 3 + 2 3 * * *
-->
[1]
[4,1]
[1 + 4]
[5,1 + 4]
[3,5,1 + 4]
[5 + 3,1 + 4]
[2,5 + 3,1 + 4]
[3,2,5 + 3,1 + 4]
[2 * 3,5 + 3,1 + 4]
[( 5 + 3 ) * 2 * 3,1 + 4]
[( 1 + 4 ) * ( 5 + 3 ) * 2 * 3]
( 1 + 4 ) * ( 5 + 3 ) * 2 * 3
1 2 * 3 4 * *
-->
[1]
[2,1]
[1 * 2]
[3,1 * 2]
[4,3,1 * 2]
[3 * 4,1 * 2]
[1 * 2 * 3 * 4]
1 * 2 * 3 * 4
1 2 + 3 4 + +
-->
[1]
[2,1]
[1 + 2]
[3,1 + 2]
[4,3,1 + 2]
[3 + 4,1 + 2]
1 + 2 + 3 + 4</pre>
=={{header|Icon}} and {{header|Unicon}}==
<
every rpn := ![
"3 4 2 * 1 5 - 2 3 ^ ^ / +", # reqd
Line 2,030 ⟶ 2,113:
else x) || " "
return s || "]"
end</
{{libheader|Icon Programming Library}}
Line 2,065 ⟶ 2,148:
Implementation:
<
ops=: ;:'+ - * / ^'
Line 2,100 ⟶ 2,183:
stack=: stack,_;y
smoutput stack
)</
The stack structure has two elements for each stack entry: expression precedence and expression characters.
Line 2,106 ⟶ 2,189:
Required example:
<
pushing: 3
+-+-+
Line 2,207 ⟶ 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,274 ⟶ 2,357:
return expr.peek().ex;
}
}</
Output:
Line 2,311 ⟶ 2,394:
Needs EcmaScript 6 support (e.g. Chrome).
<
/** a / b / c = (a / b) / c */
left: 0,
Line 2,369 ⟶ 2,452:
const realOup = rpnToTree(inp).toString();
console.log(realOup === oup ? "Correct!" : "Incorrect!");
}</
Output:
Line 2,408 ⟶ 2,491:
Correct!</pre>
=={{header|jq}}==
{{works with|jq}}
'''Also works with gojq, the Go implementation of jq'''
This entry is based on the observation that the Parsing Expression Grammar (PEG)
for the reversed sequence of tokens of an RPN expression is essentially:
<pre>
E = operator operand operand
operand = number / E
operator = '+' | '-' | '*' | '^'
</pre>
it being understood that a subsequence [operator, operand1, operand2]
must finally be rendered as "(operand2 operator operand1)" because of
the reversal.
This PEG is so simple that only one of the functions from
[[:Category:Jq/peg.jq]], the jq library supporting PEG parsing, is
needed here, namely: `box/1`. It is therefore included in the
following listing, so there is no need to include peg.jq.
Notice also that the task requirements imply that the RPN string can
be readily tokenized using `splits/1`, as is done by `tokens/0`.
<syntaxhighlight lang=jq>
### PEG infrastructure
def box(E):
((.result = null) | E) as $e
| .remainder = $e.remainder
| .result += [$e.result] # the magic sauce
;
### Tokenize the RPN string.
# Input: a string representing an expression using RPN.
# Output: an array of corresponding tokens.
def tokens:
[splits("[ \n\r\t]+")]
| map(select(. != "")
| . as $in
| try tonumber catch $in);
### Parse the reversed array of tokens as produced by `tokens`.
# On entry, .remainder should be the reversed array.
# Output: {remainder, result}
def rrpn:
def found: .result += [.remainder[0]] | (.remainder |= .[1:]);
def nonempty: select(.remainder|length>0);
def check(predicate):
nonempty | select(.remainder[0] | predicate);
def recognize(predicate): check(predicate) | found;
def number : recognize(type=="number");
def operator: recognize(type=="string");
def operand : number // rrpn;
box(operator | operand | operand);
# Input: an array of tokens as produced by `tokens`
# Output: the infix equivalent expressed as a string.
def tokens2infix:
def infix:
if type != "array" then .
elif length == 1 then .[0] | infix
elif length == 3 then "(\(.[2] | infix) \(.[0]) \(.[1] | infix))"
else error
end;
{remainder: reverse} | rrpn | .result | infix;
# Input: an RPN string
# Output: the equivalent expression as a string using infix notation
def rpn2infix: tokens | tokens2infix;
def tests:
"3 4 2 * 1 5 - 2 3 ^ ^ / +",
"1 2 + 3 4 + ^ 5 6 + ^"
;
tests | "\"\(.)\" =>", rpn2infix, ""
</syntaxhighlight>
{{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))
</pre>
=={{header|Julia}}==
<
function parseRPNstring(rpns)
infix = []
Line 2,430 ⟶ 2,599:
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,451 ⟶ 2,620:
=={{header|Kotlin}}==
{{trans|Java}}
<
import java.util.Stack
Line 2,502 ⟶ 2,671:
println("Infix : ${postfixToInfix(e)}\n")
}
}</
{{out}}
Line 2,539 ⟶ 2,708:
=={{header|Lua}}==
The ouput contains more parenthesis then in strictly nessicary, but otherwise seems to read correctly
<
local out = {}
local cnt = 0
Line 2,623 ⟶ 2,792:
end
main()</
{{out}}
<pre>3 + ((4 * 2) / ((1 - 5) ^ (2 ^ 3)))
Line 2,629 ⟶ 2,798:
=={{header|M2000 Interpreter}}==
<syntaxhighlight lang="m2000 interpreter">
Module Rpn_2_Infix {
Rem Form 80,60
Line 2,686 ⟶ 2,855:
}
Rpn_2_Infix
</syntaxhighlight>
{{out}}
Line 2,768 ⟶ 2,937:
=={{header|Nim}}==
{{trans|Go}}
<
const nPrec = 9
Line 2,812 ⟶ 2,981:
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,901 ⟶ 3,070:
=={{header|Perl}}==
<
use warnings;
use feature 'say';
Line 2,930 ⟶ 3,099:
) { say } # track progress
say '=>' . substr($_,2,-2)."\n";
}</
{{out}}
<pre> ($2^$3)
Line 2,948 ⟶ 3,117:
=={{header|Phix}}==
<!--<syntaxhighlight lang="phix">(phixonline)-->
<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: #008080;">constant</span> <span style="color: #000000;">operators</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"^"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"*"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"/"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"+"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"-"</span><span style="color: #0000FF;">},</span>
<span style="color: #000000;">precedence</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span> <span style="color: #0000FF;">},</span>
<span style="color: #000000;">rassoc</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">'r'</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span> <span style="color: #0000FF;">,</span><span style="color: #008000;">'l'</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span> <span style="color: #0000FF;">,</span><span style="color: #008000;">'l'</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">parseRPN</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">expr</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">expected</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">stack</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span>
<span style="color: #000000;">ops</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #000000;">expr</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">lhs</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">rhs</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">lprec</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rprec</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Postfix input: %-32s%s"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">expr</span><span style="color: #0000FF;">,</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">show_workings</span><span style="color: #0000FF;">?</span><span style="color: #008000;">'\n'</span><span style="color: #0000FF;">:</span><span style="color: #008000;">' '</span><span style="color: #0000FF;">)})</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ops</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #008000;">"error"</span> <span style="color: #008080;">return</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ops</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">op</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ops</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">op</span><span style="color: #0000FF;">,</span><span style="color: #000000;">operators</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">stack</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">stack</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">op</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">else</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">stack</span><span style="color: #0000FF;">)<</span><span style="color: #000000;">2</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #008000;">"error"</span> <span style="color: #008080;">return</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">rprec</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rhs</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">stack</span><span style="color: #0000FF;">[$];</span> <span style="color: #000000;">stack</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">stack</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..$-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">lprec</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lhs</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">stack</span><span style="color: #0000FF;">[$]</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">prec</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">precedence</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">assoc</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rassoc</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">lprec</span><span style="color: #0000FF;"><</span><span style="color: #000000;">prec</span> <span style="color: #008080;">or</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">lprec</span><span style="color: #0000FF;">=</span><span style="color: #000000;">prec</span> <span style="color: #008080;">and</span> <span style="color: #000000;">assoc</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'r'</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">lhs</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"("</span><span style="color: #0000FF;">&</span><span style="color: #000000;">lhs</span><span style="color: #0000FF;">&</span><span style="color: #008000;">")"</span>
<span style="color: #008080;">end</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">rprec</span><span style="color: #0000FF;"><</span><span style="color: #000000;">prec</span> <span style="color: #008080;">or</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">rprec</span><span style="color: #0000FF;">=</span><span style="color: #000000;">prec</span> <span style="color: #008080;">and</span> <span style="color: #000000;">assoc</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'l'</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">rhs</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"("</span><span style="color: #0000FF;">&</span><span style="color: #000000;">rhs</span><span style="color: #0000FF;">&</span><span style="color: #008000;">")"</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">stack</span><span style="color: #0000FF;">[$]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">prec</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lhs</span><span style="color: #0000FF;">&</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">&</span><span style="color: #000000;">op</span><span style="color: #0000FF;">&</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">&</span><span style="color: #000000;">rhs</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">show_workings</span> <span style="color: #008080;">then</span>
<span style="color: #0000FF;">?{</span><span style="color: #000000;">op</span><span style="color: #0000FF;">,</span><span style="color: #000000;">stack</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">stack</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Infix result: %s [%s]\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">=</span><span style="color: #000000;">expected</span><span style="color: #0000FF;">?</span><span style="color: #008000;">"ok"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"**ERROR**"</span><span style="color: #0000FF;">)})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</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>
<span style="color: #000000;">show_workings</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
<span style="color: #000000;">parseRPN</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1 2 + 3 4 + ^ 5 6 + ^"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"((1 + 2) ^ (3 + 4)) ^ (5 + 6)"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">parseRPN</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1 2 + 3 4 + 5 6 + ^ ^"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"(1 + 2) ^ (3 + 4) ^ (5 + 6)"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">parseRPN</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"moon stars mud + * fire soup * ^"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"(moon * (stars + mud)) ^ (fire * soup)"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">parseRPN</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"3 4 ^ 2 9 ^ ^ 2 5 ^ ^"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"((3 ^ 4) ^ 2 ^ 9) ^ 2 ^ 5"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">parseRPN</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"5 6 * * + +"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"error"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">parseRPN</span><span style="color: #0000FF;">(</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"error"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">parseRPN</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1 4 + 5 3 + 2 3 * * *"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"(1 + 4) * (5 + 3) * 2 * 3"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">parseRPN</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1 2 * 3 4 * *"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"1 * 2 * 3 * 4"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">parseRPN</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1 2 + 3 4 + +"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"1 + 2 + 3 + 4"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">parseRPN</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1 2 + 3 4 + ^"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"(1 + 2) ^ (3 + 4)"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">parseRPN</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"5 6 ^ 7 ^"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"(5 ^ 6) ^ 7"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">parseRPN</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"5 4 3 2 ^ ^ ^"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"5 ^ 4 ^ 3 ^ 2"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">parseRPN</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1 2 3 + +"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"1 + 2 + 3"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">parseRPN</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1 2 + 3 +"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"1 + 2 + 3"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">parseRPN</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1 2 3 ^ ^"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"1 ^ 2 ^ 3"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">parseRPN</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1 2 ^ 3 ^"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"(1 ^ 2) ^ 3"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">parseRPN</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1 1 - 3 +"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"1 - 1 + 3"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">parseRPN</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"3 1 1 - +"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"3 + 1 - 1"</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- [txr says 3 + (1 - 1)]</span>
<span style="color: #000000;">parseRPN</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1 2 3 + -"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"1 - (2 + 3)"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">parseRPN</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"4 3 2 + +"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"4 + 3 + 2"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">parseRPN</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"5 4 3 2 + + +"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"5 + 4 + 3 + 2"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">parseRPN</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"5 4 3 2 * * *"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"5 * 4 * 3 * 2"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">parseRPN</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"5 4 3 2 + - +"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"5 + 4 - (3 + 2)"</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- [python says 5 + (4 - (3 + 2))]</span>
<span style="color: #000000;">parseRPN</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"3 4 5 * -"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"3 - 4 * 5"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">parseRPN</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"3 4 5 - *"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"3 * (4 - 5)"</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- [python says (3 - 4) * 5] [!!flagged!!]</span>
<span style="color: #000000;">parseRPN</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"3 4 - 5 *"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"(3 - 4) * 5"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">parseRPN</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"4 2 * 1 5 - +"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"4 * 2 + 1 - 5"</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- [python says 4 * 2 + (1 - 5)]</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>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 3,069 ⟶ 3,241:
=={{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,101 ⟶ 3,273:
(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,133 ⟶ 3,305:
+ ((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,191 ⟶ 3,363:
end cvt;
</syntaxhighlight>
Outputs:
<pre>
Line 3,236 ⟶ 3,408:
=={{header|Python}}==
<
"""
Line 3,355 ⟶ 3,527:
print ("Input: ",strTest)
print ("Output:",strResult)
</syntaxhighlight>
Output:
<pre>
Line 3,367 ⟶ 3,539:
=={{header|Racket}}==
{{trans|AWK}}
<
#lang racket
(require racket/dict)
Line 3,400 ⟶ 3,572:
(if (eq? +inf.0 p) (printf "[~a] " s) (printf "[~a {~a}] " s p)))
(newline))
</syntaxhighlight>
Output:
Line 3,445 ⟶ 3,617:
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku"
sub rpm-to-infix($string) {
Line 3,461 ⟶ 3,633:
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,477 ⟶ 3,649:
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,514 ⟶ 3,686:
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,559 ⟶ 3,731:
^ ──► {4 ( Mond * ( Sterne + Schlamm)) ^ ( Feur * Suppe)}
infix: ( Mond * ( Sterne + Schlamm)) ^ ( Feur * Suppe)
</pre>
=={{header|RPL}}==
It adds more parentheses than required, thus avoiding any ambiguity.
« '''IF''' DUP " " POS '''THEN''' " )" + "( " SWAP + '''END'''
» '<span style="color:blue">ADDPAR</span>' STO
« "}" + "{" SWAP + STR→ <span style="color:grey">@ tokenize</span>
→ postfix
« 1 postfix SIZE '''FOR''' j
postfix j GET →STR
'''IF''' "+-*/^" OVER POS '''THEN'''
ROT <span style="color:blue">ADDPAR</span> " " + SWAP + " " +
SWAP <span style="color:blue">ADDPAR</span> +
'''END'''
'''NEXT'''
» » '<span style="color:blue">→INFIX</span>' STO
"3 4 2 * 1 5 - 2 3 ^ ^ / +" <span style="color:blue">→INFIX</span>
"1 2 + 3 4 + ^ 5 6 + ^" <span style="color:blue">→INFIX</span>
{{out}}
<pre>
2: "3 + ( ( 4 * 2 ) / ( ( 1 - 5 ) ^ ( 2 ^ 3 ) ) )"
1: "( ( 1 + 2 ) ^ ( 3 + 4 ) ) ^ ( 5 + 6 )"
</pre>
Line 3,565 ⟶ 3,761:
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,589 ⟶ 3,785:
=={{header|Sidef}}==
{{trans|Raku}}
<
pair[0] < prec ? "( #{pair[1]} )" : pair[1]
}
Line 3,620 ⟶ 3,816:
]
tests.each { say rpm_to_infix(_).join(' ') }</
{{out}}
<pre>
Line 3,645 ⟶ 3,841:
=={{header|Tcl}}==
<
# Helpers
Line 3,683 ⟶ 3,879:
puts [rpn2infix {3 4 2 * 1 5 - 2 3 ^ ^ / +}]
puts [rpn2infix {1 2 + 3 4 + ^ 5 6 + ^}]</
Output:
<pre>
Line 3,722 ⟶ 3,918:
The <code>lisp-to-infix</code> filter then takes advantage of this non-associativity in minimizing the parentheses.
<
(defvar exp (intern "^"))
Line 3,784 ⟶ 3,980:
((a b . c) "*excess args*")
((a) (lisp-to-infix (rpn-to-lisp (string-to-rpn a))))
(else "*arg needed*"))))</
{{out}}
Line 3,876 ⟶ 4,072:
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<
Imports System.Text.RegularExpressions
Line 3,996 ⟶ 4,192:
End Sub
End Module</
{{out}}
<pre>Postfix : 3 4 2 * 1 5 - 2 3 ^ ^ / +
Line 4,032 ⟶ 4,228:
{{libheader|Wren-seq}}
{{libheader|Wren-pattern}}
<
import "./pattern" for Pattern
class Expression {
Line 4,085 ⟶ 4,281:
System.print("Postfix : %(e)")
System.print("Infix : %(postfixToInfix.call(e))\n")
}</
{{out}}
Line 4,122 ⟶ 4,318:
=={{header|zkl}}==
{{trans|Go}}
<
var opa=D(
Line 4,158 ⟶ 4,354:
}
println("infix:", stack[0][1])
}</
{{out}}
<pre>
|