Add parentheses to Polish notation

Question

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 code-golf, the shortest program wins.

Answer 1

Regex (Perl / PCRE / Python^regex), 48 47 45 44 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:
($2$1$3)  # ( argument1 operator argument2 )
~         # No flags

See also Convert from postfix notation to infix notation, which adds parsing of operator precedence.

Regex (_{^{Perl /}} Boost), 47 46 bytes

s~([*-/] *(\d++|\((?1)\)) *(?2))(?!\))~\($1\)~

Try it online! - Perl
Try it online! - Boost

Boost needs parentheses escaped in its replacement argument, because its conditional-replacement syntax uses parentheses. This isn't compatible with PCRE or Python^regex, as they will interpret it as a literal \( and \).

This exposes a bug in Boost's subroutine call processing. If {2} is used to match two arguments, instead of (?2) to match the second argument, it makes an incorrect full match. Example:

+(+ 1 2) 3

If the regex ([*-/]( *(\d++|\((?1)\))){2})(?!\)) is used, it matches +(+ 1 2) instead of the entire expression, so the closing parenthesis is added in the wrong place.

But if the regex ([*-/]( *(\d++|\(([*-/]( *\d++){2})\))){2})(?!\)) (with (?1) replaced with itself to one level of depth) is used instead, it correctly matches the full string.

The bug is still present in the latest version of Boost. I have reported it.

Regex (_{^{PCRE /}} Ruby), 47 46 44 bytes

s~([*-/]( *(\d++|\(\g<1>\))){2})(?!\))~(\1)~

Try it online! - PCRE1
Try it online! - PCRE2
Try it online! - Ruby

Ported to Ruby's subroutine syntax.

\$\large\textit{Functions}\$

Ruby, 75 74 69 67 66 bytes

-5 bytes thanks to Steffan
-1 byte thanks to Dingus

->s{0while s[/([*-\/]( *(\d++|\(\g<1>\))){2})(?!\))/]&&="(#$1)";s}

Try it online!

Python (with regex), 107 106 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), 101 100 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, 51 50 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!

Answer 2

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!

Answer 3

MATL, 93 92 90 89 86 85 84 bytes

t"t'(?<!\()[*-/]'1&XXX<t?:&)w0XH&)40hwb'\d+|[\(-/ ]'XX"@gt1)t47>Ew41>-H+XH2=?41XH]&h

Try it online! Or verify all test cases.

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.

Answer 4

Rust Nightly, 332 319 307 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

Answer 5

Prolog (SWI), 292 274 125 91 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

Answer 6

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 ')
  }
 }
}

Answer 7

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!

Answer 8

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

Answer 9

Retina 0.8.2, 67 66 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.

[*-/]
($&

Prefix a ( to each operator.

Answer 10

Python, 186 bytes

lambda s,a=[]:(t:=s.rstrip(),[a:=c<'!'and a[:-1]+[c+a[-1]]or a+[c.isdigit()and c or"("+c+a.pop()+a.pop()+")"]for c in re.findall("\d+|.",t)[::-1]],a)[2][-1]+' '*(len(s)-len(t))
import re

Attempt This Online!

Handling trailing whitespace added a lot of bytes, even though leading whitespace didn't.

If we didn't have to handle trailing whitespace:

Python, 149 bytes

lambda s,a=[]:[a:=c<'!'and a[:-1]+[c+a[-1]]or a+[c.isdigit()and c or"("+c+a.pop()+a.pop()+")"]for c in re.findall("\d+|.",s)[::-1]][-1][-1]
import re

Attempt This Online!

If there was no whitespace or multi-digit numbers:

Python, 90 bytes

lambda s,a=[]:[a:=a+[c.isdigit()and c or"("+c+a.pop()+a.pop()+")"]for c in s[::-1]][-1][0]

Attempt This Online!

Answer 11

Charcoal, 46 bytes

⊞υω⭆θ⎇№+-*/ι∧⊞Ｏ⊞Ｏυ⁺⊟υ)ω⁺(ι⎇›№⭆χλι№⭆χλ§θ⊕κ⁺ι⊟υι

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

⊞υω

Start with 0 on top of the stack.

⭆θ

Loop through the input characters.

⎇№+-*/ι

If this is an operator, then...

∧⊞Ｏ⊞Ｏυ⁺⊟υ)ω

... increment the top of the stack, push 0 to the top of the stack, and...

⁺(ι

... output the operator prefixed with a (.

⎇›№⭆χλι№⭆χλ§θ⊕κ

Otherwise, if this is a digit but the next isn't, then...

⁺ι⊟υ

... output the digit followed by a number of )s given by the top of the stack.

ι

Otherwise, just output the character.

Answer 12

nearley, 78 bytes

m->_ p _{%a=>a.flat(1/0)%}
p->[\d]:+|[-+/*] _ p _ p{%a=>['(',a,')']%}
_->" ":*

Post-processing functions for production rules, denoted by {%...%}, are evaluated in JavaScript. Each function is called with an array of post-processed results for each terminal or non-terminal from which the rule is produced.

This EBNF grammar is defined by three non-terminal production rules m, p, and _.

• _ is zero or more spaces
• p is one or more digits OR one of -, +, /, * followed by _, p, _, then p.
• m is _, p, then _.

The post-processing function of p wraps the result in parentheses when it is produced by [-+/*] _ p _ p, and the post-processing function of m flattens the nested array of characters produced from parsing the complete input.

You can test it in the Nearley Parser Playground, but you'll need to add the the code above and the test cases yourself since there's no permalink feature.

Alternatively, if you're comfortable with the Developer Tools in your browser, you can evaluate the following snippet on the console while loaded on that page to save yourself from having to insert the test cases manually.

localStorage.playgroundState=String.raw`{"active":0,"compiled_grammar":"module.exports={ParserRules:[{name:'m',symbols:['_','p','_'],postprocess:a=>a.flat(1/0)},{name:'p$ebnf$1',symbols:[/[\\d]/]},{name:'p$ebnf$1',symbols:[/[\\d]/,'p$ebnf$1'],postprocess:a=>[a[0],...a[1]]},{name:'p',symbols:['p$ebnf$1']},{name:'p',symbols:[/[-+/*]/,'_','p','_','p'],postprocess:a=>['(',a,')']},{name:'_$ebnf$1',symbols:[]},{name:'_$ebnf$1',symbols:[{literal:' '},'_$ebnf$1'],postprocess:a=>[a[0],...a[1]]},{name:'_',symbols:['_$ebnf$1']}],ParserStart:'m'}","tabs":[{"name":"Add parentheses to Polish notation","editor_value":"m->_ p _{%a=>a.flat(1/0)%}\np->[\\d]:+|[-+/*] _ p _ p{%a=>['(',a,')']%}\n_->\" \":*","errors":[],"tests":["+1 2","++ 1 2 3","    +1    +2 3","* *1 2 /3 0  ","//30 300/18 205","/ -20/ 30 30  999","/////1 2 3 4 5 6","/1/2/3/4/5/6/7/8 9"]}]}`;location.reload()

Answer 13

Prolog (SWI), 178 177 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).

Answer 14

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!

Answer 15

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.

Answer 16

05AB1E, 32 30 bytes

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

Input as a list of characters.

Try it online or verify all test cases.

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

Answer 17

C (clang), 136 132 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!