# Add parentheses to Polish notation

In most programming languages, arithmetic is written with infix notation -- i.e. the operator is put in between the operands -- e.g. 1+2. In contrast, with Polish notation (a.k.a prefix notation), the operator comes before the operands -- e.g. +1 2. As long as the number of operands for each operator is fixed, this means that parentheses are never necessary, unlike with infix notation.

## The Challenge

Given a string consisting of nonnegative integers (digits 0 through 9), spaces, +, -, *, and / representing a single expression in Polish notation, add parentheses around each sub-expression, maintaining the whitespace. The parentheses should start right before the operator and end right after the last operands. You can assume each function has arity 2 (i.e. it takes in exactly 2 operands). You can also assume there will be no extra preceding zeros (e.g. 000 or 09).

## Test Cases

Input Output
+1 2 (+1 2)
++ 1 2 3 (+(+ 1 2) 3)
+1 +2 3 (+1 (+2 3))
* *1 2 /3 0 (* (*1 2) (/3 0))
//30 300/18 205 (/(/30 300)(/18 205))
/ -20/ 30 30 999 (/ (-20(/ 30 30)) 999)
/////1 2 3 4 5 6 (/(/(/(/(/1 2) 3) 4) 5) 6)
/1/2/3/4/5/6/7/8 9 (/1(/2(/3(/4(/5(/6(/7(/8 9))))))))

Standard loopholes are forbidden. As this is , the shortest program wins.

• @mousetail That's not a valid expression. Aug 9, 2022 at 14:50
• Also the last test case seems incorrect, there shouldn't be a space between the / and 30 right? Aug 9, 2022 at 14:50
• @DLosc I originally intended all whitespace, but I think that it's more interesting if limited to spaces only, so I'll say that. Aug 9, 2022 at 16:59
• maintaining the whitespace - this seems unnecessary and prevents answers from parsing languages like flex. Aug 9, 2022 at 18:19
• Suggested test case: /////1 2 3 4 5 6 – a regex 4 bytes shorter passes all the current test cases but breaks on this one. And I'd also suggest /1/2/3/4/5/6/7/8 9 because this pattern approaches the maximum ratio of {number of parentheses pairs added} / {string length}. Aug 9, 2022 at 23:32

# Regex (Perl / PCRE / Pythonregex), 48474544 43 bytes

s~([*-/]( *(\d++|$$(?1)$$)){2})(?!\))~($1)~ Try it online! - Perl Try it online! - PCRE1 Try it online! - PCRE2 Try it online! - Python import regex This is a single regex substitution to be repeatedly applied until it has nothing to match (or until there is no change, where necessary or convenient). In the following explanation, represents a space: s~ # Begin substitution - match the following: ( # Define subroutine (?1);$1 = the following (the entire match):
[*-/]  # Character class of the four arithmetic operators. This also
# includes "," and ".", but those are guaranteed not to be in the
# input.
(
␣*        # Any number of spaces, minimum zero.
(         # Define subroutine (?2) as an argument to an operator:
\d++  # Any number of digit characters, minimum one; force all of
# them to be consumed (prevent backtracking).
|  # or...
$$# An opening parenthesis (?1) # Recursively call (?1)$$    # A closing parenthesis
)
){2}   # Do the above twice (for two arguments).
)
(?!\))     # Assert there is no closing parenthesis following this, as that
# would indicate that this expression has already been parenthesized.
~          # Replace with the following:
($1) # Preserve$1 (the entire match), and surround it with parentheses.
~          # Flags:
# No global flag. For better efficiency, adding the "g" flag
# would allow the substitution loop to end sooner, but it's
# not needed.

Saved 1 byte by using {2} instead of a subroutine call for the second argument (shamelessly stolen from Neil's regex).

## Bonus: Convert Polish notation to infix notation, 58 52 bytes

s~([*-/]) *(\d++|$$(?2)(?1)(?2)$$) *((?2))~($2$1$3)~ Try it online! - PCRE2 s~ # Begin substitution - match the following: ([*-/]) # Define subroutine (?1): Character class of the four arithmetic # operators. This also includes "," and ".", but those are guaranteed # not to be in the input. ␣* # Any number of spaces, minimum zero. ( # Define subroutine (?2) as an argument to an operator: \d++ # Any number of digit characters, minimum one; force all of # them to be consumed (prevent backtracking). | # or... $$# An opening parenthesis (?2) # An argument (?1) # An operator (?2) # An argument$$ # A closing parenthesis ) ␣* # Any number of spaces, minimum zero. ( #$3 = the following:
(?2)  # second argument
)
# No need for "(?!\))", because parenthesized expressions won't be in
# ARGUMENT ARGUMENT OPERATOR format.
~         # Replace with the following:

Try it online!

# Python (with regex), 107106 105 bytes

import regex
f=lambda s,p=0:s==p and s or f(regex.sub('([*-/]( *(\d++|$$(?1)$$)){2})(?!\))',r'(\1)',s),s)

Try it online!

# Python 3.8+ (with regex), 101100 99 bytes

lambda s:[s:=regex.sub('([*-/]( *(\d++|$$(?1)$$)){2})(?!\))',r'(\1)',s)for i in s][-1]
import regex

Can't Try it online! - Confirmed to work on my machine, but regex is not installed on TIO or ATO.

Just like in Remove redundant parentheses, it's guaranteed that a fewer number of substitution iterations will be needed than the number of characters in the input, so this "do this for each character of s" trick works. The maximum number of substitutions approaches $$\1/2\$$ of the number of characters in the input string:

$$\lim_{n\to\infty}{n\over {2n+2}}= {1\over 2}$$

# PowerShell, 100 bytes

[char[]]($p="$args")|%{$p=$p-replace'[*-/](?> *(\d+|$$((\()|[^)]|(?<-3>.))+$$)){2}(?!\))','($&)'};$p

Try it online!

Uses Neil's regex with an additional -8 byte golf. Applies the substitution the same number of times as the length of the input in characters.

# PHP, 104 bytes

function($s){while($p!=$s=preg_replace('~([*-/]( *(\d++|$$(?1)$$)){2})(?!\))~','($1)',$p=$s));return$s;} Try it online! Thanks to Steffan for pointing out a 1 byte golf that has the added bonus of making this anonymous rather than recursive. Knocking off an additional 2 bytes from that has the further bonus of removing the "Undefined variable" warnings from this non-recursive function. ## $$\\large\textit{Full programs}\$$ # MATL, 54 48 bytes -6 bytes thanks to Luis Mendo t"'([*-/]( *(\d++|$$(?1)$$)){2})(?!\))' '($1)'YX

Try it online!

This too applies the substitution the same number of times as the length of the input in characters.

# Perl-p, 5150 49 bytes

