Parsing/RPN to infix conversion: Difference between revisions
→{{header|Phix}}
m (added whitespace before the TOC (table of contents), added a ;Task: (bold) header, added other whitespace and highlighting to the task's preamble.) |
|||
Line 2,117:
-----------------
( ( 1 + 2 ) ^ ( 3 + 4 ) ) ^ ( 5 + 6 )</pre>
=={{header|Phix}}==
<lang Phix>integer show_workings = 1
constant operators = {"^","*","/","+","-"},
precedence = { 4, 3, 3, 2, 2 },
rassoc = {'r', 0 ,'l', 0 ,'l'}
procedure parseRPN(string expr, string expected)
sequence stack = {}
sequence ops = split(expr)
string lhs, rhs
integer lprec,rprec
printf(1,"Postfix input: %-30s%s", {expr,iff(show_workings?'\n':'\t')})
if length(ops)=0 then ?"error" return end if
for i=1 to length(ops) do
string op = ops[i]
integer k = find(op,operators)
if k=0 then
stack = append(stack,{9,op})
else
if length(stack)<2 then ?"error" return end if
{rprec,rhs} = stack[$]; stack = stack[1..$-1]
{lprec,lhs} = stack[$]
integer prec = precedence[k]
integer assoc = rassoc[k]
if lprec<prec or (lprec=prec and assoc='r') then
lhs = "("&lhs&")"
end if
if rprec<prec or (rprec=prec and assoc='l') then
rhs = "("&rhs&")"
end if
stack[$] = {prec,lhs&" "&op&" "&rhs}
end if
if show_workings then
?{op,stack}
end if
end for
string res = stack[1][2]
printf(1,"Infix result: %s [%s]\n", {res,iff(res=expected?"ok","**ERROR**")})
end procedure
parseRPN("3 4 2 * 1 5 - 2 3 ^ ^ / +","3 + 4 * 2 / (1 - 5) ^ 2 ^ 3")
show_workings = 0
parseRPN("1 2 + 3 4 + ^ 5 6 + ^","((1 + 2) ^ (3 + 4)) ^ (5 + 6)")
parseRPN("1 2 + 3 4 + 5 6 + ^ ^","(1 + 2) ^ (3 + 4) ^ (5 + 6)")
parseRPN("moon stars mud + * fire soup * ^","(moon * (stars + mud)) ^ (fire * soup)")
parseRPN("3 4 ^ 2 9 ^ ^ 2 5 ^ ^","((3 ^ 4) ^ 2 ^ 9) ^ 2 ^ 5")
parseRPN("5 6 * * + +","error")
parseRPN("","error")
parseRPN("1 4 + 5 3 + 2 3 * * *","(1 + 4) * (5 + 3) * 2 * 3")
parseRPN("1 2 * 3 4 * *","1 * 2 * 3 * 4")
parseRPN("1 2 + 3 4 + +","1 + 2 + 3 + 4")
parseRPN("1 2 + 3 4 + ^","(1 + 2) ^ (3 + 4)")
parseRPN("5 6 ^ 7 ^","(5 ^ 6) ^ 7")
parseRPN("5 4 3 2 ^ ^ ^","5 ^ 4 ^ 3 ^ 2")
parseRPN("1 2 3 + +","1 + 2 + 3")
parseRPN("1 2 + 3 +","1 + 2 + 3")
parseRPN("1 2 3 ^ ^","1 ^ 2 ^ 3")
parseRPN("1 2 ^ 3 ^","(1 ^ 2) ^ 3")
parseRPN("1 1 - 3 +","1 - 1 + 3")
parseRPN("3 1 1 - +","3 + 1 - 1") -- [txr says 3 + (1 - 1)]
parseRPN("1 2 3 + -","1 - (2 + 3)")
parseRPN("4 3 2 + +","4 + 3 + 2")
parseRPN("5 4 3 2 + + +","5 + 4 + 3 + 2")
parseRPN("5 4 3 2 * * *","5 * 4 * 3 * 2")
parseRPN("5 4 3 2 + - +","5 + 4 - (3 + 2)") -- [python says 5 + (4 - (3 + 2))]
parseRPN("3 4 5 * -","3 - 4 * 5")
parseRPN("3 4 5 - *","3 * (4 - 5)") -- [python says (3 - 4) * 5] [!!flagged!!]
parseRPN("3 4 - 5 *","(3 - 4) * 5")
parseRPN("4 2 * 1 5 - +","4 * 2 + 1 - 5") -- [python says 4 * 2 + (1 - 5)]
parseRPN("4 2 * 1 5 - 2 ^ /","4 * 2 / (1 - 5) ^ 2")
parseRPN("3 4 2 * 1 5 - 2 3 ^ ^ / +","3 + 4 * 2 / (1 - 5) ^ 2 ^ 3")</lang>
{{out}}
<pre>
Postfix input: 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 result: 3 + 4 * 2 / (1 - 5) ^ 2 ^ 3 [ok]
Postfix input: 1 2 + 3 4 + ^ 5 6 + ^ Infix result: ((1 + 2) ^ (3 + 4)) ^ (5 + 6) [ok]
Postfix input: 1 2 + 3 4 + 5 6 + ^ ^ Infix result: (1 + 2) ^ (3 + 4) ^ (5 + 6) [ok]
Postfix input: moon stars mud + * fire soup * ^ Infix result: (moon * (stars + mud)) ^ (fire * soup) [ok]
Postfix input: 3 4 ^ 2 9 ^ ^ 2 5 ^ ^ Infix result: ((3 ^ 4) ^ 2 ^ 9) ^ 2 ^ 5 [ok]
Postfix input: 5 6 * * + + "error"
Postfix input: "error"
Postfix input: 1 4 + 5 3 + 2 3 * * * Infix result: (1 + 4) * (5 + 3) * 2 * 3 [ok]
Postfix input: 1 2 * 3 4 * * Infix result: 1 * 2 * 3 * 4 [ok]
Postfix input: 1 2 + 3 4 + + Infix result: 1 + 2 + 3 + 4 [ok]
Postfix input: 1 2 + 3 4 + ^ Infix result: (1 + 2) ^ (3 + 4) [ok]
Postfix input: 5 6 ^ 7 ^ Infix result: (5 ^ 6) ^ 7 [ok]
Postfix input: 5 4 3 2 ^ ^ ^ Infix result: 5 ^ 4 ^ 3 ^ 2 [ok]
Postfix input: 1 2 3 + + Infix result: 1 + 2 + 3 [ok]
Postfix input: 1 2 + 3 + Infix result: 1 + 2 + 3 [ok]
Postfix input: 1 2 3 ^ ^ Infix result: 1 ^ 2 ^ 3 [ok]
Postfix input: 1 2 ^ 3 ^ Infix result: (1 ^ 2) ^ 3 [ok]
Postfix input: 1 1 - 3 + Infix result: 1 - 1 + 3 [ok]
Postfix input: 3 1 1 - + Infix result: 3 + 1 - 1 [ok]
Postfix input: 1 2 3 + - Infix result: 1 - (2 + 3) [ok]
Postfix input: 4 3 2 + + Infix result: 4 + 3 + 2 [ok]
Postfix input: 5 4 3 2 + + + Infix result: 5 + 4 + 3 + 2 [ok]
Postfix input: 5 4 3 2 * * * Infix result: 5 * 4 * 3 * 2 [ok]
Postfix input: 5 4 3 2 + - + Infix result: 5 + 4 - (3 + 2) [ok]
Postfix input: 3 4 5 * - Infix result: 3 - 4 * 5 [ok]
Postfix input: 3 4 5 - * Infix result: 3 * (4 - 5) [ok]
Postfix input: 3 4 - 5 * Infix result: (3 - 4) * 5 [ok]
Postfix input: 4 2 * 1 5 - + Infix result: 4 * 2 + 1 - 5 [ok]
Postfix input: 4 2 * 1 5 - 2 ^ / Infix result: 4 * 2 / (1 - 5) ^ 2 [ok]
Postfix input: 3 4 2 * 1 5 - 2 3 ^ ^ / + Infix result: 3 + 4 * 2 / (1 - 5) ^ 2 ^ 3 [ok]
</pre>
=={{header|PicoLisp}}==
Line 2,185 ⟶ 2,305:
^ ((4 . "((1 + 2) \^ (3 + 4)) \^ (5 + 6)"))
-> "((1 + 2) \^ (3 + 4)) \^ (5 + 6)"</lang>
=={{header|PL/I}}==
| |||