[Question]
  [
Infix notation is a method of printing mathematical expressions where each operator sits between its two arguments, such as \$ \left(5 \cdot 4\right) + 3 \$.
Prefix notation is a method of printing expressions where operators sit before their arguments. The equivalent of the above is `+*543`. It's a bit harder to understand than infix, but here's a sort of explanation:
```
+*543 # Expression
+     # Adding
 *54  # Expression
 *    # The product of
  5   # 5 and
   4  # 4
    3 # And 3
```
Your challenge is to, given an expression in prefix, convert it to infix notation.
You may take input as a string, character array, array of charcodes, etc.
The input will contain lowercase letters and digits, and can be assumed to be a valid expression - that is, each operator (letter) has exactly two operands and there is only one value left at the end
The output should be a valid expression in infix - that is, it should be an expression in the following recursive grammar:
```
digit := 0-9
operator := a-z
expression := digit | (expression operator expression)
```
That is, each expression should be a digit, or two expressions joined by an operator and wrapped in parentheses for unambiguity.
## Example
Note: Spaces are for clarity and are optional in the input and output.
```
Expression: x 3 u f 4 3 h 5 9
You could read this as x(3, u(f(4, 3), h(5, 9))) or something.
The x is taking 3 and the expression with a u as operands:
Result: (3 x ...)
Expression: u f 4 3 h 5 9
The u is taking the expression with a f and the expression with an h as operands.
Result: (3 x ((...) u (...)))
Expression: f 4 3
The f is taking 4 and 3 as operands.
Result: (3 x ((4 f 3) u (...)))
Expression: h 5 9
The h is taking 5 and 9 as operands.
Expression: (3 x ((4 f 3) u (5 h 9)))
And that's the result! Spaces are optional.
```
## Testcases
As usual, these are manually created, so comment if I've stuffed these up.
```
a34 -> (3a4)
ba567 -> ((5a6)b7)
cba1234 -> (((1a2)b3)c4)
a1b23 -> (1a(2b3))
a1fcb46d4e95ig6h42kj32l68 -> (1a(((4b6)c(4d(9e5)))f((6g(4h2))i((3j2)k(6l8)))))
```
Standard [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'") rules apply.
  
[Answer]
# [Python 3.8 (pre-release)](https://docs.python.org/3.8/), 61 bytes
```
f=lambda S:(s:=next(S:=iter(S)))[:s<"a"]or"("+f(S)+s+f(S)+")"
```
[Try it online!](https://tio.run/##NY5BboMwEEX3nMKa1YySVsI2DqF1LwG7NAsbcHBCAYEXLZenQJvZjOb9p9EffkLTdyIdxmVxujVftjIsz3DKdFd/B8wz7UM9Yk5El2x6BwPXfgSEg1vZYfpbQLAUGgCMkOzlg6EwkiJrEnXaT0yMInuiqLQm5v8OYmw4WUHl6prYcrHj2CBf4YZcaaWqZH1O/E01kj/ugrcqfWqI0ioqUVZ4rpO1oENUN5QNJ/KI4s7pgapNaZu1XFToS3idhtYHhO0JEHP9yALzHSuewWcHdI027o/9nmSzdujpbRh9F3A@zlr3FC2/ "Python 3.8 (pre-release) ‚Äì Try It Online")
This does the conversion in a single linear pass over the input. The tree structure is captured by a recursive scheme where each branch corresponds to an instance of the function. The function logic is then as simple as: Read the next character and return it if it is a numeral. Else store it, then output opening braces call yourself for the first operand, output the stored infix call yourself for the second operand and add the closing braces.
To keep track of the position within the input string across all the recursive function calls we convert the input to an iterator. Applying `iter` to an iterator returns the object itself, so it does no harm doing it multiple times. As all copies of the recursive function use the self-same single instance of the iterator the bookkeeping becomes trivial.
[Answer]
# TypeScript Types, ~~234~~ 206 bytes
Saved 28 bytes thanks to tjjfvi!
```
//@ts-ignore
type F<E>=E extends`${infer H}${infer T}`?(H extends`${number}`?[H,T]:F<T>extends[infer I,infer U]?F<U>extends[infer J,infer V]?[`(${I}${H}${J})`,V]:0:0):0
type G<E>=F<E>extends[infer H,""]?H:0
```
[Try it online!](https://www.typescriptlang.org/play?#code/PTACBcGcFoEsHMB2B7ATgUwFDgJ4Ad0ACAMQB4BRAPgF5zD0APcdRAE0gAMASAb1kQBm6VIQASAX178hIgCriOAfgAUo+kxbtuPRAFcAtgCNhCxQG1RAGlkBdAFxlZlRszaQz04YQCSlzyIBVG0UyAOcNNw9BLwApP2iRADVgsw5lXm9JHgleGPEASg5LZLsABjL8sux8IgBxChoyKhdNd38xSwAiTuDRKswQCBgEFAxqgkIAYQALdABjAGtSAEF1V3ZCSHBUfnhLQgAhNdbN7d3KQmpCeuWLlrdDwkVCTuWAGzfCeGRkVgBCTqEOyEDgAeWmhFY6AAhqh9rwbpRxIRYJBCChwIRwLNNtD9ERoWjeAcFABuTDjIirK4zeZLTrQgDMABZOvtOspGdDmflOpQBsBCEKAHqKSmPGmzRakTqGaEAVgAbAB2NkvZTKeXQxX5QzK3n8kBCwii8WTS5TKX0uZygCMACYWWqORrbdD7brGfk5jy+QLjabcBMACIW2nShm2wyO53KN3Ke2GL0G-0isVBoh0SV0mXQ20CG3MxWsZnoACc8oQiumzPtCwAVoz7W9FQAOWPxjXMww6ubKZmsZRl9Dy-JjgQaxXwfvTD35WAaxn1j0LZSKt6tsdbv1GtNAA)
Thanks to [@tjjfvi](https://codegolf.stackexchange.com/users/87606/tjjfvi) for helping me get started with abusing TypeScript's surprisingly powerful type system. This is pretty much the same approach as my Scala answer, just at compile time. At each step, `F` returns one expression and the remainder of the input. First it deconstructs the input into the first character `H` and the rest `T` using `E extends `${infer H}${infer T}`` . Then it checks if the first character of `E` is a digit (`H extends'0'|...|'9'`). If it is, it just returns that first character (a valid infix expression) and `T` in a list (or is it a tuple type?). Otherwise, it finds the next two expressions `I` and `J` and returns the infix expression `(IHJ)` along with the remaining text `V`. `G` exists simply to match on `F`'s output and return the valid expression, as the second part of the output of `F` is an empty string by the end.
[Answer]
# [JavaScript (Node.js)](https://nodejs.org), 49 bytes
```
s=>(i=0,g=(c=s[i++])=>c>=0?c:'('+g()+c+g()+')')()
```
[Try it online!](https://tio.run/##PY9BbsIwEEX3OYV3/qNARBzHQJHTVU9BkXCMEwwBIxxVSFXPniaodBYjzZunL/2T@TLR3v2tn1/DwQ2NHqKu4PVi1mpYHbc@TXekK1vpxbt94@BpC0rtc3PiBBp6F3trootMs31iCsnmFUNhJCW1KdXyeaI0iuolJbY2ufhzgNwIqguyo2vyWhRPnBuIEU6osbVUB@nWpW/VUYrzqRCdWr00QNaKLOQBa1cSUQOoFvIoiDxQnASdoboVTZPss/7uL6As3jrfg39eOWUXc8OD6Yo9XngK50Sb5L9Y1oT7h7FHYOtnzO1o8r8Txmy4xtC5rAstEMb@DTyNX62Zm7EwZvzQZvgF "JavaScript (Node.js) ‚Äì Try It Online")
[Answer]
# x86-16 machine code, ~~23~~ 21 bytes
```
00000000: ac3c 617c 0e50 b028 aae8 f4ff 58aa e8ef  .<a|.P.(....X...
00000010: ffb0 29aa c3                             ..)..
```
Listing:
```
        P2I:
AC          LODSB               ; AL = next char, SI++
3C 61       CMP  AL, 'a'        ; is alpha? 
7C 0E       JL   IS_ARG         ; if not, it's an argument
50          PUSH AX             ; save operator to stack 
B0 28       MOV  AL, '('        ; load left paren 
AA          STOSB               ; write to output 
E8 0100     CALL P2I            ; recursive call for next char 
58          POP  AX             ; restore operator from this call stack 
AA          STOSB               ; write to output 
E8 0100     CALL P2I            ; recursive call for next char 
B0 29       MOV  AL, ')'        ; load right paren
        IS_ARG:
AA          STOSB               ; write to output 
C3          RET                 ; return to caller
```
Input string at `[SI]`, output to `[DI]`.
[![enter image description here](https://i.stack.imgur.com/AeZn9.png)](https://i.stack.imgur.com/AeZn9.png)
[Answer]
# [Haskell](https://www.haskell.org/), 70 bytes
```
g(a:b)|a<'a'=([a],b)|(c,d)<-g b,(e,f)<-g d=('(':c++a:e++")",f)
f=fst.g
```
[Try it online!](https://tio.run/##Rcm9DoIwGIXh3av40qVtKCYURCXAFejkiAxfgQLyEyJ1894rSKLbc97T4NxVfW9tzTBS/I0xRZqwDHOxLFaIksduDUqwSugvy4RRRqPCcTCqHIdwshw7nejZ7Gs7YDtCAgNOV2B3A24K08vczBMMpD@TtZN/uIzANBjOISPoB0QAUXgIjysKhZ7cGnpK@ht0oYKwDKrzoa3DJpDdw5d9eCK5/QA "Haskell ‚Äì Try It Online")
[Answer]
# [R](https://www.r-project.org/), ~~96~~ ~~65~~ ~~72~~ 69 bytes
Or **[R](https://www.r-project.org/)>=4.1, 62 bytes** by replacing the word `function` with `\`.
*-many bytes by changing I/O to vector of char codes.*  
*-another some bytes thanks to [@Dominic van Essen](https://codegolf.stackexchange.com/users/95126/dominic-van-essen).*  
*+7 bytes costed converting from not-so-self-contained function to a program.*  
*-3 bytes thanks to [@Dominic van Essen](https://codegolf.stackexchange.com/users/95126/dominic-van-essen) - converting back to one (reusable) function.*
```
`/`=function(s,t=0)"if"((a=s[i<<-t*i+1])<58,a,c(40,s/1,a,s/1,41));i=9
```
[Try it online!](https://tio.run/##hZDNbsIwEITvfQqUXmbbIPAviYh7752eqkrYJgYDSiRieP3USJVoL80eVjva/WakvYy@727tJZlxu9iacO18in2HoUxmSUUMBWDN8BmbZp5e4iv7okZVpS095LIcFiyP9y4Z0Tqaeoxd2vQfKVT4McY1i03/3iUUVsiCiJ5n87cZhJX09O@5s0qvHgCU1eRWE5B3lvHfOQCznJwgP5VnmePiATILnrFJKHgn9U62tYp7fZD8dBT8rKs/RoB0mvLTdqhblTcB0HvIAyeKgDhyOkGfK7rX@A0 "R ‚Äì Try It Online")
Port of [@loopy walt's answer](https://codegolf.stackexchange.com/a/237581/55372).
**Explanation**
A function takes string `s` and `t` defaulting to `0` (for resetting global variable).  
The recursive function (named `/` overriding division) takes one character at a time (`a`) incrementing the global counter each time. If the character char code is less then 58, then it's a digit and needs to be returned as is. Otherwise, we surround the character with braces (char codes `40,41`) and recursive calls to our function (with `t=1` to keep `i` as is between calls).  
The code at the end initiates global counter `i` to a digit (`9` chosen for demonstration purposes).
---
Solution shorter for [R](https://www.r-project.org/)>=4.1:
### [R](https://www.r-project.org/), 74 bytes
Or **[R](https://www.r-project.org/)>=4.1, 60 bytes** by replacing two `function` occurrences with `\`s.
```
function(s,i=0,f=function(a=s[i<<-i+1])"if"(a<58,a,c(40,f(),a,f(),41)))f()
```
[Try it online!](https://tio.run/##hZDNbsJADITvfQoULmM1SN1fgpT03js9VT14lywsoI0ES18/LKgq7aXxwRpb840ln0Y/pK/@lLsxXJLPcUg417F7qUP3s@Du/BHbdhGfxSdVMVTg1jQ11x66GEFF3roWRFTEGFNeD@85NPhOx6UM6@EtZVSsdFV889nidQbFmp7@tTs2dvkAYNiSW05A3rGQv@8AgiU5RX7qHgsn1QMUDFmwSSh4p@1G9ysTt3an5WGv5NE2f4IA7SyVp22w6s39V7Bb6J0kioDaSzrAHhu61XgF "R ‚Äì Try It Online")
Same as above, but here `i` is "local" for the main function, but "global" for the recursive one.
[Answer]
# [Prolog (SWI)](http://www.swi-prolog.org), ~~95~~ 81 bytes
Haven't programmed in Prolog for a while, so this was a fun challenge to do.
Prologs ability to handle strings and atoms do not make it easy. Probably suboptimal, but here we go:
```
f(R,[H|T]):-T=[],H<97,R=[H];append(X,Y,T),f(C,X),f(D,Y),flatten([40,C,H,D,41],R).
```
Input and output are both codepoint lists.
[Try it online!](https://tio.run/##hY4/D4IwEMV3PgVxapPDCFT8P@GAkwlh0BBCChSskkKgRge/O1Y2opFb3uXe795d3VRlVRjtg3ddjnwIvVcQ4bUR7MIIvO1qAf4u9KINrWsmMnSCMwQYcuTC6SN7OCspqZRMoJDMwAUP9kDMCHw87eqG5fwZyyrmQjXoIEA/3iXW14amq2plw0URp1XG2t50Px2G3lTvsHY4GvAqCHSF/LgzoTaZ9Oa9lHiqaV9AQufO4j@SJtS0xnKomVj2GJKnCXEywlZzXjgXYt2utlU6y8HaGw "Prolog (SWI) ‚Äì Try It Online")
[Answer]
# [Retina](https://github.com/m-ender/retina/wiki/The-Language), 74 bytes
```
+`([a-z])((([a-z])|(?<-4>\d))*\d)((([a-z])|(?<-7>\d))*\d)
($2$U$1$5)
T`L`l
```
[Try it online!](https://tio.run/##K0otycxLNPz/XztBIzpRtypWU0MDyqjRsLfRNbGLSdHU1AISqOLmcHEuDRUjlVAVQxVTTa6QBJ@EnP//E41NuJISTc3MuZKTEg2NgLxEwyQjYyCZlpxkYpZikmppmplulmFilJ1lbJRjZgEA "Retina ‚Äì Try It Online") Link includes test cases. Explanation:
```
([a-z])((([a-z])|(?<-4>\d))*\d)((([a-z])|(?<-7>\d))*\d)
```
Match a letter followed by two prefix expressions. A prefix expression is readily identified as being a substring that contains exactly one more digit than letter.
```
($2$U$1$5)
```
Convert this letter to infix and upper case it to show that it has been converted.
```
+`
```
Keep making replacements until all of the letters have been upper cased.
```
T`L`l
```
Change all the letter back to lower case again.
[Answer]
# [Ruby](https://www.ruby-lang.org/), ~~62~~ ~~60~~ 54 bytes
```
->e,i=-1{(f=->c=e[i+=1]{c=~/\d/?c:?(+f[]+c+f[]+?)})[]}
```
Saved 6 more bytes by removing parenthesis and using ternary operator by the hint from Dingus.
[Try it online!](https://tio.run/##RY3BjoIwEIbvPsWEvcxE0VBK1U2qp30KlkNbilQJGoFkN8i@Ogsusj20zf/NN/@90d99IXv/YFdO@kGLmfQPRtrYLWWQtEb@bD7TzdG8H3GZxcnSPO8jdRQnXd8uADwVcg/kATwMFSdvNWZaRWI7pRgpQXo7EaNVwGYDMVCMdEjmZapAs3CigUI2sJlkRnORcruP3EnknF3OISvE7n8akWtBBnmKexsRUYYoTshzRuQQwzOjC4piR@MZtnZrq0wO6RUerrw19Qrs182a2qaPofFuq6aoQUIRP2kyZMNTTWCcUK6y4H1MEry1L3/tymr8daCbGk7XemB/2kw8aMrCVtXcI@f2hS3TRf8L "Ruby ‚Äì Try It Online")
[Answer]
# [Perl 5](https://www.perl.org/) -p, 51 bytes
```
s/(\D) (\S+) (\S+)/ ($2$1$3)/||s/.\b/ $&/ until/^ /
```
[Try it online!](https://tio.run/##K0gtyjH9/79YXyPGRVNBIyZYG0rqK2ioGKkYqhhr6tfUFOvrxSTpK6io6SuU5pVk5ujHKej//59obMKVlGhqZs6VnJRoaATkJRomGRkr0AMArUpLTjIxSzFJtTTNTDfLMDHKzjI2yjGz@JdfUJKZn1f8X7cAAA "Perl 5 ‚Äì Try It Online")
Uses regexp substitutions and treat the $\_ string as an array where the first element is the input, or what is left of it while processing, and the rest of the array elements is the working stack. Commands to see it's behavior on the last test case:
```
INP=a1fcb46d4e95ig6h42kj32l68      #which is the last test case
echo $INP|perl -plE'say,s/(\D) (\S+) (\S+)/ ($2$1$3)/||s/.\b/ $&/ until/^ /'
a1fcb46d4e95ig6h42kj32l68
a1fcb46d4e95ig6h42kj32l6 8
a1fcb46d4e95ig6h42kj32l 6 8
a1fcb46d4e95ig6h42kj32 (6l8)
a1fcb46d4e95ig6h42kj3 2 (6l8)
a1fcb46d4e95ig6h42kj 3 2 (6l8)
a1fcb46d4e95ig6h42k (3j2) (6l8)
a1fcb46d4e95ig6h42 ((3j2)k(6l8))
a1fcb46d4e95ig6h4 2 ((3j2)k(6l8))
a1fcb46d4e95ig6h 4 2 ((3j2)k(6l8))
a1fcb46d4e95ig6 (4h2) ((3j2)k(6l8))
a1fcb46d4e95ig 6 (4h2) ((3j2)k(6l8))
a1fcb46d4e95i (6g(4h2)) ((3j2)k(6l8))
a1fcb46d4e95 ((6g(4h2))i((3j2)k(6l8)))
a1fcb46d4e9 5 ((6g(4h2))i((3j2)k(6l8)))
a1fcb46d4e 9 5 ((6g(4h2))i((3j2)k(6l8)))
a1fcb46d4 (9e5) ((6g(4h2))i((3j2)k(6l8)))
a1fcb46d 4 (9e5) ((6g(4h2))i((3j2)k(6l8)))
a1fcb46 (4d(9e5)) ((6g(4h2))i((3j2)k(6l8)))
a1fcb4 6 (4d(9e5)) ((6g(4h2))i((3j2)k(6l8)))
a1fcb 4 6 (4d(9e5)) ((6g(4h2))i((3j2)k(6l8)))
a1fc (4b6) (4d(9e5)) ((6g(4h2))i((3j2)k(6l8)))
a1f ((4b6)c(4d(9e5))) ((6g(4h2))i((3j2)k(6l8)))
a1 (((4b6)c(4d(9e5)))f((6g(4h2))i((3j2)k(6l8))))
a 1 (((4b6)c(4d(9e5)))f((6g(4h2))i((3j2)k(6l8))))
 (1a(((4b6)c(4d(9e5)))f((6g(4h2))i((3j2)k(6l8)))))
```
[Answer]
# [Rust](https://www.rust-lang.org/), 117 bytes
```
fn f(s:&mut std::str::Chars)->String{let c=s.next().unwrap();if c<'a'{c.into()}else{format!("({}{}{})",f(s),c,f(s))}}
```
Takes a mutable reference to a character iterator and returns a string. Requires Rust 1.46+.
[Rust Playground](https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&code=%0Afn%20f(s%3A%26mut%20std%3A%3Astr%3A%3AChars)-%3EString%7Blet%20c%3Ds.next().unwrap()%3Bif%20c%3C%27a%27%7Bc.into()%7Delse%7Bformat!(%22(%7B%7D%7B%7D%7B%7D)%22%2Cf(s)%2Cc%2Cf(s))%7D%7D%0A%0A%2F%2F%20Run%20testcases%0Afn%20main()%20%7B%0A%20%20%20%20let%20testcases%20%3D%20%22a34%20-%3E%20(3a4)%0Aba567%20-%3E%20((5a6)b7)%0Acba1234%20-%3E%20(((1a2)b3)c4)%0Aa1b23%20-%3E%20(1a(2b3))%0Aa1fcb46d4e95ig6h42kj32l68%20-%3E%20(1a(((4b6)c(4d(9e5)))f((6g(4h2))i((3j2)k(6l8)))))%22%3B%0A%20%20%20%20for%20line%20in%20testcases.lines()%20%7B%0A%20%20%20%20%20%20let%20(input%2C%20expected)%20%3D%20parse_input(line)%3B%0A%20%20%20%20%20%20let%20result%20%3D%20f(%26mut%20input.chars())%3B%0A%20%20%20%20%20%20println!(%22%7B%7D%20-%3E%20%7B%7D%22%2C%20input%2C%20result)%3B%0A%20%20%20%20%20%20assert_eq!(result%2C%20expected)%3B%0A%20%20%20%20%7D%0A%7D%0A%20%20%20%20%0Afn%20parse_input(line%3A%20%26str)%20-%3E%20(String%2CString)%20%7B%0A%20%20%20%20let%20parts%3A%20Vec%3C_%3E%20%3D%20line.split(%22%20-%3E%20%22).collect()%3B%0A%20%20%20%20(%0A%20%20%20%20%20%20%20%20parts%5B0%5D.into()%2C%0A%20%20%20%20%20%20%20%20parts%5B1%5D.into()%2C%0A%20%20%20%20)%0A%7D)
### Ungolfed
```
fn f(iterator: &mut std::str::Chars) -> String
{
    // Get next character
    let c = iterator.next().unwrap();
    // If it's a digit 
    if c < 'a' {
        c.into() // convert the sole digit character into a string
    }
    // Otherwise
    else {
        // Build infix string with two recursive calls for the operands
        format!("({}{}{})", f(iterator), c, f(iterator))
    }
}
```
[Answer]
# [Curry (PAKCS)](https://www.informatik.uni-kiel.de/%7Epakcs/), 44 bytes
```
f(a:b++c)|a>'9'='(':f b++a:f c++")"
f[a]=[a]
```
[Try it online!](https://tio.run/##Sy4tKqrULUjMTi7@/z9NI9EqSVs7WbMm0U7dUt1WXUPdKk0BKJIIpJK1tZU0lbjSohNjbYH4f25iZp6CrUKaglKiYVpykolZikmqpWlmulmGiVF2lrFRjpmF0n8A "Curry (PAKCS) ‚Äì Try It Online")
[Answer]
# [Lexurgy](https://www.lexurgy.com/sc), 164 bytes
```
class d {\0,\1,\2,\3,\4,\5,\6,\7,\8,\9}
a propagate:
{a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z}$1 {(\( []+ \)),@d}$2 {(\( []+ \)),@d}$3=>\( $2 $1 $3 \)
```
Explanation:
```
class d {\0,\1,\2,\3,\4,\5,\6,\7,\8,\9} # define digits
a propagate: # while the input changed last iteration...
# match an op
{a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z}$1
# match left expr
    {(\( []+ \)),@d}$2
# match right expr
        {(\( []+ \)),@d}$3
# put parens, swap op and left
            =>\( $2 $1 $3 \)
```
[Answer]
# [Java (JDK)](http://jdk.java.net/), 91 bytes
```
Object f(java.util.Iterator<Character>s){var c=s.next();return c<97?c:"("+f(s)+c+f(s)+")";}
```
[Try it online!](https://tio.run/##VVA7b8IwEN75FadISLYAS4QQyrNDpw5VB7pVHS7GAYe8ZF9QK8Rvd@0SVe3gO913/h52gRecFIeza7us1BJkidbCC@oargOAHrWE5Nul0Qeo/I7tyej6@P4BaI6W/1wFyBsD7IImgLD6twIIuCbYBljIExrLuKiwfWtes4JJmOyABZhLLjQpg9QYxtd/2EbZrgwKOdP0u9l/WVKVaDoSrc9EOYuGNqgN7bCOxsFu3FN7zm1wP/dHOW@vJHnRwn@F6EiX4rn33zz5QCj9tLP8GjLIrRW1@iSfzCjqTA1ys1w8ylXEolHOLB/Je4t4tL65m3M4S1yG83ThZIbT2E84zeKZr7nMkvSQqOVcH9NTEp@LWVymD98 "Java (JDK) ‚Äì Try It Online")
[Answer]
# [C (gcc)](https://gcc.gnu.org/), ~~71~~ 70 bytes
-1 thanks to [AZTECCO](https://codegolf.stackexchange.com/questions/237574/convert-prefix-to-infix/237616?noredirect=1#comment539038_237616)
```
f(char*s){s=putchar(*s+!(*s++>60?f("("),s=f(s):1))>60?f(s)+!f(")"):s;}
```
[Try it online!](https://tio.run/##RY/RbsIwDEWfyVcES5Ni0gnahrARyj5k4yENDWRjBdXdy6p@e5dCpb1Y19fX1rF7Pjk3DF64s20WhB0Vt592bMSC5Hwscq9Xb16AAEyo8IJwmyI@TEI5jyME3JLph28baoEdux/jrXs/8IJ3DGyuIGFQ2rXejMKVNs0enk3LLP/3fHVUU8im3pVKH1X1ug4nfVbZ12eeXfQLsN4wf224CHXLQ7EyYUfht7p60TpcTvLOgCZIiRFhdmtiOKLu@RN91JBEuHBAw2bj0iTj5yQAouxZP/wB "C (gcc) ‚Äì Try It Online")
Relies on summands evaluating from left to right. Outputs to stdout.
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 40 bytes
```
If[t=##2;#>60,##&[40,#0@t,#,#0@t,41],#]&
```
[Try it online!](https://tio.run/##VchBC4IwGIDhuz9jH3haoHOuIpSBEHQL6iYevs0trVQYu4n@9VV46vQ@vAP6zgzoe43BFuFia18AsBOUIqEAcc2/SaSnsIWnDYUmDlfXj76GXXl201B16FB746qpNXK2Ut6n/wdLE683jeM6RwQzTmhEFOZi/4NWmLLtYapYtsFqxUXLzTHvH6Lj7PXM2FscSLSEDw "Wolfram Language (Mathematica) ‚Äì Try It Online")
Input and output a sequence of character codes.
### [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 37 bytes
```
If[t=##2;#>60,40 .#0@t.#.#0@t. 41,#]&
```
[Try it online!](https://tio.run/##VYtBC4IwGIbv/grZoEOY6JyrCGUgBEGHoG7i4dvccpUKa7fIv74KT52eh@fl7cF1qgdnJHhd@IOuXYEx2eGSJRFNwhgn3MV4RkjTCDcLf7JmcDVelXs79lUHFqRTthpbxZdH83Sca84v4//yPU5nCcP0ChBkFEUBEpCz9U@kgJTMDVJBslm0FJS1VG1zc2UdJfdbRh5sg4K3/wA "Wolfram Language (Mathematica) ‚Äì Try It Online")
Outputs a `Dot` of character codes instead.
[Answer]
# Scala, 57 bytes
```
s=>{def g:Any={val n=s.next;if(n>58)s"($g$n$g)"else n};g}
```
[Try it online!](https://scastie.scala-lang.org/DylOh9yeSFWNzgNzefzY0w)
Takes an iterator of characters instead of a string so it can save its position.
## Without an iterator, 118 bytes
```
f(_)._1
def f(s:String):(Any,String)=if(s(0)<58)s.splitAt(1)else{val(a,t)=f(s.tail);val(b,u)=f(t);s"($a${s(0)}$b)"->u}
```
[Try it online!](https://scastie.scala-lang.org/QGm9zd8YTgOsWY6A61XxHA)
[Answer]
# [Haskell](https://www.haskell.org/), 63 bytes (or 69\*)
Below, `a` is Haskell's IO monad computation of type `IO ()` which, when executed, reads the expression from `stdin` and outputs the result to `stdout`.
```
a=getChar>>=(putStr#)
p#c|c<'a'=p[c]|1<2=p"(">>a>>p[c]>>a>>p")"
```
[Try it online!](https://tio.run/##ZVDBaoNAEL3vVwymED0YiDG2DXEPDS0EWnLIsZQwrlu12eyKu1IC@Xe7rloo3cNjZt6bfcMrUZ@5EF11qVVj4HjVhl8W@wP4lX4@vARkJHZKmkaJxZuSmIPfSsG1DjpMC252JTaUpn7dmqNpZgGpZ@zGtnOcp/U7@7gtt1Fae75HKVLaT4bCC7yulaYS1m2zAYtPSgkIaV/6wW9BJhFTModM5VdIIVcE7NOlakV@0kbVsA2dws2H@/7QvtukFP59FxBywUqOR1hD140ek9rFAXeTMTo89aZjAhCGsC@kajiYkoPk36KSHJilkBneuIUholcJntfhKiYZrpN7wjJcRrbDZRatLH6yLE7ymD@uqyIp4@j8tYpE8kB@AA "Haskell ‚Äì Try It Online")
### Ungolfed code
```
main = a >> putStrLn ""
a :: IO ()
a = do
  c <- getChar -- read a character c
  putStr # c   -- if c is an operator, process its arguments
(#) :: (String -> IO ()) -> Char -> IO ()
p # c 
  | c < 'a' = p[c] -- the character is a number
  | otherwise = do -- the character is an operator
    p "(" -- print "(" to stdout
    a     -- read the left subexpression and output it in the required format
    p [c] -- print the operator to stdout
    a     -- read the right subexpression and output it in the required format
    p ")" -- print ")" to stdout
```
### \*Disclaimer
I am not sure if the standard code golf rules permit answers being Haskell's IO monads of type `IO ()`. In [this meta answer](https://codegolf.meta.stackexchange.com/a/11935), it was stated that computations of type `IO a` which read `stdin` and produce a value of type `a` are allowed. Should the `IO ()` type be unacceptable, I shall replace my answer with this 69 byte entry with computation of type `IO String` ‚Äì
[try it online!](https://tio.run/##ZVDRaoMwFH3PV1xKQUUs1Fq3WfVhZYPCRh/6OEaJSVpd00SSSCn0313M7GAsD4dzcu6953JrrE@M8745t1IZ2F21YefZZgt@o1@2rwEajbUURkk@e5cCU/A7wZnWQY@LIzPrGquyLA7oAORGcg97Rdsp9kE@b/M8Lqhc8TzCKzXAYEw938t4GJJMheEkmPSdMA23mVkGFp@l5BCVA/WDX4LuRUQKCpWkVyiASgT26Vp2nO61kS3kkatw/z9b/rF911mW8G9cgNAZN2JcwgY6NWbcq91RYHoPxkJfmBoysdP7gY4XgSiCzVFIxcDUDAS78EYwINbCxDDlGtrO7Ix6E@OkHi8SVOFl@oBIheexVXhexQuLB1IlKU3Y07I5pnUSn74WMU8f0Tc "Haskell ‚Äì Try It Online").
I asked for a clarification in [this comment](https://codegolf.stackexchange.com/questions/237574/convert-prefix-to-infix/237817#comment539295_237574).
[Answer]
# [Python](https://www.python.org), ~~146~~ ~~139~~ 84 bytes
```
lambda x,s=[]:[(s:=s+[n if n<":"else"("+s.pop()+n+s.pop()+")"])for n in x[::-1]][-1]
```
[Attempt This Online!](https://ato.pxeger.com/run?1=m72soLIkIz9vweI025ilpSVpuhY3Q3ISc5NSEhUqdIpto2OtojWKrWyLtaPzFDLTFPJslKyUUnOKU5U0lLSL9QryCzQ0tfPgLCVNpVjNtPwiBaDiPIWKaCsrXcPY2GggATVbtaAoM69EI01DKdEwLTnJxCzFJNXSNDPdLMPEKDvL2CjHzEJJUxOieMECCA0A)
*¬Ø55 thanks to @emanresuA*
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), 54 bytes
```
‚äûœÖ‚ü¶‚üßÔº¶Ôº≥¬ø‚ÑñŒ≤Œπ‚äûœÖ‚ü¶Œπ‚üß¬´‚äû¬ßœÖ¬±¬πŒπÔº∑‚Åº¬≥Ôº¨¬ßœÖ¬±¬π‚äû¬ßœÖ¬±¬≤‚™´()‚™´‚Æå‚Å∫‚ü¶‚äü¬ßœÖ¬±¬π‚üß‚äüœÖœâ¬ª‚äüœÖ
```
[Try it online!](https://tio.run/##dY@xbsIwEIZn/BQnprOUDoQ0apUJoQ4ghKIyIgYTLonBsmlsA1LFs7txRVkKy@n0/fr@01Wt6CojVAilty36BNYbXrDadIAzffRu5TqpG@QcZA04NV473CYge3A3ZFRIWYJvNvilEzfTO7rEdEmNcIQjzqNVsMG5lYoAP768UBbHCSxIN@6Jw//u/E/T2Dg3UuMQ@fC2ftKJOktYKm9xXZrj49pNAjHzPHac@1mwKyv7Tx3eeBGCGNXVNst3Gb2/yiZvs/SwH6cqfwsvJ/UD "Charcoal ‚Äì Try It Online") Link is to verbose version of code. Explanation:
```
‚äûœÖ‚ü¶‚üß
```
Start with no expression.
```
Ôº¶Ôº≥
```
Loop over the input characters.
```
¬ø‚ÑñŒ≤Œπ‚äûœÖ‚ü¶Œπ‚üß
```
If it's a letter then begin a new operation.
```
¬´
```
Otherwise:
```
‚äû¬ßœÖ¬±¬πŒπ
```
Push this operand to the current operation.
```
Ôº∑‚Åº¬≥Ôº¨¬ßœÖ¬±¬π
```
While the current operation has both of its operands, ...
```
‚äû¬ßœÖ¬±¬≤‚™´()‚™´‚Æå‚Å∫‚ü¶‚äü¬ßœÖ¬±¬π‚üß‚äüœÖœâ
```
Convert it to infix and push it to its parent operation, which becomes the new current operation.
```
¬ª‚äüœÖ
```
Output the final infix code.
[Answer]
# [Pip](https://github.com/dloscutoff/pip), 34 bytes
```
c:POacGT9?pJ J[b:REacREa@>#:bDCp]c
```
Takes the prefix expression as a command-line argument. [Replit!](https://replit.com/@dloscutoff/pip) Here's the closest I can get with TIO: [Try it online!](https://tio.run/##K8gs@F9gpaShqfQ/2SrAPzHZPcTSvsBLwSs6yUojLVEzGUg42ClbJbk4F2jGJv///z/RMMnIGAA "Pip ‚Äì Try It Online")
### Explanation
Recursive program; parses the first prefix expression from its input and returns its infix representation. If the input starts with a digit, the expression is just that single digit. Otherwise, the first character is an operator and its operands are the results of recursively parsing twice.
```
c:POacGT9?pJ J[b:REacREa@>#:bDCp]c
    a                               Current prefix expression, possibly including
                                    some extra trailing characters
  PO                                Pop the first character
c:                                  and store it in local variable c
     cGT9                           Is c greater than "9" (string comparison)?
         ?                          If so, it's a letter:
              [                 ]    Make a list containing the following:
                                      1)
                 REa                   Call the program recursively on the portion of
                                       the input after the (popped) first character
               b:                      and assign the result to local variable b
                                      2)
                    c                  The popped first character (the operator)
                                      3)
                     RE                Call the program recursively on
                       a@>             the portion of the input after this index...
                          #:           Length of
                            bDCp       b from earlier with all parentheses deleted
             J                       Join that list into a single string
          pJ                         Join "()" on that string
                                    Otherwise, c is a number:
                                 c   Return the number
```
[Answer]
# [Stax](https://github.com/tomtheisen/stax), 17 [bytes](https://github.com/tomtheisen/stax/blob/master/docs/packed.md#packed-stax)
```
√®‚ñº2‚ïñX!√∫‚ñ¨Ie‚ïì∆í√ª‚âà¬≤O‚î¨
```
[Run and debug it](https://staxlang.xyz/#p=8a1f32b75821a3164965d69f96f7fd4fc2&i=a34%0Aba567%0Acba1234%0Aa1b23%0Aa1fcb46d4e95ig6h42kj32l68&a=1&m=2)
[Answer]
# [BQN](https://mlochbaum.github.io/BQN/), 38 36 [bytes](https://github.com/mlochbaum/BQN/blob/master/commentary/sbcs.bqn)
```
{ùï©{'9'(1‚åΩ")("‚àæùïä‚àæÀúùïä‚àæ‚ä¢)‚çü<ùïó‚äëÀúi+‚Ü©1}i‚Üê¬Ø1}
```
[Try it here.](https://mlochbaum.github.io/BQN/try.html#code=RiDihpAge/Cdlal7JzknKDHijL0iKSgi4oi+8J2ViuKIvsuc8J2ViuKIvuKKoinijZ888J2Vl+KKkcucaSvihqkxfWnihpDCrzF9CgpGwqgiYTM0IuKAvyJiYTU2NyLigL8iY2JhMTIzNCLigL8iYTFiMjMi4oC/ImExZmNiNDZkNGU5NWlnNmg0MmtqMzJsNjgiCg==)
How it works:
The outer function simply makes a counter `i` and passes the input `ùï©` to the inner function as `ùïó`.
```
{'9'(1‚åΩ")("‚àæùïä‚àæÀúùïä‚àæ‚ä¢)‚çü<ùïó‚äëÀúi+‚Ü©1} # Inner function
                        i+‚Ü©1  # Increment i, 
                     ùïó‚äëÀú      # and use it to index into the input
 '9'(             )‚çü<         # if the code point is greater than '9'
               ùïä‚àæ‚ä¢            # recurse and prepend the result
            ùïä‚àæÀú               # recurse and append the result
     1‚åΩ")("‚àæ                  # wrap with parentheses
```
[Answer]
# [Pyth](https://github.com/isaacg1/pyth), 33 bytes
```
V_Q?-1/GN=Y+YN=Y+YjN[+\(.)Y+.)Y\)
```
[Try it online!](https://tio.run/##K6gsyfj/Pyw@0F7XUN/dzzZSOxJMZPlFa8do6GlGagNxjOb//0qJhmnJSSZmKSaplqaZ6WYZJkbZWcZGOWYWSgA "Pyth ‚Äì Try It Online")
```
                                     # Q = eval(input())
                                     # G = "abcdefghijklmnopqrstuvwxyz"
                                     # Y = []
V_Q                                  # for N in reversed(Q):
   ?-1/GN                            #   if N in G:
         =Y+YN                       #     Y.append(N)
                                     #   else:
                   jN[+\(.)Y+.)Y\)   #     X = N.join(['(' + Y.pop(), Y.pop() + ')'])
              =Y+Y                   #     Y.append(X)
```
]