4
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ 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. \$\endgroup\$
    – RoToRa
    Mar 17, 2023 at 12:07
  • 1
    \$\begingroup\$ "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. \$\endgroup\$
    – user272945
    May 3, 2023 at 8:25
  • \$\begingroup\$ 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? \$\endgroup\$
    – CiaPan
    May 4, 2023 at 12:12
  • \$\begingroup\$ @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. \$\endgroup\$
    – CiaPan
    May 4, 2023 at 12:28

7 Answers 7

2
\$\begingroup\$

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;
}
\$\endgroup\$
2
\$\begingroup\$

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());
    }
}
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
        };
}
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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;
}
\$\endgroup\$
1
\$\begingroup\$

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());
    }
}
\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$ May 6, 2023 at 13:02

Not the answer you're looking for? Browse other questions tagged or ask your own question.