Parsing/RPN to infix conversion: Difference between revisions
→{{header|jq}}
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
|||
Line 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}}==
<syntaxhighlight lang="julia">
| |||