Questions tagged [balanced-string]
In a balanced string certain pairs of characters or substrings always appear with the same amount. Often there are additional restrictions that those pairs also have to be ordered. The most common example is a correctly parenthesized string. See also the [palindrome] and [syntax] tags.
104
questions
91
votes
119
answers
12k
views
N(e(s(t))) a string
To "function nest" a string, you must:
Treat the first character as a function, and the following characters as the arguments to that function. For example, if the input string was ...
- 59.4k
91
votes
110
answers
13k
views
Count of "a"s and "b"s must be equal. Did you get it computer?
In the popular (and essential) computer science book, An Introduction to Formal Languages and Automata by Peter Linz, the following formal language is frequently stated:
$$\large{L=\{a^n b^n:n\in\...
user55673
85
votes
51
answers
7k
views
Telescopic Parentheses
Consider a non-empty string of correctly balanced parentheses:
(()(()())()((())))(())
We can imagine that each pair of parentheses represents a ring in a ...
- 197k
62
votes
48
answers
7k
views
Are the brackets fully matched?
You must write a program or function that takes a string of brackets and outputs whether or not that string is fully matched. Your program should print a truthy or falsy value, and IO can be in any ...
- 59.4k
46
votes
19
answers
10k
views
Can Pac-Man Eat This String?
In the arcade version of the game, Pac-Man eats pac-dots. However, in this challenge, he's hungry for alphanumeric characters and punctuation in a string.
Your task is to create a function that feeds ...
- 2,995
45
votes
3
answers
3k
views
Enumerate valid Brainf**k programs
Golunar/Unary is a way to encode all valid Brainfuck programs, but it is not an enumeration, since most natural numbers do not correspond to a valid program.
For the purpose of this challenge, assume ...
- 210k
43
votes
57
answers
8k
views
Catalan Numbers
The Catalan numbers (OEIS) are a sequence of natural numbers often appearing in combinatorics.
The nth Catalan number is the number of Dyck words (balanced strings of parenthesis or brackets such as <...
- 11.2k
43
votes
25
answers
4k
views
(A[l(t[e(r)n]e)s]t) a string!
Alternesting, is the act of taking a string and nesting it in alternating brackets. Here is how you alternest a string.
For a string of length N, take the center N characters, and surround them in ...
- 59.4k
43
votes
17
answers
3k
views
{Curly Numbers};
In the esoteric programming language Curly, programs consist solely of curly braces {} and semicolons ;. Despite this humble ...
- 38.8k
41
votes
9
answers
6k
views
"Convenient palindrome" checker
If you've ever tried to write palindromic code before, you'd know how much brackets tend to get in your way. ()() is not a palindrome, even though it kinda looks ...
- 8,816
36
votes
4
answers
2k
views
Code Explanation Formatter
Successful code golf submissions are, by nature, filled with crazy symbols all over the place. To make their submission easier to understand, many code-golfers choose to include an explanation of ...
- 29.1k
35
votes
5
answers
1k
views
Make Bracket Squares
Every programmer knows that brackets []{}()<> are really fun. To exacerbate this fun, groups of interwoven brackets can be transformed into cute and fuzzy ...
- 29.1k
33
votes
10
answers
2k
views
Build a nest
The challenge is simple: write a program or function that, when given a finite non-negative integer, outputs a nested array.
The rules
Your code must produce a unique valid nested array for every ...
- 50.1k
32
votes
40
answers
3k
views
Parenthifiable Binary Numbers
If you express some positive integer in binary with no leading zeros and replace every 1 with a ( and every ...
- 90k
31
votes
19
answers
3k
views
Motzkin Numbers
The nth Motzkin Number is the number of paths from (0, 0) to (n, 0) where each step is of the form (1, -1), (1, 0) or (1, 1), and the path never goes below y = 0.
Here's an illustration of these paths ...
- 42.1k
31
votes
9
answers
1k
views
Interlocking Brackets
Write a program or function that takes in an eight byte string containing one of each of the characters ()[]{}<> arranged in any way such that the four ...
- 90k
29
votes
31
answers
3k
views
Open or Close the Parentheses
Every phone needs a calculator app. Because of the limited screen real estate, the developer of mine has decided to save some buttons. Instead of having two dedicated bracket buttons - one for open <...
- 7,684
28
votes
34
answers
3k
views
Rotate brackets until they're balanced
Take the string of brackets ]][][[. When you rotate it to the right once, you get []][][. If you rotate it again, you get ...
- 18.9k
28
votes
18
answers
2k
views
Find the index of the matching parentheses for each character
The challenge is simple, find the matching parentheses for every one of the parentheses in a given string input
E.g.
()()() -> [1, 0, 3, 2, 5, 4]
Always start ...
- 5,097
28
votes
9
answers
2k
views
Parentheses into Footnotes
Background
LISP programmers have taken over the world!
Parentheses have been declared as sacred characters, and from now on, they can only be used in LISP programs.
It has been decided that ...
- 42.7k
27
votes
12
answers
2k
views
Expand compressed brain-flak
This challenge was posted as part of the April 2018 LotM challenge, as well as for Brain-flak's 2nd birthday
I was thinking about what the most efficient way to encode brain-flak programs would be. ...
- 59.4k
27
votes
5
answers
673
views
Bubble the brackets!
There are a few questions on this site about balancing brackets, and checking whether brackets are balanced. I propose it's now time to use those balanced brackets for something!
In mathematics and ...
- 371
26
votes
25
answers
2k
views
Detect Perfect Pairings
Let's have a function \$f\$ that takes a string and removes all pairs of adjacent identical characters. For example
\$f(a\color{red}{bb}ba\color{red}{cc}) = aba\$
Note that when two pairs overlap ...
- 99.6k
26
votes
17
answers
2k
views
Topographic Strings
Here is some example input, so I can explain what the problem is:
((1 2)(3 (4 5) moo)) (i (lik(cherries)e (woohoo)))
Think of this line of text as a topographic ...
- 4,360
26
votes
11
answers
2k
views
De-Parenthesizing a String
Given a properly-parenthesized string as input, output a list of all nonempty substrings within matching parentheses (or outside of all parentheses), with nested parentheses removed. Each substring ...
- 361
25
votes
25
answers
3k
views
Golf A Parentheses Matching Algorithm
You will be given a string s. It is guaranteed that the string has equal and at least one [s and ...
- 641
25
votes
5
answers
1k
views
Ungolf my tinylisp code
I like golfing in tinylisp:
(d M(q((x)(i x(i(disp x)0(M x))0
But I also like posting explanations with nicely formatted code:
...
- 38.8k
25
votes
7
answers
2k
views
Generating Brainf*** NOPs
Sometimes when writing brainfuck code, you feel the need to make it longer than needed to encourage debugging. You could do it by just plopping a >< in there, ...
- 17.9k
25
votes
6
answers
541
views
Appends or Prepends? Depends
Brain-flak turns one year old tomorrow! In honor of it's birthday, we're having a PPCG style birthday party, where several users post brain-flak related questions! Help us celebrate! :)
Brain-flak is ...
- 59.4k
24
votes
3
answers
2k
views
Balance the Brackets
Your objective: Given a string of brackets, output the minimum Damerau-Levenshtein Distance required to turn the input string into a string where the brackets are balanced.
Input
The input string will ...
- 9,377
24
votes
3
answers
1k
views
Clearly parenthesize APL trains
In APL, you can write tacit functions, called trains. How they work is irrelevant for this challenge. Here are the different ways they can be grouped, using ⍴ as ...
- 40.6k
24
votes
1
answer
506
views
Reverse Engineer Bracket Rectangles
Every programmer knows that rectangles □ are really fun. To exacerbate this fun, these cute and fuzzy diagrams can be transformed into groups of interwoven brackets....
- 29.1k
23
votes
16
answers
4k
views
Remove redundant parentheses
Given a string containing some parentheses and some other ASCII printable characters, like this: (abc((123))(k)) your task is to remove any sets of parentheses that ...
- 13k
23
votes
9
answers
1k
views
Formatting a Lisp-like Syntax
Background
(Based on a true, heart-wrenching story)
In my time, I've played around with Lisp and similar languages often. I've written with them, ran them, interpreted them, designed them, and made ...
- 5,480
23
votes
12
answers
6k
views
How long is this string, really?
In most programming languages, the string Hello, World! can be represented as "Hello, World!". But if you want to ...
- 41.6k
22
votes
22
answers
1k
views
Find the First Bracket Match
This was one of a series of challenges leading up to Brain-Flak's birthday. Find out more here.
Challenge
For this challenge your objective will be to find the very first pair of matching brackets in ...
- 9,377
22
votes
23
answers
4k
views
Verify Brainfuck program
Yet another Brainfuck parsing problem, but this time... different.
You are working in the Infinite Monkeys Incorporated, the company making Brainfuck programs, to solve various interesting problems ...
- 12.1k
21
votes
31
answers
2k
views
Remove oddly nested substrings
Task:
Input will consist of some text, with nested [] separating some of it into nested groups:
...
- 18.9k
21
votes
14
answers
2k
views
Turn a string inside out
A balanced string is a string of parentheses () so that every parenthesis is can be matched with another one. More rigorously they are the strings spanned by this ...
- 99.6k
21
votes
3
answers
777
views
Parenthesize an expression
Recently I've been writing a new language, to avoid needing to handle order of operations, I simply parenthesize each expression properly to avoid this entirely.
Because parenthesis are at char-...
- 29.1k
20
votes
28
answers
3k
views
Rearrange to a palindrome
Given a string, shuffle it so that it becomes a palindrome.
For example, adadbcc can be arranged into dacbcad, or ...
- 41.6k
20
votes
11
answers
4k
views
I'm Lazy: Close my Superparens
Picolisp has a feature called "super parentheses":
Brackets ('[' and ']') can be used as super parentheses. A closing bracket will match [all parentheses to and including] the innermost ...
- 1,488
20
votes
12
answers
2k
views
Evaluating Parentheses and Brackets as Integers
Write a program that takes in a string of the four characters ()[] that satisfies these points:
Every left parenthesis ( has a ...
- 90k
20
votes
9
answers
686
views
Balanced triplet brackets
A "triplet bracket" (that I made up for this challenge) is one of the following:
(...+...)
[...:...]
{...|...}
<...-...>
A balanced triplet bracket string (...
- 37k
19
votes
9
answers
2k
views
Write a brain-flak classic interpreter!
Brain-Flak (a cross between Brainf**k and Flak-Overstow) is a stack-based esoteric language. Since this challenge was posted, the language has evolved and updated, but this first revision of the ...
- 59.4k
19
votes
23
answers
3k
views
Split a string on unnested commas
Create the shortest program/function/whatever that splits an inputted string along un-nested commas. A comma is considered nested if it is either within parentheses, brackets, or braces.
Input and ...
- 2,095
19
votes
13
answers
2k
views
Remove All Smalltalk Comments for Code Golf
Take a line of input (function arguments or stdin, etc.).
Remove comments in it, where a comment starts and ends with ".
Do not remove comments in string ...
- 1,488
19
votes
10
answers
2k
views
Bracket balancing
You will be given a (possibly empty) string containing brackets ([{()}]) and any other characters (A-...
- 3,311
19
votes
10
answers
837
views
A simple number system
Let me tell you about a simple number system. (which I made up just for this challenge)
This system contains the functions (), ...
- 10.6k
18
votes
26
answers
2k
views
Is it a valid list?
Given a string like [[[],[[]]],[]], made of only commas and square brackets, your challenge is to determine whether it represents a list.
A list is either:
...
- 41.6k