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>
AB(CD{EF]GH
, the opening parenthesis is left unbalanced? \$\endgroup\$[]
and{}
\$\endgroup\$