Breaking a string expression in operator and operands

Question

Requesting for a code review for a scala implementation.

Problem

Given an expression string made of numbers and operators +,-,/,* , break it in a list of Integer or String.

Example

"1+2+3" --> List(1, "+", 2 , "+", 3)
"+1++2++3" --> List(1, "+", 2 , "+", 3) //unary +
"1+-2+-3" --> List(1, "+", -2 , "+", -3)//unary -
"1--2--3" --> List(1, "-", -2 , "-", -3)
"-2-3*-4/-6" --> List(-2, "-", 3 , "*", -4, "/", 6)

Error checks are not needed for the valid expression, i.e. expression like *, 2+1 or // wont be passed.

Solution

I implemented the solution in Scala 2.13 . Using Either to store Int or String in the result. Wanted to check if I got algo correct for positive cases.

  def breakExpression(s: String): List[Either[Int, String]] = {
    def isValidOperator(op: String): Boolean = List("+", "-", "/", "*").contains(op)
    def isValidNumber(num:String): Boolean = num.forall(_.isDigit)

    def breakByOperator(expression:String,operator: Char): List[String] = {
      expression.split(operator).filter(_.nonEmpty).foldLeft(List.empty[String]) { case (res, e) =>
        res :+ e :+ operator.toString
      }.init
    }

    def breakByUnaryMinusOperator(expression: String): List[Int] =
      expression.split('-').foldLeft((List.empty[(String,Int)], 1)) { case ((resInProgress, multiplier), exp) =>
        if (exp.isEmpty) (resInProgress, -1)
        else  (resInProgress :+ (exp, multiplier), 1)
      }._1.map { x => x._1.toInt * x._2 }

    List('+', '/', '*').foldLeft(List(s)) { case (expressions, op) =>
      expressions flatMap { e =>
        if (isValidOperator(e) || isValidNumber(e)) List(e)
        else  breakByOperator(e, op)
      }
    }.map {
        case ss if isValidNumber(ss) => Left(ss.toInt)
        case ss => Right(ss)
    }.flatMap {
      case Left(s)  => List(Left(s))
      case Right(s) if isValidOperator(s) => List(Right(s))
      case Right(s) =>
        breakByUnaryMinusOperator(s).foldLeft(List.empty[Either[Int, String]]) { case (res, number) =>
          res :+ Left(number) :+ Right("-")
        }.init
    }
  }

Testing

Test cases

  println(breakExpression("2+34/6"))
  println( "2-3*4/6" , " ---> " , breakExpression("2-3*4/6"))
  println("2-3*-4/-6", " ---> ", breakExpression("2-3*-4/-6"))
  println("-2-3*-4/-6", " ---> ", breakExpression("-2-3*-4/-6"))
  println("1+-2--3", " ---> ", breakExpression("1+-2--3"))

I get following result

List(Left(2), Right(+), Left(34), Right(/), Left(6))
(2-3*4/6, ---> ,List(Left(2), Right(-), Left(3), Right(*), Left(4), Right(/), Left(6)))
(2-3*-4/-6, ---> ,List(Left(2), Right(-), Left(3), Right(*), Left(-4), Right(/), Left(-6)))
(-2-3*-4/-6, ---> ,List(Left(-2), Right(-), Left(3), Right(*), Left(-4), Right(/), Left(-6)))
(1+-2--3, ---> ,List(Left(1), Right(+), Left(-2), Right(-), Left(-3)))

Followup Question: What is the best way to introduce error handling for badly formed string expressions.

Answer 1

In Scala strings are sequence of characters; consequently the Iterator methods are available without a previous split.

The super type of both String and Integer is Any. Operating with the super type wrapping the intermediate results with Either monad is redundant.

The operators could be defined in a String and the utility nested methods simplified to test whether the argument is operator or not.

Folding the string to parse might improve algorithmic efficiency.

Characters' index and the accumulator's size could be used to test edge cases.

From the above perspective the implementation would change to following:

