Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

9
votes
14answers
1k views

Parentheses sequences in lexicographical order

Challenge Taken from here and also here An n parentheses sequence consists of n (s and n )s. A valid parentheses sequence is ...
15
votes
22answers
3k views

Test if a string is parenthesly balanced

We call a parens group the open paren (, its matching close paren ) and everything inside them. A parens group or string is ...
6
votes
2answers
185 views

What associativity was it again

Non-associative operators (for example the subtraction-operator) often are either left- or right associative, such that one has to write less parentheses. Consider for example the following: $$ a-b-c ...
25
votes
25answers
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 ...
25
votes
25answers
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 ...
26
votes
12answers
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. ...
12
votes
11answers
1k views

Balanced Zero-One Encoding

Task Encode a string that entirely consists of uppercase alphabets (A-Z) using only zeros and ones, using your own favorite scheme. But the rule isn't that simple! ...
13
votes
3answers
452 views

Flatten a Stack Cats program

Stack Cats is a reversible, stack-based language. Its reversible nature makes for somewhat weird loops. This challenge is about the conditional loop (...). When ...
18
votes
9answers
476 views

Fill in the Bracks

Normal brackets ((),[],<> and {}) are nice and ...
8
votes
2answers
357 views

Keep Decoding This Number!

This challenge posed an algorithm for encoding an integer n as another integer r. What follows is a succinct explanation of that ...
11
votes
4answers
224 views

Decode Factor Trees

In case you missed Encode Factor Trees, here is the definition of a Factor Tree: The empty string is 1. Concatenation represents multiplication. A number n enclosed in parentheses (or any ...
19
votes
4answers
840 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 ...
13
votes
7answers
360 views

Encode Factor Trees [duplicate]

I once saw on the xkcd fora a format for expressing numbers in an odd way. In this "factor tree" format: The empty string is 1. Concatenation represents multiplication. A number n enclosed in ...
27
votes
5answers
549 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 ...
21
votes
14answers
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 ...
36
votes
21answers
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 ...
12
votes
3answers
280 views

Quote my quote!

A quotation is "the repetition of one expression as part of another one". In American English, a quotation is surrounded by double-quotation marks ("), as in the previous sentence. However, this rule ...
3
votes
17answers
697 views

Is there an unmatched parenthesis in this String?

Introduction Given a String containing an arithmetic expression, your task is to output a truthy or falsey value based on whether it contains unmatched parentheses. Input Your program should take ...
23
votes
6answers
466 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 ...
22
votes
20answers
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 ...
14
votes
5answers
385 views

Generate all Brain-Flak Snippets

This question is the second of several Brain-flak Birthday challenges designed to celebrate Brain-Flak's first Birthday! You can find more information about Brain-Flak's Birthday here Challenge For ...
25
votes
3answers
1k 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 ...
6
votes
2answers
290 views

Uni-Dimensional String Golf

Introduction You have to simulate playing golf over an input string that represents the green. The 2-character substring () represents the hole, and is guaranteed ...
11
votes
1answer
224 views

Find a balanced Neighborhood

Your task will be to take a balanced-string and a integer representing a Levenshtein distance (the number of characters that have to be inserted, deleted or changed to make one string into another) ...
13
votes
2answers
304 views

Close your tags!

This is based off a previous deleted challenge of mine with the same name Introduction You are tasked with writing a program that returns a truthy or falsey value based on if the input has all its ...
9
votes
4answers
232 views

Equal out bracket types

Based on THIS question. Given a string, replace each bracket ()[]{}<> with a bracket of the appropriate type so that the brackets match, and the nested ...
9
votes
1answer
382 views

Gather the trash

You're looking at an avenue, and someone has left the trash out! You need to write a program to help fix the problem, by putting the trash into trashcans. The task The avenue is made up of a string ...
16
votes
10answers
992 views

Generate all brace-strings of length n

A brace string is defined as a string consisting of the characters *()[] in which braces match correctly: ...
19
votes
10answers
785 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 (), ...
19
votes
9answers
633 views

Balanced triplet brackets

A "triplet bracket" (that I made up for this challenge) is one of the following: (...+...) [...:...] {...|...} <...-...> A balanced triplet bracket string (...
76
votes
91answers
10k 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 ...
30
votes
9answers
1k 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 ...
8
votes
3answers
402 views

Two Symbol Math

Introduction The four basic math operators (+, -, *, /) can be reduced to just two, due to the fact that: x + y = x - (-y) x * y = x / (1/y), y != 0 x * 0 = 0/x ...
7
votes
7answers
404 views

Decompose string into blocks

Your program's input is a string containing whitespaces, parentheses, and other characters. The string is assumed to be parenthesed correctly, i.e. each right parenthesis matches a unique left ...
46
votes
19answers
9k 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 ...
5
votes
11answers
1k views

Recursion bracketed; or Dyck words generation

We already have challenges to check if a string of brackets is fully matched and to count the number of balanced strings. It remains for us to generate these strings, but it will not be so easy… A ...
12
votes
8answers
463 views

Autonest an array

Everybody loves nested lists! However, sometimes it's hard to make a nested list. You have to decide if you want to nest it deeper, or if you need to nest it shallower. So for your challenge, you must ...
9
votes
12answers
923 views

Are the two sets equal

{}is the empty set. You may use () or [] if you choose. We aren't going to rigorously ...
19
votes
8answers
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 ...
55
votes
32answers
5k 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 ...
12
votes
1answer
333 views

Are there brackets in disguise?

Someone's given us a string, but all bracket-like characters have been changed into normal ones, and we don't know which, or even how many there were. All we know is that if ...
24
votes
1answer
447 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....
33
votes
5answers
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 ...
20
votes
3answers
630 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-...
28
votes
14answers
2k 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 ...
36
votes
47answers
6k 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 ...
26
votes
7answers
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, ...
20
votes
10answers
2k views

Bracket balancing

You will be given a (possibly empty) string containing brackets ([{()}]) and any other characters (A-...
11
votes
2answers
471 views

Fully parenthesize expressions

Today your challenge is to produce all possible full parenthesizations of an expression. Your input is a single line of printable ASCII containing one or more terms separated by operators. The input ...
25
votes
9answers
1k 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 ...