1while s;([*-/]( *(\d++|$$(?1)$$)){2})(?!\));($1) Try it online! # PHP-F, 98 bytes <?for($s=$argn;$p!=$s=preg_replace('~([*-/]( *(\d++|$$(?1)$$)){2})(?!\))~','($1)',$p=$s););echo$s; Try it online! • It's amazing how much this beats my current Python answer. Some of these snippets are probably as short as they can get in that language Aug 9, 2022 at 20:40 • Your Ruby can be 73, omitting the parens and adding a space: ->s{s.each_char{s.sub! /([*-\/] *(\d++|$$\g<1>$$) *\g<2>)(?!\))/,'(\1)'}} Aug 9, 2022 at 20:41 • You can also save a few more by using s.chars instead of s.each_char Aug 9, 2022 at 20:42 • You can save another byte on the Ruby by avoiding sub!: Try it online! Aug 10, 2022 at 0:54 • @Jonah Thanks. And to be honest, that's not something I've looked into in detail. Regex not being Turing-complete is a large part of what fascinates me about it – not quite being sure what the boundaries are of what it can do, and sometimes being surprised something turns out to be possible. Though I've been thinking about designing a regex-based language that is Turing-complete, but preserves enough regex-flavor to still be appealing to me. (I feel that Retina is not that.) Aug 11, 2022 at 0:53 # Curry (PAKCS), 102 bytes f(s++t)|all(<'!')t=g s++t g(' ':s)=' ':g s g s|all(>'/')s=s g(c:s++t)|elem c"+-*/"='(':c:g s++g t++")" Try it online! # MATL, 939290898685 84 bytes t"t'(?<!$$)[*-/]'1&XXX<t?:&)w0XH&)40hwb'\d+|[\(-/ ]'XX"@gt1)t47>Ew41>-H+XH2=?41XH]&h The code uses a non-recursive approach, based on the facts that • each operator must have a ( immediately before, and • the corresponding ) must be placed immediately after the first number for which the count of numbers minus operators to the right of the ( equals 2. The procedure is as follows: Repeat these steps as many times as the input length (it would suffice to repeat as many times as the number of operators in the input string): 1. Find the first operator (+-/*) that is not predeced by (, if any. 2. Insert ( right before that. 3. Take the substring after that position until the end and split it into groups, where each group is either a number (one or more digits), an operator, an opening or closing parenthesis, or whitespace (one or more spaces). 4. Start a counter at 0. For each group from the previous step, increment the counter if the group is a number, and decrement it if the group is an operator. 5. When the counter reaches 2, insert ) right after that group. • Using a regexp substitution is 30 bytes shorter :-) Aug 10, 2022 at 20:37 • @Deadcode Well done! :-) Aug 10, 2022 at 20:40 # Rust Nightly, 332319307 292 bytes Can probably be golfed a lot more. |b:&[char]|b.iter().chain([&' ']).scan((vec![9],1),|(a,q),&b|Some(if '0'>b{let mut o=if*q<1{*q=1;let mut u=format!("");while{let z=a.last_mut()?;*z-=1;*z<1}{a.pop();u.push(')')};u.push(b);u}else{b.into()};if b!=' '{o.insert(o.len()-1,'(');a.push(2)}o}else{*q=0;b.into()})).collect::<String>() Playground Link # Prolog (SWI), 29227412591 129 bytes • -18 bytes thanks to Steffan • -999999 bytes thanks to Seffan • -19 bytes thanks to JoKing • -15 bytes by myself :). I realized I didn't really need to return the value "Z" since it's only possible value could be a space. • +28 bytes to fix spacing bug :( Just like my other answer inputs require a trailing space. I'm very new to prolog so this is probably nowhere near optimal. N+Z:-N=32,N,\X,X+Z;N/Z. N:-put(N). \N:-get0(N). 32/32. X/Z:-X<48,40,X,\D,D+W,W+Z,41;X^Z. X^Z:-X>48,X,\W,W^Z;X=Z. :- \X,X+_. TIO • get_code can be get0, and you can remoev the space after :-. Sep 2, 2022 at 14:54 • some simple golfs for 139. can be way shorter, will work on this later. Sep 2, 2022 at 15:06 • removed the halt because I thought you didn't need it, but you can add it back if you think you need it for it to be valid Sep 2, 2022 at 15:10 • 125 Sep 2, 2022 at 15:35 • I hate to rain on your parade, but the question requires that trailing spaces be preserved, which your 91-byte version does not do. Sep 3, 2022 at 7:28 # Pip, 50 bytes W#aI@aQsOPOaEIaLT0OxPBt&'(.POaEL{Oa~XIa:'WDQxO')} Try It Online! (Note: the footer is because DSO doesn't flush the output buffer until a newline is output.) ### Explanation Loop through the input string. • If the first character is a space, pop and output it. • If the first character is an operator: • Output an open paren. • Pop and output the operator. • Push 1 (representing a close-paren) and 0 (representing the space between an operator's first and second operands) to a stack. • Else (this is a number): • Output the first run of digits in the string. • Remove the first run of digits from the string. • Pop the stack; while the result is 1, output a close-paren and repeat. ### Ungolfed expr: a stack: "" W # expr { I @ expr Q " " { O PO expr } EI expr LT "0" { O '( O PO expr stack PB 1 stack PB 0 } EL { O expr ~ ^\d+ expr : ' W DQ stack { O ') } } } # Ruby, 129 bytes f=->(s){def k a;i,j=a.shift;j=~/\d/?(i+j): i+"("+j+k(a)+k(a)+")"end;h,t=s.scan(/(.*[^ ])( *)/)[0];k(h.scan(/( *)([0-9]+|.)/))+t} Try it online! • Welcome to Code Golf, and nice answer! Aug 9, 2022 at 18:52 # Pip, 47 bytes O({a:POysNa?a.VfaLT0?pJa.(fMJt)a}Y(aw,+XD,XX))y This is a different enough approach that I thought it warranted its own answer. Try It Online! ### Explanation First, we tokenize the input: (aw,+XD,XX) a Command-line argument ( ) Find all matches of this regex: w Run of whitespace , or +XD Run of digits , or XX Any single character Now we're going to run a recursive descent parser on this list of tokens, popping each token as it's parsed. Unfortunately, functions in Pip are call-by-value rather than call-by-reference, so we store the list in the global variable y and modify that at each step. This also means our function doesn't actually take any arguments. Calling a function with no arguments can be a bit tricky in Pip, so sometimes we'll call it with a dummy argument that gets ignored. {a:POysNa?a.VfaLT0?pJa.(fMJt)a} { } Recursive function, parses y and returns a parenthesized string POy Pop the first token from y a: Store it in the local variable a sNa? If it contains a space (whitespace token): a. Concatenate it to Vf a recursive call to the current function aLT0? Else, if it is lexicographially earlier than "0" (operator): a.( ) Concatenate it to f the current function MJ called on each character in t "10" (i.e., called twice) and the results joined into a single string pJ Join the string "()" on the above result a Else (number token), just return the token This function parses exactly one expression. In particular, if the input had trailing spaces, the final whitespace token is not parsed and remains in y. Therefore, the overall program is: O({...}Y(...))y (...) Tokenize the input Y Yank the list of tokens into y ( ) Call, with that argument {...} the parser function O Output the resulting parenthesized expression without a newline y Autoprint the remainder of y, if any, with a trailing newline # Retina 0.8.2, 6766 58 bytes +[*-/](?> *\d+| *\(((\()|[^)]|(?<-2>.))+$$){2}(?!\)) ($&)