def sequencer( parsed : String ) : Seq[Any] = {

      def isOperator(symbol : String) : Boolean = "+-*/".indexOf(symbol) > -1;
      def isNumber(symbol : String) : Boolean = isOperator(symbol) == false;

      parsed.map { _.toString }.zipWithIndex.foldRight(Seq[String]()) {
          case ( (symbol, index), result ) if ( isOperator(symbol) && index == 0) => result.dropRight(1) :+ ( symbol + result(result.size - 1))
          case ( (symbol, index), result ) if ( isNumber(symbol) && result.size > 0 ) => if ( isNumber( result(result.size - 1) ) ) result.dropRight(1) :+ (symbol + result(result.size - 1)) else result :+ symbol 
          case ( (symbol, index), result ) if ( isNumber(symbol) ) => result :+ symbol 
          case ( (symbol, index), result ) if ( isOperator(symbol) && result.size > 0 ) => if ( isOperator( result(result.size - 1) ) ) (result.dropRight(2) :+ (result(result.size - 1) + result(result.size - 2))) :+ symbol else result :+ symbol
          case ( (symbol, index), result ) if ( isOperator(symbol) ) => result :+ symbol 
      }.reverseIterator.map {
          case symbol if ( isOperator(symbol) ) => symbol
          case symbol => symbol.toInt
      }.toSeq;
}

Answer 2

The implementation is eager in that is parsing the entire string to be parsed even for getting only the first operand and on top of it is parsing it several times. Differently described the breakExpression("-2-3*-4/-6").iterator.next() call results in the expression "-2-3*-4/-6" being parsed multiple times.

Something similar happens with transformations accumulating intermediary results, the expression to be parsed is completely parsed even for getting only part of operator and operands.

It is possible to implement a lazy parsing solution. For fun... a pardon, for academic purpose with a lot of syntactic sugar (currying) and design patterns (strategy, chain of responsibility, template method) Iterator#map transformation could temporarily accumulate intermediary results returning empty iterators until sound operands are formed.

def sequencer( parsed : String ) : Iterator[Any] = {
    val result = Diffuser.until(" ").plain;
    (parsed + " ").iterator
                  .map { _.toString }
                  .map { case symbol => result.parse(symbol); }
                  .filter( _.nonEmpty)
                  .flatten
                  .map {
                       case symbol if ( Diffuser.isOperator(symbol) ) => symbol
                       case symbol => symbol.toInt
                  };
}

Delving into details delaying the Iterator#map returns is possible with serial collections, with parallel collections the results are unpredictable.

import scala.collection.mutable.Clearable
import scala.collection.mutable.ArrayDeque;

object Stringer {

    object Diffuser {

        def until(endSymbol : String) : Selector = { Selector(endSymbol); }

        def isOperator(symbol: String) : Boolean = { "+-*/".indexOf(symbol) > -1; }
        private def isNumber(symbol: String) : Boolean = { symbol.trim().length > 0 && isOperator(symbol) == false; }

        class Selector(val endSymbol : String) {

            // template method
            private def enabler(enabled : String => Boolean)(parse : String => Unit)(next : String => Unit)(symbol : String) : Unit = {
                if ( enabled(symbol) ) { parse(symbol); } else { next(symbol); }
            }

            // template method
            private def flusher(enabled : String => Boolean)(parse : () => Iterator[String])(next : String => Iterator[String])(symbol : String) : Iterator[String] = {
                if ( enabled(symbol) ) { parse(); } else { next(symbol); }
            }
            // template method
            private def vainer(flushed : Clearable)(flushee : Iterator[String]) : Iterator[String] = {
                flushed.clear();
                flushee;
            }

