23
\$\begingroup\$

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.

\$\endgroup\$
14
  • 1
    \$\begingroup\$ @mousetail That's not a valid expression. \$\endgroup\$ Aug 9 at 14:50
  • 1
    \$\begingroup\$ Also the last test case seems incorrect, there shouldn't be a space between the / and 30 right? \$\endgroup\$
    – mousetail
    Aug 9 at 14:50
  • 1
    \$\begingroup\$ @DLosc I originally intended all whitespace, but I think that it's more interesting if limited to spaces only, so I'll say that. \$\endgroup\$ Aug 9 at 16:59
  • 3
    \$\begingroup\$ maintaining the whitespace - this seems unnecessary and prevents answers from parsing languages like flex. \$\endgroup\$
    – Noodle9
    Aug 9 at 18:19
  • 2
    \$\begingroup\$ 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}. \$\endgroup\$
    – Deadcode
    Aug 9 at 23:32

17 Answers 17

15
\$\begingroup\$

Regex (Perl / PCRE / Pythonregex), 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 Pythonregex, 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!

\$\endgroup\$
10
  • 1
    \$\begingroup\$ 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 \$\endgroup\$
    – Steffan
    Aug 9 at 20:40
  • 1
    \$\begingroup\$ Your Ruby can be 73, omitting the parens and adding a space: ->s{s.each_char{s.sub! /([*-\/] *(\d++|\(\g<1>\)) *\g<2>)(?!\))/,'(\1)'}} \$\endgroup\$
    – Steffan
    Aug 9 at 20:41
  • 1
    \$\begingroup\$ You can also save a few more by using s.chars instead of s.each_char \$\endgroup\$
    – Steffan
    Aug 9 at 20:42
  • 1
    \$\begingroup\$ You can save another byte on the Ruby by avoiding sub!: Try it online! \$\endgroup\$
    – Dingus
    Aug 10 at 0:54
  • 1
    \$\begingroup\$ @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.) \$\endgroup\$
    – Deadcode
    Aug 11 at 0:53
5
\$\begingroup\$

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!

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

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.
\$\endgroup\$
2
  • \$\begingroup\$ Using a regexp substitution is 30 bytes shorter :-) \$\endgroup\$
    – Deadcode
    Aug 10 at 20:37
  • 1
    \$\begingroup\$ @Deadcode Well done! :-) \$\endgroup\$
    – Luis Mendo
    Aug 10 at 20:40
5
\$\begingroup\$

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

\$\endgroup\$
5
+100
\$\begingroup\$

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

\$\endgroup\$
17
  • 1
    \$\begingroup\$ get_code can be get0, and you can remoev the space after :-. \$\endgroup\$
    – Steffan
    Sep 2 at 14:54
  • \$\begingroup\$ some simple golfs for 139. can be way shorter, will work on this later. \$\endgroup\$
    – Steffan
    Sep 2 at 15:06
  • \$\begingroup\$ 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 \$\endgroup\$
    – Steffan
    Sep 2 at 15:10
  • \$\begingroup\$ 125 \$\endgroup\$
    – Steffan
    Sep 2 at 15:35
  • 2
    \$\begingroup\$ I hate to rain on your parade, but the question requires that trailing spaces be preserved, which your 91-byte version does not do. \$\endgroup\$
    – DLosc
    Sep 3 at 7:28
4
\$\begingroup\$

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

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!

\$\endgroup\$
1
  • \$\begingroup\$ Welcome to Code Golf, and nice answer! \$\endgroup\$ Aug 9 at 18:52
4
\$\begingroup\$

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

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.

\$\endgroup\$
10
  • \$\begingroup\$ This is not fully parenthesizing the last test case, / -20/ 30 30 999. \$\endgroup\$
    – Deadcode
    Aug 9 at 21:22
  • \$\begingroup\$ @Deadcode Ugh I can't believe it took me over half an hour to spot that missing ?... \$\endgroup\$
    – Neil
    Aug 9 at 22:21
  • \$\begingroup\$ Oopsie! But any reason you didn't use the character class [*-/] to save 1 byte? \$\endgroup\$
    – Deadcode
    Aug 9 at 22:57
  • \$\begingroup\$ @Deadcode Partly because I had already forgotten by then and partly because I don't like mixing golfs with bugfixes. \$\endgroup\$
    – Neil
    Aug 9 at 23:19
  • 2
    \$\begingroup\$ You can drop the (?(2)^) and change the [^()] to [^)] for -8 bytes, because the expression is already atomicized and the parentheses are guaranteed to be balanced since your own regex is what created them. \$\endgroup\$
    – Deadcode
    Aug 10 at 0:01
3
\$\begingroup\$

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!

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

Charcoal, 46 bytes

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

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

∧⊞O⊞Oυ⁺⊟υ)ω

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

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

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

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).
\$\endgroup\$
4
  • \$\begingroup\$ X+[]+X. can just be X+_+X. because if that point is reached, we know that the list is empty. \$\endgroup\$
    – Steffan
    Sep 2 at 18:50
  • \$\begingroup\$ Why not have I/O as list of charcodes, like this? \$\endgroup\$
    – Steffan
    Sep 2 at 18:52
  • \$\begingroup\$ @Steffan I can't remember if that's allowed, but if so, that's the alternate solution at the bottom of the post already. ;) \$\endgroup\$
    – DLosc
    Sep 2 at 19:34
  • 1
    \$\begingroup\$ You can use atom_codes instead of string_codes and itw ill still work with strings. \$\endgroup\$
    – Steffan
    Sep 2 at 19:59
2
\$\begingroup\$

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!

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

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.

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

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

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!

\$\endgroup\$
0

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.