CDGLF: TMN to APL

Question

In this challenge you will remove one of my least favorite features, operator precedence from traditional math notation, to acheive the syntax of one of my favorite languages, APL. The APL subset we will be working with includes only a few functions and single digit numbers. (No arrays!)

Here is the grammar of the input

(in pegjs notation, with / representing disjunction and [] representing a set of possible characters. If you would like to test it out and validate inputs/outputs you can go to https://pegjs.org/online and paste it in the grammar textbox)

Expr = Addition;
Addition = Multiplication [+-] Addition / Multiplication;
Multiplication = Power [*/] Multiplication / Power;
Power = Floor '^' Expr / Floor;
Floor = '[' Expr ']' / '{' Expr '}' / Paren;
Paren = '(' Expr ')' / Digit;
Digit = [0-9];

• In descending order of precedence, the infix operators are ^ (exponentiation), * or /, and + or -.
• All the operators are left-associative except for ^. (0-1-2 is (0-1)-2 but 0^1^2 is 0^(1^2))
• There are no prefix operators.

And the output format:

Expr = Multiplication / Addition / Power / Floor;
Multiplication = Floor [*/] Expr;
Addition = Floor [+-] Expr;
Power = Floor '^' Expr;
Floor = '[' Expr / '{' Expr / Paren;
Paren = '(' Expr ')' / [0-9];

• { and [ are prefix and don't need a closing ] or }.
• All operators, prefix and infix, have the same precedence.
• All operators are right-associative, so 0o1o2 is the same as 0o(1o2) for any infix operator o.
• The infix operators are +-*/^ (^ is for exponentiation, and * and / are for multiplication and division respectively), and the prefix operators are { and [, which represent floor and ceiling respectively.

Note that these don't handle whitespace or negation and your program doesn't have to either.

Task

You are to take an Expr in the input format, assumed to be valid, and output an equivalent expression (Expr) in the APL-like output format. In this case, equivalent means structurally, so 9 is not a valid output for the input of 3*3. More specifically, the string that is outputted should have an Expr node where the input had an Expr, an Addition node where the input had Addition, etc. with the exception that in the output where an Expr node would be placed there may instead be a Paren node (this rule is recursive).

Examples:

These are not necessarily the only answers. Any amount of parentheses are allowed in the output.

input        output
1+1          1+1
2*2+1        (2*2)+1
3-5/2+1      (3-(5/2))+1
3-5/(2+1)    3-5/2+1
2*{2+1}      2*{2+1
5^4+1        (5^4)+1
{2+1}+1      ({2+1)+1
3^2^2        3^2^2
(3^2)^2      (3^2)^2

---

This is code-golf, shortest code per language wins. Your function or program takes a string from arguments or stdin and outputs through return or stdout etc. etc.

Answer 1

Factor, 187 bytes

: c ( x -- y ) concat "("")"surround ;
EBNF: A [=[
p=p("*"|"/")e=>[[c]]|e
e=f"^"e=>[[c]]|f
f=("["|"{")s("]"|"}")=>[[2 head c]]|"("s")"=>[[c]]|[0-9]=>[[1string]]
s=s("+"|"-")p=>[[c]]|p
]=]

Try it online! Does not work on TIO, but works on 0.98 stable.

Defines a named function A which takes a string, parses it, and returns an equivalent expression string in the output format.

Test:

{ "1+1" "2*2+1" "3-5/2+1" "3-5/(2+1)" "2*{2+1}"
  "5^4+1" "{2+1}+1" "3^2^2" "(3^2)^2" } [ A print ] each

Output:

(1+1)
((2*2)+1)
((3-(5/2))+1)
(3-(5/(((2+1)))))
(2*({(2+1)))
((5^4)+1)
(({(2+1))+1)
(3^(2^2))
((((3^2)))^2)

Since any number of parentheses are allowed, it is easiest to ignore the operator associativity of APL and parenthesize every single parsed node.

Factor comes with a PEG parser with EBNF syntax peg.ebnf. The grammar nodes s, p, e, and f stand for "sum", "product", "exp", and "floor" respectively. The last line is recognized as the "main" grammar, so I moved s to the last line.

It does support character classes like [+-], but it is converted to a single character (= integer), not a string, so it is more complicated to post-process. So I decided to simply use disjunction on string literals instead (except for digits).

=> [[ Factor code ]] defines how to post-process the grammar. For most of the nodes, it is simply "concatenate all parts and wrap in a pair of parens", which is defined as a named function c and reused throughout the code. For floor and ceiling, we only need to keep the opening {[ and the body, thus 2 head c.