            def plain : Diffuser = {

                val buffer = ArrayDeque[String]();
                // strategy
                def vain(result : ArrayDeque[String]) : Iterator[String] = { vainer(result)(Iterator(result.drop(0).mkString)); }
                // strategy
                def diffuser(result : ArrayDeque[String]) : Iterator[String] = { 
                    val remainingSize = result.lastOption
                                              .map { 
                                                   case lastFromResult if isOperator(lastFromResult) => 2 
                                                   case _ => 1
                                               }
                                               .getOrElse(0);
                    if ( result.size > remainingSize) { result.removeHeadWhile( (token) => { result.size > remainingSize } ).iterator } else Iterator.empty;
                }

                // strategy
                def parseNumber(result : ArrayDeque[String])(symbol : String) : Unit = {
                    result.removeLastOption()
                          .map {
                              case lastFromResult if isNumber(lastFromResult.last.toString()) => () => result.addOne(lastFromResult + symbol)
                              case lastFromResult if result.size == 0 => () => result.addOne(lastFromResult + symbol)
                              case lastFromResult if isOperator(lastFromResult) => result.last match {
                                                                                       case beforeLastFromResult if isOperator(beforeLastFromResult) => () => result.addOne(lastFromResult + symbol)
                                                                                       case _ => () => result.addOne(lastFromResult).addOne(symbol);
                                                                                   } 
                          }
                          .getOrElse(() => result.addOne(symbol))();
                }
                // strategy
                def parseOperator(result : ArrayDeque[String])(symbol : String) : Unit = { result.addOne(symbol); }

                // chain of responsability
                val diffuse : String => Iterator[String] = flusher( (symbol) => true )( () => diffuser(buffer) )( (symbol) => { Iterator.empty} );
                val flush :  String => Iterator[String] = flusher( (symbol) => endSymbol.equals(symbol) )( () => vain(buffer) )( diffuse );
            
                // chain of responsibility
                val operator : String => Unit = enabler( (symbol) => isOperator(symbol) )( parseOperator(buffer) )( (symbol) => {} );
                val number : String => Unit = enabler( (symbol) => isNumber(symbol) )( parseNumber(buffer) )( operator );

                Diffuser(number, flush);
            }

            def reversed : Diffuser = {

                val buffer = ArrayDeque[String]();
                // strategy
                def vain(result : ArrayDeque[String]) : Iterator[String] = { vainer(result)(Iterator(result.drop(0).reverse.mkString)); }
                // strategy
                def diffuser(result : ArrayDeque[String]) : Iterator[String] = { 

                    val remainingSize = result.lastOption
                                              .map { 
                                                   case lastFromResult if isOperator(lastFromResult) => 2 
                                                   case _ => 1
                                               }
                                               .getOrElse(0);
                    if ( result.size > remainingSize) { result.removeHeadWhile( (token) => { result.size > remainingSize } ).iterator } else Iterator.empty;
                }

                // strategy
                def parseNumber(result : ArrayDeque[String])(symbol : String) : Unit = {
                    result.removeLastOption()
                          .map {
                              case lastFromResult if isNumber(lastFromResult.last.toString()) => () => { result.addOne(symbol + lastFromResult); }
                              case lastFromResult => () => { result.addOne(lastFromResult).addOne(symbol); }
                          }
                          .getOrElse( () => { result.addOne(symbol); } )();
                }

                // strategy
                def parseOperator(result : ArrayDeque[String])(symbol : String) : Unit = {
                    result.removeLastOption()
                          .map {
                              case lastFromResult if isOperator(lastFromResult) => {
                                  result.removeLastOption()
                                        .map {
                                            case beforeLastFromResult => () => { result.addOne(lastFromResult + beforeLastFromResult).addOne(symbol); }
                                        }
                                        .getOrElse( () => { result.addOne(lastFromResult); } );
                              }
                              case lastFromResult => () => { result.addOne(lastFromResult).addOne(symbol); }
                          }
                          .getOrElse( () => { result.addOne(symbol); } )();
                }

                // chain of responsibility
                val diffuse : String => Iterator[String] = flusher( (symbol) => true )( () => diffuser(buffer) )( (symbol) => { Iterator.empty; } );
                val flush : String => Iterator[String] = flusher( (symbol) => endSymbol.equals(symbol) )( () => vain(buffer) )( diffuse );

                // chain of responsibilty
                val operator : String => Unit = enabler( (symbol) => isOperator(symbol) )( parseOperator(buffer) )( (symbol) => {} );
                val number : String => Unit = enabler( (symbol) => isNumber(symbol) )( parseNumber(buffer) )( operator );

                Diffuser(number, flush);
            }
        }
    }

    class Diffuser(val number : String => Unit, val flush : String => Iterator[String] ) {

        def parse(symbol : String) : Iterator[String] = {
            number(symbol);
            flush(symbol);
        }
    }

    def sequencer( parsed : String ) : Iterator[Any] = {
        val result = Diffuser.until(" ").plain;
        (parsed + " ").iterator
                .map { _.toString }
                .map { case symbol => result.parse(symbol); }
                .filter( _.nonEmpty)
                .flatten
                .map {
                     case symbol if ( Diffuser.isOperator(symbol) ) => symbol
                     case symbol => symbol.toInt
                };
    }

