Splitting complex String Pattern (without regex) in a functional approach

Question

I am trying to split a string without regex in a more idiomatic functional approach.

case class Parsed(blocks: Vector[String], block: String, depth: Int)

def processChar(parsed: Parsed, c: Char): Parsed = {
  import parsed._
  c match {

    case '|'  if depth == 0
                =>  parsed.copy(block = "", blocks = blocks :+ block ,
                                  depth = depth)                          
    case '['  => parsed.copy(block = block + c,
                                  depth = depth + 1)
    case ']'  if depth == 1
                => parsed.copy( block = "", blocks = blocks :+ (block + c),
                                depth = depth - 1)
    case ']'  => parsed.copy(block = block + c,
                                  depth = depth - 1)
    case _    => parsed.copy(block = block + c)
  }
}

val s = "Str|[ts1:tssub2|ts1:tssub2]|BLANK|[INT1|X.X.X.X|INT2|BLANK |BLANK | |X.X.X.X|[INT3|s1]]|[INT3|INT4|INT5|INT6|INT7|INT8|INT9|INT10|INT11|INT12|INT13|INT14|INT15]|BLANK |BLANK |[s2|s3|s4|INT16|INT17];[s5|s6|s7|INT18|INT19]|[[s8|s9|s10|INT20|INT21]|ts3:tssub3| | ];[[s11|s12|s13|INT21|INT22]|INT23:INT24|BLANK |BLANK ]|BLANK |BLANK |[s14|s15]"
val parsed = s.foldLeft(Parsed(Vector(), "", 0))(processChar)
parsed.blocks.size //20 
parsed.blocks foreach println

I would expect to get the following result (parsed.blocks.size should be 12).

Str
[ts1:tssub2|ts1:tssub2]
BLANK|
[INT1|X.X.X.X|INT2|BLANK |BLANK | |X.X.X.X|[INT3|s1]]
[INT3|INT4|INT5|INT6|INT7|INT8|INT9|INT10|INT11|INT12|INT13|INT14|INT15]
BLANK 
BLANK 
[s2|s3|s4|INT16|INT17];[s5|s6|s7|INT18|INT19]
[[s8|s9|s10|INT20|INT21]|ts3:tssub3| | ];[[s11|s12|s13|INT21|INT22]|INT23:INT24|BLANK |BLANK ]
BLANK 
BLANK 
[s14|s15]

However result I am getting is (parsed.blocks.size is 20)

Str
[ts1:tssub2|ts1:tssub2]

BLANK
[INT1|X.X.X.X|INT2|BLANK|BLANK||X.X.X.X|[INT3|s1]]

[INT3|INT4|INT5|INT6|INT7|INT8|INT9|INT10|INT11|INT12|INT13|INT14|INT15]

BLANK
BLANK
[s2|s3|s4|INT16|INT17]
;[s5|s6|s7|INT18|INT19]

[[s8|s9|s10|INT20|INT21]|ts1:tssub2||]
;[[s11|s12|s13|INT21|INT22]|INT23:INT24|BLANK|BLANK]

BLANK
BLANK
[s14|s15]

To my understanding this is slight variation of parenthesis balancing problem. However in this case ; would mean kind of continuation.

I have two questions in this case

1) How the extra entry /space after [ts1:tssub2|ts1:tssub2] came, also after

[INT1|X.X.X.X|INT2|BLANK|BLANK||X.X.X.X|[INT3|s1]] , [INT3|INT4|INT5|INT6|INT7|INT8|INT9|INT10|INT11|INT12|INT13|INT14|INT15] and ;[[s11|s12|s13|INT21|INT22]|INT23:INT24|BLANK|BLANK]

in my result as well ?

2) Here at the moment [s2|s3|s4|INT16|INT17] and ;[s5|s6|s7|INT18|INT19]

go in as two different entries. However this should be merged as [s2|s3|s4|INT16|INT17];[s5|s6|s7|INT18|INT19]

