在运算符和操作数中拆分字符串表达式
在运算符和操作数中拆分字符串表达式
提问于 2023-03-01 18:23:38
请求scala实现的代码评审。
问题
给定由数字和运算符+,-,/,*组成的表达式字符串，请在整数或字符串列表中将其拆分。
示例
"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)不需要对有效表达式进行错误检查，例如*、2+1或// wont等表达式不会通过。
溶液
我在Scala2.13中实现了这个解决方案。使用任一在结果中存储Int或String。想看看我对阳性病例的判断是否正确。
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
}
}测试
测试用例
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"))我得到了如下结果
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)))后续问题:对格式错误的字符串表达式引入错误处理的最佳方法是什么。
回答 6
Code Review用户
发布于 2023-03-19 14:45:48
在Scala中，字符串是字符序列；因此，Iterator方法是可用的，而不需要以前的拆分。
String和Integer的超级类型都是Any。使用超级类型对中间结果进行包装是多余的。
可以在String中定义运算符，并简化实用程序嵌套方法，以测试参数是否为运算符。
折叠字符串以进行解析可能会提高算法效率。
字符的索引和累加器的大小可以用来测试边缘情况。
从上述角度来看，执行情况将改为：
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;
}Code Review用户
发布于 2023-04-27 16:50:57
这个实现非常渴望解析整个字符串，即使只得到第一个操作数，而且在上面解析了几次。对breakExpression("-2-3*-4/-6").iterator.next()调用结果的不同描述是对表达式"-2-3*-4/-6"进行多次解析。
在积累中间结果的转换中也会发生类似的情况，即使只获得部分运算符和操作数，也会对要解析的表达式进行完全解析。
实现延迟解析解决方案是可能的。为了好玩..。恕我直言，为了学术目的，有大量的句法糖( returning )和设计模式(策略、责任链、模板法)，Iterator#map转换可以暂时积累返回空迭代器的中间结果，直到声音操作数形成为止。
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
};
}深入研究延迟Iterator#map返回的细节对于串行集合来说是可能的，对于并行集合，结果是不可预测的。
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());
}
}Code Review用户
发布于 2023-05-07 06:37:40
添加模块化或提醒操作符%，以改进运算符列表。
List("+", "-", "/", "*", "%")
..。还有一件事是，向diffuse类中添加一个名为Iterator的方法以简化代码：
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 _ );
}在Scala语言中，在隐式类的帮助下，可以动态地向现有类添加方法，类似于下面的Buoyant类：
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())
}
}
}
}这是一种非正式的方式，总之，有各种不同的视角来审查代码，并且以渐进的方式对待评审活动可能是有用的。
页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://codereview.stackexchange.com/questions/283661
复制相关文章
相似问题
腾讯云开发者