    def sequencerReversed( parsed : String ) : Iterator[Any] = {
          val result = Diffuser.until(" ").reversed;
          (" " + parsed).reverseIterator
                .map { _.toString }
                .map { case symbol => result.parse(symbol); }
                .filter( _.nonEmpty)
                .flatten
                .map {
                     case symbol if ( Diffuser.isOperator(symbol) ) => symbol
                     case symbol => symbol.toInt
                };
    }

    def main(args : Array[String]) : Unit = {
        //println(sequencerReversed("-21-31111*-41/-61").next());
        //sequencerReversed("-21-31111*-41/-61").foreach( println _ );
        println(sequencer("-21-31111*-41/-61").next());
    }
}

Answer 3

Add modulo, or reminder, operator % to improve the list of operators.

List("+", "-", "/", "*", "%")

... and one more thing, add a method for example called diffuse to the Iterator class to simplify the code:

def main(args : Array[String]) : Unit = {
    val result = Diffuser.until(" ").plain;
    "-21-31111*-41/-61%2 ".map { _.toString }
                          .iterator
                          .diffuse { case symbol => result.parse(symbol) }
                          .filter( _.nonEmpty)
                          .flatten
                          .foreach( println _ );
}

Adding on the fly methods to existing classes is available in Scala language with the help of implicit classes, similar with the Buoyant class from the following:

import Buoyant._;

object Stringer {

    def main(args : Array[String]) : Unit = {

        println("plain diffusing...");

        val result = Diffuser.until(" ").plain;
        "-21-31111*-41/-61%2 ".map { _.toString }
                           .iterator
                           .diffuse { case symbol => result.parse(symbol) }
                           .filter( _.nonEmpty)
                           .flatten
                           .foreach( println _ );
        
        println("---------------------");
        
        println("reversed diffusing...");

        val resultReversed = Diffuser.until(" ").reversed;
        println(" -21-31111*-41/-61%2".map { _.toString }
                           .reverseIterator
                           .diffuse { case symbol => resultReversed.parse(symbol) }
                           .filter( _.nonEmpty)
                           .flatten
                           .next());
    }
    
    object Diffuser {
    
        def until(endSymbol : String) : Selector = { Selector(endSymbol); }
    
        def isOperator(symbol: String) : Boolean = { "+-*/%".indexOf(symbol) > -1; }
    
        class Selector(val endSymbol : String) {
        
            import scala.collection.mutable.Clearable
            import scala.collection.mutable.ArrayDeque;

            private def isNumber(symbol: String) : Boolean = { symbol.trim().length > 0 && isOperator(symbol) == false; }  
            private def isVoid(symbol: String) : Boolean = { endSymbol.equals(symbol); }
    
            // template method
            private def enabler(enabled : String => Boolean)(parse : String => Unit)(next : String => Unit)(symbol : String) : Unit = {
                if ( enabled(symbol) ) { parse(symbol); } else { next(symbol); }
            }
            private val void : (String => Unit) => String => Unit = enabler( (symbol) => isVoid(symbol) )( (symbol) => {} );
    
            // template method
            private def flusher(enabled : String => Boolean)(parse : () => Iterator[String])(next : String => Iterator[String])(symbol : String) : Iterator[String] = {
                if ( enabled(symbol) ) { parse(); } else { next(symbol); }
            }
            // template method
            private def vainer(flushed : Clearable)(flushee : Iterator[String]) : Iterator[String] = {
                flushed.clear();
                flushee;
            }

