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.

• RoToRa: Scala isn't my strong point, but I believe you are unnecessarily handling the unitary minus as a special case. Because numbers and operators alternate and operators are all one character long, at the start of the string (or after you found an operator) a - (or +) can't be an operator, but must be the sign of a following number.
• user272945: "Followup Question: What is the best way to introduce error handling for badly formed string expressions." Such requests are off-topic on Code Review. The question could be on-topic on other sites on the Stack Exchange network. You should look for sites with knowledge about operators additivity, internationalised thousands and decimal separators or the proper practice for integers starting with zero, whether zero should be silently dropped or not, being several topics among others to address either while accumulating symbols or before returning operators/operands to the caller.
• CiaPan: The last example seems incorrect to me: "-2-3*-4/-6" --> List(-2, "-", 3 , "*", -4, "/", 6) Shouldn't the resulting list have -6 as the last item?
• CiaPan: @RoToRa What you say depends on whether the sign preceding a number is a prefix, i.e. a leading character of the numeric literal (as you seem to assume) or an unary prefix operator (as the comments in the question suggest). In the latter case an expression like 6----4 would be legal with a meaning of 6-(-(-(-4))) and a resulting value of 10.

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());
 }
}

• Toby Speight: Code Review is always for providing any or all guidance on improving the posted code, so this is great. But we don't require askers to be specific - most of the best questions just introduce what the code is for and leave the reviewers with free rein to critique it.