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.

Filter by
Sorted by
Tagged with
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 ...
DJMcMayhem's user avatar
90 votes
108 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\...
user avatar
83 votes
50 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 ...
Martin Ender's user avatar
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 ...
DJMcMayhem's user avatar
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 ...
atlasologist's user avatar
  • 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 ...
Dennis's user avatar
  • 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 <...
a spaghetto's user avatar
  • 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 ...
DJMcMayhem's user avatar
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 ...
algorithmshark's user avatar
36 votes
14 answers
3k views

{Curly Numbers};

In the esoteric programming language Curly, programs consist solely of curly braces {} and semicolons ;. Despite this humble ...
DLosc's user avatar
  • 38.4k
35 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 ...
PhiNotPi's user avatar
  • 29k
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 ...
PhiNotPi's user avatar
  • 29k
33 votes
10 answers
2k views

B​u​i​l​d a n​e​s​t

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 ...
ETHproductions's user avatar
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 ...
Calvin's Hobbies's user avatar
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 ...
isaacg's user avatar
  • 42k
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 ...
Calvin's Hobbies's user avatar
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 <...
Jitse's user avatar
  • 6,896
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 ...
Rydwolf Programs's user avatar
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 ...
DialFrost's user avatar
  • 5,049
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 ...
Zgarb's user avatar
  • 42.6k
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. ...
DJMcMayhem's user avatar
27 votes
5 answers
660 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 ...
Arthur's user avatar
  • 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 ...
Wheat Wizard's user avatar
  • 97.7k
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 ...
redstonerodent's user avatar
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 ...
Windmill Cookies's user avatar
25 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 ...
beary605's user avatar
  • 4,310
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: ...
DLosc's user avatar
  • 38.4k
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, ...
PurkkaKoodari's user avatar
25 votes
6 answers
537 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 ...
DJMcMayhem's user avatar
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 ...
Pavel's user avatar
  • 9,367
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 ...
Erik the Outgolfer's user avatar
24 votes
1 answer
498 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....
PhiNotPi's user avatar
  • 29k
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 ...
mousetail's user avatar
  • 12.4k
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 ...
BrainSteel's user avatar
  • 5,430
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 ...
emanresu A's user avatar
  • 37.1k
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 ...
Pavel's user avatar
  • 9,367
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: ...
Rydwolf Programs's user avatar
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 ...
Wheat Wizard's user avatar
  • 97.7k
21 votes
3 answers
770 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-...
Downgoat's user avatar
  • 28.9k
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 ...
emanresu A's user avatar
  • 37.1k
20 votes
20 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 ...
Kamila Borowska's user avatar
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 ...
Wezl's user avatar
  • 1,458
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 ...
Calvin's Hobbies's user avatar
20 votes
9 answers
683 views

Balanced triplet brackets

A "triplet bracket" (that I made up for this challenge) is one of the following: (...+...) [...:...] {...|...} <...-...> A balanced triplet bracket string (...
jimmy23013's user avatar
  • 36.9k
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 ...
DJMcMayhem's user avatar
19 votes
24 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 ...
Dadsdy's user avatar
  • 2,055
19 votes
10 answers
2k views

Bracket balancing

You will be given a (possibly empty) string containing brackets ([{()}]) and any other characters (A-...
ghosts_in_the_code's user avatar
19 votes
10 answers
835 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 (), ...
Oliver Ni's user avatar
  • 10.6k
18 votes
25 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: ...
emanresu A's user avatar
  • 37.1k
18 votes
14 answers
3k views

Visualize a Recursive Acronym

Background Famously, the acronym GNU stands for GNU's Not Unix. 1 It's recursive because, after expanding it once, it still ...
Jonah's user avatar
  • 33.3k