            def plain : Diffuser = {

                val buffer = ArrayDeque[String]();
                // strategy
                def vain(result : ArrayDeque[String]) : Iterator[String] = { vainer(result)(Iterator(result.drop(0).mkString)); }
                // strategy
                def diffuser(result : ArrayDeque[String]) : Iterator[String] = { 
                    val remainingSize = result.lastOption
                                              .map { 
                                                   case lastFromResult if isOperator(lastFromResult) => 2 
                                                   case _ => 1
                                               }
                                               .getOrElse(0);
                    if ( result.size > remainingSize) { result.removeHeadWhile( (token) => { result.size > remainingSize } ).iterator } else Iterator.empty;
                }

                // strategy
                def parseNumber(result : ArrayDeque[String])(symbol : String) : Unit = {
                    result.removeLastOption()
                          .map {
                              case lastFromResult if isNumber(lastFromResult.last.toString()) => () => result.addOne(lastFromResult + symbol)
                              case lastFromResult if result.size == 0 => () => result.addOne(lastFromResult + symbol)
                              case lastFromResult if isOperator(lastFromResult) => result.last match {
                                                                                       case beforeLastFromResult if isOperator(beforeLastFromResult) => () => result.addOne(lastFromResult + symbol)
                                                                                       case _ => () => result.addOne(lastFromResult).addOne(symbol);
                                                                                   } 
                          }
                          .getOrElse(() => result.addOne(symbol))();
                }
                // strategy
                def parseOperator(result : ArrayDeque[String])(symbol : String) : Unit = { result.addOne(symbol); }

                // chain of responsability
                val diffuse : String => Iterator[String] = flusher( (symbol) => true )( () => diffuser(buffer) )( (symbol) => { Iterator.empty} );
                val flush :  String => Iterator[String] = flusher( (symbol) => isVoid(symbol) )( () => vain(buffer) )( diffuse );
            
                // chain of responsibility
                val operator : String => Unit = enabler( (symbol) => isOperator(symbol) )( parseOperator(buffer) )( (symbol) => {} );
                val number : String => Unit = enabler( (symbol) => isNumber(symbol) )( parseNumber(buffer) )( operator );

                Diffuser(void(number), flush);
            }

            def reversed : Diffuser = {

                val buffer = ArrayDeque[String]();
                // strategy
                def vain(result : ArrayDeque[String]) : Iterator[String] = { vainer(result)(Iterator(result.drop(0).reverse.mkString)); }
                // strategy
                def diffuser(result : ArrayDeque[String]) : Iterator[String] = { 

                    val remainingSize = result.lastOption
                                              .map { 
                                                   case lastFromResult if isOperator(lastFromResult) => 2 
                                                   case _ => 1
                                               }
                                               .getOrElse(0);
                    if ( result.size > remainingSize) { result.removeHeadWhile( (token) => { result.size > remainingSize } ).iterator } else Iterator.empty;
                }

                // strategy
                def parseNumber(result : ArrayDeque[String])(symbol : String) : Unit = {
                    result.removeLastOption()
                          .map {
                              case lastFromResult if isNumber(lastFromResult.last.toString()) => () => { result.addOne(symbol + lastFromResult); }
                              case lastFromResult => () => { result.addOne(lastFromResult).addOne(symbol); }
                          }
                          .getOrElse( () => { result.addOne(symbol); } )();
                }

                // strategy
                def parseOperator(result : ArrayDeque[String])(symbol : String) : Unit = {
                    result.removeLastOption()
                          .map {
                              case lastFromResult if isOperator(lastFromResult) => {
                                  result.removeLastOption()
                                        .map {
                                            case beforeLastFromResult => () => { result.addOne(lastFromResult + beforeLastFromResult).addOne(symbol); }
                                        }
                                        .getOrElse( () => { result.addOne(lastFromResult); } );
                              }
                              case lastFromResult => () => { result.addOne(lastFromResult).addOne(symbol); }
                          }
                          .getOrElse( () => { result.addOne(symbol); } )();
                }

                // chain of responsibility
                val diffuse : String => Iterator[String] = flusher( (symbol) => true )( () => diffuser(buffer) )( (symbol) => { Iterator.empty; } );
                val flush : String => Iterator[String] = flusher( (symbol) => isVoid(symbol) )( () => vain(buffer) )( diffuse );

                // chain of responsibilty
                val operator : String => Unit = enabler( (symbol) => isOperator(symbol) )( parseOperator(buffer) )( (symbol) => {} );
                val number : String => Unit = enabler( (symbol) => isNumber(symbol) )( parseNumber(buffer) )( operator );

                Diffuser(void(number), flush);
            }
        }
    }

    class Diffuser(val number : String => Unit, val flush : String => Iterator[String] ) {

        def parse(symbol : String) : Iterator[String] = {
            println("parsing symbol " + symbol);
            number(symbol);
            flush(symbol);
        }
    }
}