a single entry[So does

[[s8|s9|s10|INT20|INT21]|ts1:tssub2||]

and

;[[s11|s12|s13|INT21|INT22]|INT23:INT24|BLANK|BLANK])

as well]. Any clues to how to do so ?

"encountered unrecoverable cycle resolving import". What is this `parsed` in the beginning, and what does it have to do with the `val parsed` towards the end? — Andrey Tyukin, Apr 11 '18 at 20:29
Sorry, it's my bad I haven't included the case class and messed the import. Updated the question — Robert Knox, Apr 13 '18 at 13:12
minor-minor detail: I'd still indent the import inside function by two spaces. Scala supports local imports, no reason to align them with the beginning of the line. — Andrey Tyukin, Apr 13 '18 at 13:14
Agreed, have a bad habit of not to indenting imports as you pointed. I guess it's due to extensive Java background. — Robert Knox, Apr 13 '18 at 13:41

score 1 · Accepted Answer · answered Apr 11 '18 at 20:41

Question 1

The extra empty string block appears because the very previous case each time is

case ']'  if depth == 1

It adds an empty block and decreases the depth. Then we have

case '|'  if depth == 0

which also adds another empty block, pushing the previous empty one into the resulting Vector.

Before answering the second question, I would like to suggest another approach to the implementation of this parser, which is slightly more idiomatic. My major criticism about the current one is the usage of an intermediate object (Parsed) to wrap state and copying it in each and every case. Indeed, we do not need it: more frequent approach is to use a recursive function, especially when depth is involved.

So, without modifying significantly the processing of your cases, it can be represented as follows:

def parse(blocks: Seq[String],
          currentBlock: String,
          remaining: String,
          depth: Int): Seq[String] =
  if (remaining.isEmpty) {
    blocks
  } else {
    val curChar = remaining.head
    curChar match {
      case '|' if depth == 0 =>
        parse(blocks :+ currentBlock, "", remaining.tail, depth)
      case '[' =>
        parse(blocks, currentBlock + curChar, remaining.tail, depth + 1)
      case ']' =>
        if (depth == 1)
          parse(blocks :+ (currentBlock + curChar), "", remaining.tail, depth - 1)
        else
          parse(blocks, currentBlock + curChar, remaining.tail, depth - 1)
      case _ =>
        parse(blocks, currentBlock + curChar, remaining.tail, depth)
    }
  }

It produces exactly the same output as the original solution.

To fix the issue with empty blocks, we need to change case '|':

case '|' if depth == 0 =>
  val updatedBlocks = if (currentBlock.isEmpty) blocks
                      else blocks :+ currentBlock
  parse(updatedBlocks, "", remaining.tail, depth)

We just skip the current block if it contains an empty string.

Question 2

To merge the two blocks between ; char, we need to bring back one parsed block and return it into the currentBlock reference. This represents an additional case:

case ';' =>
  parse(blocks.init, blocks.last + curChar, remaining.tail, depth)

Now, after

val result = parse(Seq(), "", s, 0)
result.foreach(println)

The output is

Str
[ts1:tssub2|ts1:tssub2]
BLANK
[INT1|X.X.X.X|INT2|BLANK |BLANK | |X.X.X.X|[INT3|s1]]
[INT3|INT4|INT5|INT6|INT7|INT8|INT9|INT10|INT11|INT12|INT13|INT14|INT15]
BLANK 
BLANK 
[s2|s3|s4|INT16|INT17];[s5|s6|s7|INT18|INT19]
[[s8|s9|s10|INT20|INT21]|ts3:tssub3| | ];[[s11|s12|s13|INT21|INT22]|INT23:INT24|BLANK |BLANK ]
BLANK 
BLANK 
[s14|s15]

And it looks very similar to what you were looking for.

Thanks for the great explanation ! I got your point on the usage of the intermediate object (Parsed). I guess, it would be helpful for your point if few examples could also referenced in the answer. — Robert Knox, Apr 13 '18 at 13:32

Splitting complex String Pattern (without regex) in a functional approach

1 Answers1

Linked