Try it online! Link includes test cases. Explanation: Much like @Deadcode's answer, the expression tries to find unparenthesised expressions to parenthesise. Explanation:

+

Repeat until no more substitutions can be made.

[*-/]

Match an operator. Edit: Saved 1 byte thanks to @Deadcode.

(?> *\d+

Atomically match an integer parameter, ...

| *$$((\()|[^)]|(?<-2>.))+$$)

... or a balanced parenthesised parameter, ... (Edit: Saved a further 8 bytes thanks to @Deadcode)

{2}

... twice.

(?!\))

Ensure that the operator wasn't previously parenthesised. (This test shamelessly stolen from @Deadcode to save 1 byte.)

($&) Parenthesise the operator and its parameters. Alternative approach, 60 58 bytes: (?<=(()\d+|[^*-/]|(\2|())(?<-2>.))*)\d+$&$#4$*)
[*-/]
($& Try it online! Link includes test cases. Explanation: (?<=(()\d+|[^*-/]|(\2|())(?<-2>.))*)\d+$&$#4$*)

Consider the minimum number of integers that would complete the prefix expression at any given point; this value increases at an operator and (obviously) decreases at an integer. Working back from a given integer, up to the point that the value decreases below the current value, count the number of times it is equal. This is the number of parentheses that should be appended.

[*-/]

# Prolog (SWI), 178177 175 bytes

-3 bytes thanks to Steffan

S/L:-atom_codes(S,L).
[C|T]*P*R:-C=32,T*Q*R,P=[C|Q];C>47,[C|T]+P+R;T*E*Q,Q*F*R,append([[40,C],E,F,[41]],P).
[N|T]+[N|P]+R:-N>47,T+P+R.
X+_+X.
S^T:-S/L,L*P*R,append(P,R,M),T/M.

Try it online!

### Explanation

The other Prolog answer cleverly reads characters from stdin one at a time. I wanted to try a more "traditional" solution, a predicate which takes a string and generates another string.

S/L:-atom_codes(S,L).

Define the / operator as a shortcut for converting an atom or string to a list of codepoints and vice versa.

[C|T]*P*R:-

The * operator is the main workhorse here. It takes a list of codepoints (the first of which is C and the remainder of which are T) and parses one Polish-notation expression from the beginning of it, returning the correctly parenthesized parsed expression in P and the rest of the list of codepoints in R. It has three branches:

C=32,T*Q*R,P=[C|Q]

If C is a space, parse everything after the space and prepend a space to the result.

C>47,[C|T]+P+R

If C is a digit, parse a run of digits using the + operator (defined below).

T*E*Q,Q*F*R,append([[40,C],E,F,[41]],P).

Otherwise, C is an operator. Parse a subexpression E, then parse another subexpression F. Finally, concatenate an open paren, the operator C, both subexpressions, and a close paren together to form the result P.

To parse a run of digits:

[N|T]+[N|P]+R:-N>47,T+P+R.

If the list of codepoints starts with a digit N, parse a run of digits from the portion following N, and prepend N to the result.

X+_+X.

Otherwise, the remainder is the same as the input. The result is a "don't care" (_), which apparently works because (based on its use in the calling predicate) it has to be a list, and the empty list is the first possibility Prolog tries.

The ^ operator is the main predicate:

S^T:-S/L,L*P*R,append(P,R,M),T/M.

It takes a string S, converts it to a list of codepoints L, parses L into a parenthesized expression P and remainder R, concatenates P and R into M (so as to keep any trailing spaces), and converts M back into the string result T.

If I can take and return lists of codepoints instead of strings, this solution is 145 bytes:

[C|T]*P*R:-C=32,T*Q*R,P=[C|Q];C>47,[C|T]+P+R;T*E*Q,Q*F*R,append([[40,C],E,F,[41]],P).
[N|T]+[N|P]+R:-N>47,T+P+R.
X+_+X.
X^Y:-X*P*R,append(P,R,Y).
• X+[]+X. can just be X+_+X. because if that point is reached, we know that the list is empty. Sep 2, 2022 at 18:50
• Why not have I/O as list of charcodes, like this? Sep 2, 2022 at 18:52
• @Steffan I can't remember if that's allowed, but if so, that's the alternate solution at the bottom of the post already. ;) Sep 2, 2022 at 19:34
• You can use atom_codes instead of string_codes and itw ill still work with strings. Sep 2, 2022 at 19:59

# Python3, 226 bytes

lambda s:f(s)[0]
import re
f=lambda s:((' '*O[0].count(' '))+'('+O[0].lstrip()+(J:=f(s[len(O[0]):]))[0]+(T:=f(J[1]))[0]+')',T[1])if(O:=re.findall('^(?:\s+)*[\*\-\+/]',s))else((O:=re.findall('^(?:\s+)*\d+',s))[0],s[len(O[0]):])

Try it online!

# C (GCC), 174 bytes

#define p putchar(
f(char *x){int s[100]={0},*S=s,b,c;for(;*x;){if(b=*x==32)p*x++);for(c=0;isdigit(*x);b=c=1)p*x++);for(*S+=c;*S==2;)p')'),*S=0,*--S+=1;b||++S+p'(')+p*x++);}}