object Buoyant {
    implicit class DiffusingIterator[A](enhancee : Iterator[A]) {
    
        def diffuse[B](op : A => B) : Iterator[B] = { 
            new scala.collection.AbstractIterator[B] {
                override def knownSize = enhancee.knownSize
                def hasNext = enhancee.hasNext
                def next() = op(enhancee.next())
            }
        }
    }

}

This is an informal way to say all in all there are various perspectives to review the code and it might be useful to approach the review activity incrementaly.

Answer 4

When parsing collecting the results should be avoided. Since the length of arguments to be parsed could be considerable the operation could raise an OutOfMemoryError. Instead just return the Iterator.

def sequencer( parsed : String ) : Iterator[Any] = {

  def isOperator(symbol : String) : Boolean = "+-*/".indexOf(symbol) > -1;
  def isNumber(symbol : String) : Boolean = isOperator(symbol) == false;

  var result = Seq(parsed.last.toString());

  parsed.substring(0, parsed.length() - 1)
        .map { _.toString }
        .zipWithIndex
        .foldRight(result) {
             case ( (symbol, index), result ) if ( index == 0) => result.dropRight(1) :+ ( symbol + result(result.size - 1))
             case ( (symbol, index), result ) if ( isNumber(symbol) ) => if ( isNumber( result(result.size - 1) ) ) result.dropRight(1) :+ (symbol + result(result.size - 1)) else result :+ symbol 
             case ( (symbol, index), result ) if ( isOperator(symbol) ) => if ( isOperator( result(result.size - 1) ) ) (result.dropRight(2) :+ (result(result.size - 1) + result(result.size - 2))) :+ symbol else result :+ symbol
        }
        .reverseIterator
        .map {
             case symbol if ( isOperator(symbol) ) => symbol
             case symbol => symbol.toInt
        };
}

Answer 5

In Scala map, fold, reduce and the derivative transformations are lazy, they are evaluated when a terminal operation is called. Among terminal operations is toList method called to convert the result to the return type of breakByUnaryMinusOperator method. Changing the return type of breakByUnaryMinusOperator method from List to Iterator leverages build of lazy pipelines. Without going into details _{I only have a vague idea about} lazy pipelines are resources friendly.

Answer 6

Wanted to check if I got algo correct for positive cases.

Indeed you did and it can be improved considering:

• Edge case of memory size: collecting intermediary results the memory requirements will be at least double memory size of string to be parsed which is a hard requirement that cannot be avoided neither without collecting intermediary results since from a different perspective an edge case is String of digits. Consequently when parsing strings any solution is evenly usable including fold transformations that collect intermediary results. The memory size edge case can be avoided only when available resources suffice.

• Edge case of string's head and last characters: strings are indexed collection of characters, using the index the edge case of head and last characters can be accommodated.

• Returning the resulted Iterator instead of a Collection removes the redundant conversion between Iterator and Collection (Iterator -> Collection -> Iterator). Strings are immutable and stored in a string pool so either returning the Iterator or the Collection has low influence on memory requirements.

def sequencer( parsed : String ) : Iterator[Any] = {

  def isOperator(symbol : String) : Boolean = "+-*/".indexOf(symbol) > -1;
  def isNumber(symbol : String) : Boolean = isOperator(symbol) == false;

  val lastIndex = parsed.length - 1;
  val result = Seq(parsed.head.toString());

  parsed.substring(1)
        .map { _.toString }
        .zipWithIndex
        .foldLeft(result) {
             case ( result, (symbol, index) ) if ( index == lastIndex) => result.dropRight(1) :+ (symbol + result(result.size - 1))
             case ( result, (symbol, index) ) if ( isNumber(symbol) ) => if ( isNumber( result(result.size - 1) ) ) result.dropRight(1) :+ (result(result.size - 1) + symbol) else if ( result.size == 1 ) result.dropRight(1) :+ result(result.size - 1) + symbol else if (isOperator(result(result.size - 1)) && isOperator(result(result.size - 2)) ) result.dropRight(1) :+ result(result.size - 1) + symbol else result :+ symbol
             case ( result, (symbol, index) ) if ( isOperator(symbol) ) => result :+ symbol
    }
    .map {
         case symbol if ( isOperator(symbol) ) => symbol
         case symbol => symbol.toInt
    }
    .iterator;
}

