Convert prefix to infix

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 rules apply.

Answer 1

Python 3.8 (pre-release), 61 bytes

f=lambda S:(s:=next(S:=iter(S)))[:s<"a"]or"("+f(S)+s+f(S)+")"

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 2

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!

Thanks to @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 3

JavaScript (Node.js), 49 bytes

s=>(i=0,g=(c=s[i++])=>c>=0?c:'('+g()+c+g()+')')()

Try it online!

Answer 4

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].

Answer 5

Haskell, 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!

Answer 6

R, 96 65 72 69 bytes

Or R>=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.
+7 bytes costed converting from not-so-self-contained function to a program.
-3 bytes thanks to @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!

Port of @loopy walt's answer.

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>=4.1:

R, 74 bytes

Or R>=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!

Same as above, but here i is "local" for the main function, but "global" for the recursive one.

Answer 7

Prolog (SWI), 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!

Answer 8

Retina, 74 bytes

+`([a-z])((([a-z])|(?<-4>\d))*\d)((([a-z])|(?<-7>\d))*\d)
($2$U$1$5)
T`L`l

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 9

Ruby, 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!

Answer 10

Perl 5 -p, 51 bytes

s/(\D) (\S+) (\S+)/ ($2$1$3)/||s/.\b/ $&/ until/^ /

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 11

Rust, 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

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 12

Curry (PAKCS), 44 bytes

f(a:b++c)|a>'9'='(':f b++a:f c++")"
f[a]=[a]

Try it online!

Answer 13

Lexurgy, 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 14

Java (JDK), 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!

Answer 15

C (gcc), 71 70 bytes

-1 thanks to AZTECCO

f(char*s){s=putchar(*s+!(*s++>60?f("("),s=f(s):1))>60?f(s)+!f(")"):s;}

Try it online!

Relies on summands evaluating from left to right. Outputs to stdout.

Answer 16

Wolfram Language (Mathematica), 40 bytes

If[t=##2;#>60,##&[40,#0@t,#,#0@t,41],#]&

Try it online!

Input and output a sequence of character codes.

Wolfram Language (Mathematica), 37 bytes

If[t=##2;#>60,40 .#0@t.#.#0@t. 41,#]&

Try it online!

Outputs a Dot of character codes instead.

Answer 17

Scala, 57 bytes

s=>{def g:Any={val n=s.next;if(n>58)s"($g$n$g)"else n};g}

Try it online!

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!

Answer 18

Haskell, 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!

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, 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!.

I asked for a clarification in this comment.

Answer 19

Python, 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!

¯55 thanks to @emanresuA

Answer 20

Charcoal, 54 bytes

⊞υ⟦⟧ＦＳ¿№βι⊞υ⟦ι⟧«⊞§υ±¹ιＷ⁼³Ｌ§υ±¹⊞§υ±²⪫()⪫⮌⁺⟦⊟§υ±¹⟧⊟υω»⊟υ

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 21

Pip, 34 bytes

c:POacGT9?pJ J[b:REacREa@>#:bDCp]c

Takes the prefix expression as a command-line argument. Replit! Here's the closest I can get with TIO: 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 22

Stax, 17 bytes

è▼2╖X!ú▬Ie╓ƒû≈²O┬

Run and debug it

Answer 23

BQN, 38 36 bytes

{𝕩{'9'(1⌽")("∾𝕊∾˜𝕊∾⊢)⍟<𝕗⊑˜i+↩1}i←¯1}

Try it here.

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 24

Pyth, 33 bytes

V_Q?-1/GN=Y+YN=Y+YjN[+\(.)Y+.)Y\)

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)