Attempt This Online!

Note: as it is, it works up to 100 nested brackets.

• You don't need the space in char *x Aug 9, 2022 at 17:45
• couldn't you set the size to 999, same amount of bytes with more storage, or is the 100 significant? Aug 10, 2022 at 3:47
• @Samathingamajig yes, you can. 100 was just the first number I typed in Aug 10, 2022 at 7:53
• 166 bytes Aug 13, 2022 at 19:07

# 05AB1E, 32 30 bytes

ÎĆü2vyÇн₆%Ígi'(?>0}y¬?dRJi')×?

Input as a list of characters.

Port of @Neil's Charcoal answer, so make sure to upvote him as well!

Explanation:

Î              # Push 0 and the input character-list
Ć             # Enclose it; append its own head
ü2           # Pop and push its overlapping pairs
v             # Loop over each pair of characters y:
y            #  Push the current pair y
Ç           #  Convert both to its codepoint integer
н          #  Pop and leave just the first integer
₆%        #  Modulo-36
Í       #  +2
g      #  Then pop and push the length
i     #  If this is 1 (which means it's an operator character):
'(? '#   Print "("
>    #   Increase the current value by 1
0    #   Push a new 0
}     #  Close the if-statement
y            #  Push pair y again
¬           #  Push its first character (without popping the pair)
?          #  Pop and output this first character
d         #  Check for both characters whether they're digits
R        #  Reverse the pair
J       #  Join them together to a string
i      #  If this is "01":
')×  '#   Pop the top value, and push a string with that many ")"
?  #   Pop and print it

# C (clang), 136132 125 bytes

#define p putchar(
x;*s;r(n){for(;*s&&n<2;x||p*s<40?n--,*s++:p'(')+!!r(!p*s++))))for(x=!++n;*s>47;)x=p*s++);}f(*a){s=a;r(0);}

Try it online!