Answer 7

Requesting for a code review for a scala implementation.
.
.
.
Wanted to check if I got algo correct for positive cases.
.
.
.
Followup Question: What is the best way to introduce error handling for badly formed string expressions.

Are you interested also in what could be improved or you're looking for a confirmation you are on the right track and how to keep on?

The question should be rephrased in a way it express what the review's result has to be.

...whatever. Without information about style guides to follow I would say the implementation seems crowded and the absence of curly brackets turns it into a cumbersome lecture. Besides spacing to use mentioned by the style guides to follow the readability could further more be improved with various notations the language offers, a flavour of it being using for comprehension to iterate through and parse the string's characters:

def comprehension( parsed : String ) : Iterator[Any] = {
        val diffuser = Diffuser.until(" ").plain;
        (for symbol <- (parsed + " ") yield diffuser.parse(symbol.toString()))
        .filter( _.nonEmpty)
        .flatten
        .iterator
        .map {
             case symbol if ( Diffuser.isOperator(symbol) ) => symbol
             case symbol => symbol.toInt
        };
    }

... and following is the boiler plate code so the above flavour compile and runs with the proper Scala version:

object Stringer {

    object Diffuser {

        def until(endSymbol : String) : Selector = { Selector(endSymbol); }

        def isOperator(symbol: String) : Boolean = { "+-*/".indexOf(symbol) > -1; }

        class Selector(val endSymbol : String) {

            import scala.collection.mutable.Clearable
            import scala.collection.mutable.ArrayDeque;

            private def isNumber(symbol: String) : Boolean = { symbol.trim().length > 0 && isOperator(symbol) == false; }  
            private def isVoid(symbol: String) : Boolean = { endSymbol.equals(symbol); }

            // template method
            private def enabler(enabled : String => Boolean)(parse : String => Unit)(next : String => Unit)(symbol : String) : Unit = {
                if ( enabled(symbol) ) { parse(symbol); } else { next(symbol); }
            }
            private val void : (String => Unit) => String => Unit = enabler( (symbol) => isVoid(symbol) )( (symbol) => {} );

            // template method
            private def flusher(enabled : String => Boolean)(parse : () => Iterator[String])(next : String => Iterator[String])(symbol : String) : Iterator[String] = {
                if ( enabled(symbol) ) { parse(); } else { next(symbol); }
            }
            // template method
            private def vainer(flushed : Clearable)(flushee : Iterator[String]) : Iterator[String] = {
                flushed.clear();
                flushee;
            }

            def plain : Diffuser = {

                val buffer = ArrayDeque[String]();
                // strategy
                def vain(result : ArrayDeque[String]) : Iterator[String] = { vainer(result)(Iterator(result.drop(0).mkString)); }
                // strategy
                def diffuser(result : ArrayDeque[String]) : Iterator[String] = { 
                    val remainingSize = result.lastOption
                                              .map { 
                                                   case lastFromResult if isOperator(lastFromResult) => 2 
                                                   case _ => 1
                                               }
                                               .getOrElse(0);
                    if ( result.size > remainingSize) { result.removeHeadWhile( (token) => { result.size > remainingSize } ).iterator } else { Iterator.empty; }
                }

                // strategy
                def parseNumber(result : ArrayDeque[String])(symbol : String) : Unit = {
                    result.removeLastOption()
                          .map {
                              case lastFromResult if isNumber(lastFromResult.last.toString()) => () => result.addOne(lastFromResult + symbol)
                              case lastFromResult if result.size == 0 => () => result.addOne(lastFromResult + symbol)
                              case lastFromResult if isOperator(lastFromResult) => result.last match {
                                                                                   case beforeLastFromResult if isOperator(beforeLastFromResult) => () => result.addOne(lastFromResult + symbol)
                                                                                       case _ => () => result.addOne(lastFromResult).addOne(symbol);
                                                                                  } 
                          }
                          .getOrElse(() => result.addOne(symbol))();
                }
                // strategy
                def parseOperator(result : ArrayDeque[String])(symbol : String) : Unit = { result.addOne(symbol); }

                // chain of responsability
                val diffuse : String => Iterator[String] = flusher( (symbol) => true )( () => diffuser(buffer) )( (symbol) => { Iterator.empty} );
                val flush :  String => Iterator[String] = flusher( (symbol) => isVoid(symbol) )( () => vain(buffer) )( diffuse );
            
                // chain of responsibility
                val operator : String => Unit = enabler( (symbol) => isOperator(symbol) )( parseOperator(buffer) )( (symbol) => {} );
                val number : String => Unit = enabler( (symbol) => isNumber(symbol) )( parseNumber(buffer) )( operator );

                Diffuser(void(number), flush);
            }

