Removing nested blocks from a string

Question

I wrote this function in scala that uses tail recursion to remove nested blocks from a text.

Usage examples:

removeBlocks("123{456}789", "{", "}") yields "123789"
removeBlocks("123{a{b{c}b}a}789", "{", "}") yields "123789"
removeBlocks("123<div>456</div>789", "<div>", "</div>") yields "123789"
removeBlocks("123<<<div><<<</div>>>789", "<div>", "</div>") yields "123<<>>789"

This is one of my first attempts in a functional language, and I'm deeply dissatistied with my code. It's too long, too nested, and could probably be made more readable. I'm coming from C# and hope to be forgiven for this bad functional code. I'll be happy to hear how it can be improved.

 def removeBlocks(text: String, startMarker: String, endMarker: String) = {
 val startMarkerSize = startMarker.size
 val endMarkerSize = endMarker.size
 val startMarkerHead = startMarker.head
 val endMarkerHead = endMarker.head
 def removeBlocksAcc(s: String, acc: String, nestingLevel: Int): String =
 if (s.isEmpty) acc
 else {
 val (startMarkerCandidate, tail1) = s.splitAt(startMarkerSize)
 if (startMarkerCandidate == startMarker) 
 removeBlocksAcc(tail1, acc, nestingLevel + 1)
 else {
 val (endMarkerCandidate, tail2) = s.splitAt(endMarkerSize)
 if (endMarkerCandidate == endMarker) 
 removeBlocksAcc(tail2, acc, math.max(nestingLevel - 1, 0))
 else {
 val (safePart, candidate) = s.tail.span(c => c != startMarkerHead && c != endMarkerHead)
 if (nestingLevel == 0) 
 removeBlocksAcc(candidate, acc + s.head + safePart, nestingLevel)
 else 
 removeBlocksAcc(candidate, acc, nestingLevel)
 }
 }
 }
 removeBlocksAcc(text, "", 0)
 }

• Ogen: I don't understand your last removeBlocks example. Wouldn't you be left with 123<<<789
• escargot agile: @Ogen, the suffix after the </div> in the input string is ">>789". This is the suffix of the result as well, there's no reason to drop the ">>".
• geoffjentry: Is your goal here to solve the problem in the best manner possible or is it to practice the tailrec construct? I'm not saying the two are necessarily different (only glanced at the problem) but if they are the answers given might not be ideal if the answerer makes the wrong assumption
• escargot agile: @geoffjentry Good question. My primary goal is to solve the problem in the best manner possible.

Answer 1

I think you are trying to do some pattern matching on strings.

So I did this:

def escape(s: String): String = Seq("{", "}", "whatever").foldLeft(s)((x, y) => x.replaceAllLiterally(y, "\\" + y))
def removeBlocks(text: String, open: String, close: String): String = {
 val startReg = (s"${escape(open)}(.*)$$").r
 val endReg = (s"${escape(close)}(.*)$$").r
 val otherText = "(.)(.*)$".r
 @tailrec
 def removeBlocksAux(text: String, acc: String = "", lvl: Int = 0): String = {
 assume((text.length() > 0 || lvl == 0) && lvl >= 0)
 (text, lvl) match {
 case (startReg(text), lvl) => removeBlocksAux(text, acc, lvl + 1)
 case (endReg(text), lvl) => removeBlocksAux(text, acc, lvl - 1)
 case (otherText(c, text), 0) => removeBlocksAux(text, acc + c)
 case (otherText(c, text), lvl) => removeBlocksAux(text, acc, lvl)
 case ("", _) => acc
 }
 }
 removeBlocksAux(text)
}

I tried to find a way to define the regular expressions inside the match group, but I failed at that, it may not be a good idea after all, but I would like to have a more compact and efficient representation for it. The escape function should escape all special cases of operators in Scala regex, that sounds boring, so there may be already a method for that.

I'm also not a big fan of having a function inside a function, but I kept that design decision. Finally, I'd simply use parser combinators for this, but I guess that's not the point.

• escargot agile: Thank you, but regular expressions are just not up to the task. Try this: removeBlocks("123{a{b{c}b}a}456{a}789", "{", "}"). This should give 123456789, but if we replace with (s"${escape(open)}(.*)$$").r, it will leave just 123789. Doing non-greedy matching won't help either.
• Trylks: If you are going to say that my code doesn't work you could at least try to run it before...
• escargot agile: You're right, I'm so sorry! It does work. I was sure there's no solution with regular expressions, but I sloppily missed the fact that your regular expressions don't try to capture the entire block, but only its beginning or end. This is indeed an elegant solution, and it's especially good because it challenged my assumptions. Thank you!

Answer 2

As Illya has mentioned Regex alone cannot solve this problem. Instead, we must employ some type of stack-like data structure to give our program memory of past characters. The first three lines of the main function are just a cheap way to replace blockers with a single character. A better solution would be to tokenize txt so that this isn't necessary.

def removeBlocks(txt: String, startBlocker: String, endBlocker: String): String = {
 val left = "["
 val right = "]"
 val filteredTxt = txt.replace(startBlocker, left).replace(endBlocker, right)
 def func(xs: List[String], stk: List[String]): List[String] = xs match {
 case Nil => Nil
 case `left` :: tail => func(tail, left :: stk)
 case `right` :: tail => func(tail, stk.tail)
 case head :: tail =>
 if (stk.nonEmpty && stk.head == left) 
 func(tail, stk)
 else 
 head :: func(tail, stk)
 }
 func((filteredTxt map(_.toString)).toList, Nil).mkString
}

• escargot agile: Thank you, replacing the blockers with constant one-character strings is a great idea. Now I just need to find two characters that can't appear in the text, or alternatively replace all the occurrences of "[" and "]" with some improbable string, and then replace back in the end.

Answer 3

The simplest thing that comes to mind, provided you're willing to escape special regex chars (like the braces in your examples) yourself (or use Apache Commons, see below) would be this:

def removeBlocks(text: String, startMarker: String, endMarker: String) = {
 val pattern = s"${startMarker}(.*)${endMarker}"
 text.replaceAll(pattern, "")
}
scala> removeBlocks("123<div>456</div>789", "<div>", "</div>")
res20: String = 123789
scala> removeBlocks("123{456}789", "\\{", "\\}")
res19: String = 123789

If you were willing to use Apache Commons, commons lang has StringEscapeUtils which you could use to remove that issue.

• escargot agile: Regex is not strong enough for this task, because regex is a regular language. Try this: removeBlocks("123{a{b{c}b}a}456{a}789", "{", "}"). This should give 123456789, but no regex will do this job well.
• geoffjentry: Ack, you're right. It looks like other people are jumping in w/ answers so I'll leave it to them