Keta Bracket Autocompletion

Question

^{Special thanks to Bubbler and AdmBorkBork for supplying feedback about this challenge}

Keta (Keyboard tacit — clever naming, I know!) is a golfing language I’ve been working on recently. One of it’s features is it’s most probably unique bracket autocompletion system, which will hopefully allow for shorter programs.

There are two types of brackets in Keta: grouping brackets ([] and {}) and list brackets (()). This challenge only involves completing grouping brackets.

Much like it’s predecessor Keg, Keta will automatically close any open brackets within your program. For example:

[3+H

Will be turned into

[3+H]

And:

{0L100R3

Will be turned into:

{0L100R3}

Obviously, matched brackets won’t be autocompleted, as they are already fully closed.

Now, this may seem like a very trivial challenge, but I ain’t done yet. Keta will also close open closing brackets as well. More specifically:

H+4}

Turns into

{H+4}

But what happens if two bracket types are mixed together? For example:

P[DD+s}S3

In cases like this, the opening bracket will complete up until a non-matching closing bracket. The closing bracket will then complete up until the start of the string. This means our above example will turn into:

{P[DD+s]}S3

More concisely:

[S]can left to right, maintaining a stack of open brackets. If I meet a non-matching closing bracket, close the open one(s) until they match or stack is empty. If the stack is empty, put a matching open bracket at the beginning instead. If the stack is nonempty at the end of the string, close all of them. ~ Bubbler

The Challenge

Given a string of potentially unmatched brackets, autocomplete the brackets as described above.

Test Cases

Input -> Output
[3+H --> [3+H]
{0L100R3 --> {0L100R3}
H+4} --> {H+4}
P[DD+s}S3 --> {P[DD+s]}S3
3+HH} --> {3+HH}
{abc --> {abc}
(3..12)S4] --> [(3..12)S4]
[0L100 --> [0L100]
A[BC}D --> {A[BC]}D
x{yz]a --> [x{yz}]a
[AbC] --> [AbC]
{12345678} --> {12345678}
A[bc} --> {A[bc]}
X{yz] --> [X{yz}]
'Hello, World!' --> 'Hello, World!'
AB(CD{EF]GH --> [AB(CD{EF}]GH
AB(CD}EF]GH --> [{AB(CD}EF]GH
AB[CD{EF]GH --> AB[CD{EF}]GH
AB[CD[EF}GH --> {AB[CD[EF]]}GH
AB{CD]EF]GH --> [[AB{CD}]EF]GH
A[bc --> A[bc]
A{bc --> A{bc}
[ --> []
{ --> {}
] --> []
} --> {}
 --> 

Note that the last test case represents a literally empty string.

Rules

• Input can be taken in any convenient and reasonable format.
• Output can be given in any convenient and reasonable format.
• The input string will be limited to printable ASCII characters, although it may be empty.
• An ungolfed reference program can be found here

Scoring

Of course, this is code golf, so the answer in each language consisting of the fewest number of bytes wins. Happy golfings!

Leaderboards

Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

# Language Name, N bytes

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

# Ruby, <s>104</s> <s>101</s> 96 bytes

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:

# Perl, 43 + 2 (-p flag) = 45 bytes

You can also make the language name a link which will then show up in the leaderboard snippet:

# [><>](http://esolangs.org/wiki/Fish), 121 bytes

var QUESTION_ID=198087;
var OVERRIDE_USER=78850;
var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;function answersUrl(d){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+d+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(d,e){return"https://api.stackexchange.com/2.2/answers/"+e.join(";")+"/comments?page="+d+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(d){answers.push.apply(answers,d.items),answers_hash=[],answer_ids=[],d.items.forEach(function(e){e.comments=[];var f=+e.share_link.match(/\d+/);answer_ids.push(f),answers_hash[f]=e}),d.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(d){d.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),d.has_more?getComments():more_answers?getAnswers():process()}})}getAnswers();var SCORE_REG=function(){var d=String.raw`h\d`,e=String.raw`\-?\d+\.?\d*`,f=String.raw`[^\n<>]*`,g=String.raw`<s>${f}</s>|<strike>${f}</strike>|<del>${f}</del>`,h=String.raw`[^\n\d<>]*`,j=String.raw`<[^\n<>]+>`;return new RegExp(String.raw`<${d}>`+String.raw`\s*([^\n,]*[^\s,]),.*?`+String.raw`(${e})`+String.raw`(?=`+String.raw`${h}`+String.raw`(?:(?:${g}|${j})${h})*`+String.raw`</${d}>`+String.raw`)`)}(),OVERRIDE_REG=/^Override\s*header:\s*/i;function getAuthorName(d){return d.owner.display_name}function process(){var d=[];answers.forEach(function(n){var o=n.body;n.comments.forEach(function(q){OVERRIDE_REG.test(q.body)&&(o="<h1>"+q.body.replace(OVERRIDE_REG,"")+"</h1>")});var p=o.match(SCORE_REG);p&&d.push({user:getAuthorName(n),size:+p[2],language:p[1],link:n.share_link})}),d.sort(function(n,o){var p=n.size,q=o.size;return p-q});var e={},f=1,g=null,h=1;d.forEach(function(n){n.size!=g&&(h=f),g=n.size,++f;var o=jQuery("#answer-template").html();o=o.replace("{{PLACE}}",h+".").replace("{{NAME}}",n.user).replace("{{LANGUAGE}}",n.language).replace("{{SIZE}}",n.size).replace("{{LINK}}",n.link),o=jQuery(o),jQuery("#answers").append(o);var p=n.language;p=jQuery("<i>"+n.language+"</i>").text().toLowerCase(),e[p]=e[p]||{lang:n.language,user:n.user,size:n.size,link:n.link,uniq:p}});var j=[];for(var k in e)e.hasOwnProperty(k)&&j.push(e[k]);j.sort(function(n,o){return n.uniq>o.uniq?1:n.uniq<o.uniq?-1:0});for(var l=0;l<j.length;++l){var m=jQuery("#language-template").html(),k=j[l];m=m.replace("{{LANGUAGE}}",k.lang).replace("{{NAME}}",k.user).replace("{{SIZE}}",k.size).replace("{{LINK}}",k.link),m=jQuery(m),jQuery("#languages").append(m)}}

body{text-align:left!important}#answer-list{padding:10px;float:left}#language-list{padding:10px;float:left}table thead{font-weight:700}table td{padding:5px}
#language-list h2{color:#215F06}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="https://cdn.sstatic.net/Sites/codegolf/primary.css?v=f52df912b654"> <div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td><a href="{{LINK}}">{{SIZE}}</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td><a href="{{LINK}}">{{SIZE}}</a></td></tr></tbody> </table>

Answer 1

Charcoal, 74 68 bytes

ＦＳ«Ｗ∧υ›№]}ι⁼§υ±¹ι≔⁺ω⊟υω≔⁺ωιω≡ι]Ｆ¬∧υ⊟υ≔⁺[ωω}Ｆ¬∧υ⊟υ≔⁺{ωω[⊞υ]¦{⊞υ}»ω↑⮌υ

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

ＦＳ«

Loop over the characters of the input.

Ｗ∧υ›№]}ι⁼§υ±¹ι≔⁺ω⊟υω

If the current character is a closing bracket and we're expecting the other sort of closing bracket then append that bracket now. Keep doing this until we run out of other closing brackets to insert.

≔⁺ωιω

Append the current character.

≡ι]Ｆ¬∧υ⊟υ≔⁺[ωω}Ｆ¬∧υ⊟υ≔⁺{ωω[⊞υ]¦{⊞υ}

Switch on the current character. If it's a closing bracket, then remove the (now) matching closing bracket, but if that can't be done then prepend the desired matching opening bracket. If it's an opening bracket, then just save the desired matching closing bracket.

»ω↑⮌υ

After all the characters have been processed, output the processed characters (now including autocompleted missing opening brackets and wrong closing brackets), and then any remaining missing closing brackets.

Answer 2

JavaScript (ES6),  145  142 bytes

s=>[...s].map(c=>o+=(i=(S='[]{}').indexOf(c)^1)&1?(s=S[i]+s,c):i<0?c:(g=_=>s?(C=s[s=s.slice(1),0])==c?c:C+g():(p=S[i]+p,c))(),s=o=p='')&&p+o+s

Try it online!

Answer 3

Retina 0.8.2, 269 bytes

\[(\[(?=.*(]))|\{(?=.*(?<2>}))|[^][}{]|(?<-2>\2))*(?(2)(?!))(?=}|$)
$&]
\{(\[(?=.*(]))|\{(?=.*(?<2>}))|[^][}{]|(?<-2>\2))*(?(2)(?!))(?=]|$)
$&}
^(\[(?=.*(]))|\{(?=.*(?<2>}))|[^][}{]|(?<-2>\2))*(?(2)$)]
[$&
}`^(\[(?=.*(]))|\{(?=.*(?<2>}))|[^][}{]|(?<-2>\2))*(?(2)$)}
{$&

Try it online! Link includes test suite. Explanation: In .NET, the regex (\[(?=.*(]))|\{(?=.*(?<2>}))|[^][}{]|(?<-2>\2))*(?(2)(?!)) matches a string containing only balanced brackets. This is broken down into four alternatives, which are repeated, and then the capture group is checked for emptiness (this can be done more golfily in the latter cases), proving that all brackets have been balanced. It then remains to match the appropriate mismatched brackets and/or start/end and insert the correct matching bracket. Finally, the whole script is repeated using }` until all mismatched brackets have been autocompleted.

\[(?=.*(]))

Match a [ and capture a ] (which happens to be capture group 2).

\{(?=.*(?<2>}))

Match a { and capture a }, but name this capture group 2 as well.

[^][}{]

Match anything that isn't a bracket (under this question's definition).

(?<-2>\2)

Match the last closing bracket that we captured earlier, and then forget that bracket, so that the previous closing bracket becomes the next potential match.

Answer 4

Prolog (SWI), 246 bytes

Input is taken as a list of ASCII character codes while ouput is printed to stdout. The approach is a straightforward translation of the algorithm described in the post into Prolog.

\T:-T+D+[],maplist(put_code,D).
[]+[]+[].
X+[D|U]+S:-X=[],S=[O|Z],D is O+2,X+U+Z;X=[H|T],(D=H,(\+H^`[]{}`,T+U+S;H^`]}`,O is H-2,(S=[O|Z],T+U+Z;S=[],put_code(O),T+U+S);H^`[{`,T+U+[H|S]);S=[O|V],H^`}]`,D^`}]`,H\=D,O is D-2,X+U+V).
A^B:-member(A,B).

Try it online!

Prolog has a special syntax for literal lists of character codes so, invoking the predicate is easy.

?- \`A[bc}`.
{A[bc]}
true .