            def reversed : Diffuser = {

                val buffer = ArrayDeque[String]();
                // strategy
                def vain(result : ArrayDeque[String]) : Iterator[String] = { vainer(result)(Iterator(result.drop(0).reverse.mkString)); }
                // strategy
                def diffuser(result : ArrayDeque[String]) : Iterator[String] = { 

                    val remainingSize = result.lastOption
                                              .map { 
                                                   case lastFromResult if isOperator(lastFromResult) => 2 
                                                   case _ => 1
                                               }
                                               .getOrElse(0);
                    if ( result.size > remainingSize) { result.removeHeadWhile( (token) => { result.size > remainingSize } ).iterator } else Iterator.empty;
                }

                // strategy
                def parseNumber(result : ArrayDeque[String])(symbol : String) : Unit = {
                    result.removeLastOption()
                          .map {
                              case lastFromResult if isNumber(lastFromResult.last.toString()) => () => { result.addOne(symbol + lastFromResult); }
                              case lastFromResult => () => { result.addOne(lastFromResult).addOne(symbol); }
                          }
                          .getOrElse( () => { result.addOne(symbol); } )();
                }

                // strategy
                def parseOperator(result : ArrayDeque[String])(symbol : String) : Unit = {
                    result.removeLastOption()
                          .map {
                              case lastFromResult if isOperator(lastFromResult) => {
                                  result.removeLastOption()
                                        .map {
                                            case beforeLastFromResult => () => { result.addOne(lastFromResult + beforeLastFromResult).addOne(symbol); }
                                        }
                                        .getOrElse( () => { result.addOne(lastFromResult); } );
                              }
                              case lastFromResult => () => { result.addOne(lastFromResult).addOne(symbol); }
                          }
                          .getOrElse( () => { result.addOne(symbol); } )();
                }

                // chain of responsibility
                val diffuse : String => Iterator[String] = flusher( (symbol) => true )( () => diffuser(buffer) )( (symbol) => { Iterator.empty; } );
                val flush : String => Iterator[String] = flusher( (symbol) => isVoid(symbol) )( () => vain(buffer) )( diffuse );

                // chain of responsibilty
                val operator : String => Unit = enabler( (symbol) => isOperator(symbol) )( parseOperator(buffer) )( (symbol) => {} );
                val number : String => Unit = enabler( (symbol) => isNumber(symbol) )( parseNumber(buffer) )( operator );

                Diffuser(void(number), flush);
            }
        }
    }

    class Diffuser(val number : String => Unit, val flush : String => Iterator[String] ) {

        def parse(symbol : String) : Iterator[String] = {
            number(symbol);
            flush(symbol);
        }
    }

    def comprehension( parsed : String ) : Iterator[Any] = {
        val diffuser = Diffuser.until(" ").plain;
        (for symbol <- (parsed + " ") yield diffuser.parse(symbol.toString()))
        .filter( _.nonEmpty)
        .flatten
        .iterator
        .map {
             case symbol if ( Diffuser.isOperator(symbol) ) => symbol
             case symbol => symbol.toInt
        };
    }

    def comprehensionReversed( parsed : String ) : Iterator[Any] = {
        val diffuser = Diffuser.until(" ").reversed;
        (for symbol <- (" " + parsed).reverse yield diffuser.parse(symbol.toString()))
        .filter( _.nonEmpty)
        .flatten
        .iterator
        .map {
             case symbol if ( Diffuser.isOperator(symbol) ) => symbol
             case symbol => symbol.toInt
        };
    }

    def main(args : Array[String]) : Unit = {
        comprehensionReversed("-21-31111*-41/-61").foreach( println _ );
        //println(comprehension("-21-31111*-41/-61").next());
    }
}