Buiding a stack in a map

Question

I have a string that looks like this:

 "7-6-4-1"

or

"7"

or

""

That is, a set of numbers separated by -. There may be zero or more numbers.

I want to return a stack with the numbers pushed on in that order (i.e. push 7 first and 1 ast, for the first example)

If I just wanted to return a list I could just go str.split("-").map{_.toInt} (although this doesn't work on the empty string)/

There's no toStack to convert to a Stack though. So currently, I have

  {
    val s = new Stack[Int]; 
    if (x.nonEmpty)
        x.split('-').foreach {
    y => s.push(y.toInt)
      }
   s
   }

Which works, but is pretty ugly. What am I missing?

EDIT: Thanks to all the responders, I learnt quite a bit from this discussion

Rex Kerr · Accepted Answer · 2010-12-06T17:42:19.323

5

Stack(x.split("-").map(_.toInt).reverse: _*)

The trick here is to pass the array you get from split into the Stack companion object builder. By default the items go in in the same order as the array, so you have to reverse the array first.

Note the "treat this is a list, not as a single item" annotation, : _*.

Edit: if you don't want to catch the empty string case separately, like so (use the bottom one for mutable stacks, the top for immutable):

if (x.isEmpty) Stack() else Stack(x.split("-").map(_.toInt).reverse: _*)
if (x.isEmpty) Stack[Int]() else Stack(x.split("-").map(_.toInt).reverse: _*)

then you can filter out empty strings:

Stack(x.split("-").filterNot(_.isEmpty).map(_.toInt).reverse: _*)

which will also "helpfully" handle things like 7-9----2-2-4 for you (it will give Stack(4,2,2,9,7)).

If you want to handle even more dastardly formatting errors, you can

val guard = scala.util.control.Exception.catching[Int](classOf[NumberFormatException])
Stack(x.split("-").flatMap(x => guard.opt(x.toInt)).reverse: _*)

to return only those items that actually can be parsed.

edited Dec 06 '10 at 17:42

answered Dec 06 '10 at 16:14

Rex Kerr

166,841
26
322
407

Thanks. I still need the nonEmpty check for x? – The Archetypal Paul Dec 06 '10 at 16:18
1

@Paul yes, nonEmpty check is not there – Vasil Remeniuk Dec 06 '10 at 16:22
`x => {Stack(x.split("-").collect{case x if x.nonEmpty => x.toInt}.reverse: _*)}` bit. seems to cover the nonEmpty case :) – The Archetypal Paul Dec 06 '10 at 16:34
Yep. Works in my use case. I couldn't work out how to create an return an empty Stack[Int] when checking the first x was empty (my Scala is stil at the "change things semi-randomly until it works" level, unfortunately, and I find the compiler errors for type problems opaque) – The Archetypal Paul Dec 06 '10 at 16:42
@Paul: It will check initial string for emptiness on every iteration, instead of doing it just once at the beginning. – Vasil Remeniuk Dec 06 '10 at 16:42
The problem with `if (x.isEmpty) Stack() else Stack(x.split("-").map(_.toInt).reverse: _*)` is the type returned.It isn't `Stack[Int]` because of the `Stack()`. This causes errors in other methods which need it to be `Stack[Int]` (or at least, that's the only reason I can see for the compiler passing this method OK but givig errors elsewhere) – The Archetypal Paul Dec 06 '10 at 17:03
Take a look at http://stackoverflow.com/questions/4347718/code-golf-towers-of-hanoi/4353239#4353239 to see the entire code – The Archetypal Paul Dec 06 '10 at 17:04
@Paul - The compiler does the right thing (at least with this line on its own or as a `def`); `Stack()` is initially guessed as type `Stack[Nothing]`, but when the other branch of the if comes back as `Stack[Int]`, the result of the whole expression is widened to `Stack[Int]`. – Rex Kerr Dec 06 '10 at 17:10
@Rex Kerr, I'm not sure it is. See the little example I just edited into the bottom of my question – The Archetypal Paul Dec 06 '10 at 17:18
@Paul - Oh, you're using a _mutable_ stack. Sorry, I hadn't caught that. In that case, yes, you need Stack[Int](). – Rex Kerr Dec 06 '10 at 17:41

Vasil Remeniuk · Answer 2 · 2010-12-06T16:46:42.997

3

(Stack[Int]() /: (if(x.isEmpty) Array.empty else x.split("-")))(
                  (stack, value) => 
                      stack.push(value toInt))

edited Dec 06 '10 at 16:46

answered Dec 06 '10 at 16:08

Vasil Remeniuk

20,519
6
71
81

Thanks. It's X that can be empty, not the string once split? and can you explain it a bit? :) – The Archetypal Paul Dec 06 '10 at 16:15
@Paul `foldLeft` is used to recursively populate a new empty stack with the values coming from splitting the string. – Vasil Remeniuk Dec 06 '10 at 16:21

score 3 · Answer 3 · edited May 23 '17 at 12:26

Dont forget the ever handy breakOut which affords slightly better performance than col: _* (see Daniel's excellent explanation)

Used here with Rex Kerr's .filterNot(_.isEmpty) solution:

import scala.collection.immutable.Stack
import scala.collection.breakOut

object StackFromString {

  def stackFromString(str: String): Stack[Int] =
    str.split("-").filterNot(_.isEmpty)
      .reverse.map(_.toInt)(breakOut)

  def main(args: Array[String]): Unit = {
    println(stackFromString("7-6-4-1"))
    println(stackFromString("7"))
    println(stackFromString(""))
  }
}

Will output:

Stack(1, 4, 6, 7)
Stack(7)
Stack()

Buiding a stack in a map

3 Answers3