27
\$\begingroup\$

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

\$\endgroup\$
8
  • \$\begingroup\$ May we I/O as vector/array of characters or of ASCII char codes? \$\endgroup\$
    – pajonk
    Nov 23, 2021 at 16:53
  • \$\begingroup\$ @pajonk Sure, that's fine. \$\endgroup\$
    – emanresu A
    Nov 23, 2021 at 19:46
  • \$\begingroup\$ Bonus challenge: Remove all parentheses that are redundant in the conventional infix notation. \$\endgroup\$
    – xigoi
    Nov 23, 2021 at 21:43
  • \$\begingroup\$ @xigoi how is the precedence defined for letters? \$\endgroup\$ Nov 24, 2021 at 23:32
  • \$\begingroup\$ @PauloEbermann That would be with normal operators. \$\endgroup\$
    – xigoi
    Nov 25, 2021 at 7:06

24 Answers 24

9
\$\begingroup\$

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.

\$\endgroup\$
6
\$\begingroup\$

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

\$\endgroup\$
6
+100
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

JavaScript (Node.js), 49 bytes

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

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ Can c>=0 be 1/c? \$\endgroup\$
    – Neil
    Nov 23, 2021 at 13:03
  • 1
    \$\begingroup\$ @pxeger 1/"0" is truthy, so why do you think it doesn't work? \$\endgroup\$
    – Neil
    Nov 23, 2021 at 14:51
  • \$\begingroup\$ 47 bytes (including @Neil's suggestion). \$\endgroup\$
    – Arnauld
    Nov 23, 2021 at 16:08
4
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ This is great obfuscated R code. I can't understand it at all. But, anyway, if you don't mind accepting and returniong vectors of characters (instead of strings) you could save quite a lot... \$\endgroup\$ Nov 23, 2021 at 14:40
  • \$\begingroup\$ @Dominic, thanks, I didn't know whether it's acceptable (taking vector of char codes would be even shorter), I'll ask OP. And will add an explanation later. \$\endgroup\$
    – pajonk
    Nov 23, 2021 at 16:52
  • \$\begingroup\$ I hope it's acceptable (I seem to recall that this is a standard IO) - and, if so, you could shave-off some more bytes by removing the 2nd function definition: try it... \$\endgroup\$ Nov 23, 2021 at 20:18
  • 1
    \$\begingroup\$ @DominicvanEssen, actually I'm wondering now if the one-function approach is valid as it's not entirely reusable (meta1, meta2) \$\endgroup\$
    – pajonk
    Nov 23, 2021 at 20:55
  • 1
    \$\begingroup\$ 69 bytes as re-useable function (+ global variable)... \$\endgroup\$ Nov 24, 2021 at 11:49
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Welcome to CGCC, and nice answer. You can save a few bytes by removing parentheses around lambda arguments and using a ternary conditional: Try it online! \$\endgroup\$
    – Dingus
    Nov 24, 2021 at 22:51
  • \$\begingroup\$ Thank you @Dingus! \$\endgroup\$
    – lonelyelk
    Nov 24, 2021 at 23:23
3
\$\begingroup\$

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)))))
\$\endgroup\$
3
\$\begingroup\$

Curry (PAKCS), 44 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
0
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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))
    }
}
\$\endgroup\$
2
\$\begingroup\$

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 Stringtry it online!.

I asked for a clarification in this comment.

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\begingroup\$ 90 bytes with some hackery \$\endgroup\$
    – emanresu A
    Feb 27 at 4:16
  • \$\begingroup\$ 84 with severe lambda abuse \$\endgroup\$
    – emanresu A
    Feb 27 at 4:22
2
\$\begingroup\$

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 \)
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 54 bytes

⊞υ⟦⟧FS¿№βι⊞υ⟦ι⟧«⊞§υ±¹ιW⁼³L§υ±¹⊞§υ±²⪫()⪫⮌⁺⟦⊟§υ±¹⟧⊟υω»⊟υ

Try it online! Link is to verbose version of code. Explanation:

⊞υ⟦⟧

Start with no expression.

FS

Loop over the input characters.

¿№βι⊞υ⟦ι⟧

If it's a letter then begin a new operation.

«

Otherwise:

⊞§υ±¹ι

Push this operand to the current operation.

W⁼³L§υ±¹

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

Stax, 17 bytes

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

Run and debug it

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
5
  • \$\begingroup\$ Wouldn't it be cheaper to convert the input into a iterable of characters? \$\endgroup\$
    – emanresu A
    Nov 26, 2021 at 20:08
  • \$\begingroup\$ @emanresuA What do you mean? \$\endgroup\$
    – user
    Nov 26, 2021 at 20:10
  • \$\begingroup\$ For the version without an iterator (Just takes a string) couldn't you save bytes by converting the input into an iterable? \$\endgroup\$
    – emanresu A
    Nov 26, 2021 at 20:14
  • \$\begingroup\$ @emanresuA I'm not sure what you mean, strings are already iterable in Scala. Could you give some pseudocode of what you were thinking of? \$\endgroup\$
    – user
    Nov 26, 2021 at 20:20
  • \$\begingroup\$ Never mind, doesn't really matter \$\endgroup\$
    – emanresu A
    Nov 26, 2021 at 20:30
0
\$\begingroup\$

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)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.