SHARE
TWEET

Untitled

a guest Mar 18th, 2019 51 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package java2scala.homeworks
  2.  
  3. trait CharAutomata[+A] {
  4.  
  5.   /** потребить один символ и перейти в следующее состояние */
  6.   def consume(char: Char): CharAutomata[A]
  7.  
  8.   /** получить текущий результат, если это конец строки */
  9.   def result: Either[String, A]
  10.  
  11.   /** потребить строку символ за символом */
  12.   def apply(source: String): Either[String, A] =
  13.     if (source.isEmpty) result
  14.     else consume(source.head)(source.tail)
  15.  
  16.   /** создать автомат, который запустит оба автомата
  17.     * и если первый вернёт ошибку, вернёт результат второго
  18.     */
  19.   def or[B](auto: CharAutomata[B]): CharAutomata[Either[A, B]] = new CharAutomata.Or(this, auto)
  20.  
  21.   /** создать автомат, который запустит оба автомата
  22.     * вернёт результаты обоих, если оба вернут успешный результат
  23.     * и вернёт ошибку, если вернёт ошибку хотя бы один
  24.     */
  25.   def and[B](auto: CharAutomata[B]): CharAutomata[(A, B)] = new CharAutomata.And(this, auto)
  26. }
  27.  
  28. object CharAutomata {
  29.  
  30.   /** создаёт автомат, всегда результирующий с ошибкой
  31.     * с заданным текстом message
  32.     */
  33.   def error(message: String): CharAutomata[Nothing] = new Error(message)
  34.  
  35.   /** создаёт автомат, всегда успешно результирующий
  36.     * с заданным значением `value`
  37.     */
  38.   def const[A](value: A): CharAutomata[A] = new Const[A](value)
  39.  
  40.   /** создаёт автомат, возвращающий
  41.     * первое вхождение строчки `substring`
  42.     * или ошибкой
  43.     */
  44.   def find(substring: String): CharAutomata[Int] = new Find(substring)(Position(0), State(0))
  45.  
  46.   /** создаёт автомат, определяющий является ли строчка,
  47.     * если исключить из неё все символы, кроме `'('` и `')'`
  48.     * корректной скобочной последовательностью */
  49.   def balance: CharAutomata[Unit] = new ParenBalance(Balanced)
  50.  
  51.   /** создаёт автомат, ищущий первое число, из цифр подряд
  52.     * и возвращающий результат в качестве BigInt либо 0
  53.     */
  54.   def parseInt: CharAutomata[BigInt] = new ParseInteger(NotFound)
  55.  
  56.   /** класс для реализации метода `error` */
  57.   class Error(string: String) extends CharAutomata[Nothing] {
  58.     def consume(char: Char): CharAutomata[Nothing] = this
  59.  
  60.     def result: Either[String, Nothing] = Left(string)
  61.   }
  62.  
  63.   /** класс для реализации метода `const` */
  64.   class Const[A] private[CharAutomata] (value: A) extends CharAutomata[A] {
  65.     def consume(char: Char): CharAutomata[A] = this
  66.  
  67.     def result: Either[String, A] = Right(value)
  68.   }
  69.  
  70.   /** класс для реализации метода `find` */
  71.   /** Автомат для поиска подстроки взят из книжки Кормена из раздела 32.3 "Поиск подстрок с помощью конечных автоматов" */
  72.  
  73.   case class Position(value: Int)
  74.   case class State(value: Int)
  75.  
  76.   class Find private[CharAutomata] (substring: String)(position: Position, state: State) extends CharAutomata[Int] {
  77.     def stateTransitionFunction(state: State, char: Char): State =
  78.       State {
  79.         (Math.min(substring.length, state.value + 1) to 0 by -1)
  80.           .find(i => (substring.substring(0, state.value) + char).endsWith(substring.substring(0, i)))
  81.           .getOrElse(0)
  82.       }
  83.  
  84.     def consume(char: Char): CharAutomata[Int] =
  85.       result match {
  86.         case Right(_) => this
  87.         case Left(_)  => new Find(substring)(Position(position.value + 1), stateTransitionFunction(state, char))
  88.       }
  89.  
  90.     def result: Either[String, Int] =
  91.       if (substring.isEmpty) Right(0)
  92.       else if (substring.length == state.value) Right(position.value - substring.length)
  93.       else Left("Not found")
  94.   }
  95.  
  96.   /** класс для реализации метода `balance` */
  97.   sealed trait ParenBalanceState
  98.   case object Balanced              extends ParenBalanceState
  99.   case object NotBalanced           extends ParenBalanceState
  100.   case class  Imbalance(count: Int) extends ParenBalanceState
  101.  
  102.   class ParenBalance private[CharAutomata] (balance: ParenBalanceState) extends CharAutomata[Unit] {
  103.     def consume(char: Char): CharAutomata[Unit] = char match {
  104.       case '(' =>
  105.         balance match {
  106.           case Balanced         => new ParenBalance(Imbalance(1))
  107.           case Imbalance(count) => new ParenBalance(Imbalance(count + 1))
  108.           case _                => this
  109.         }
  110.       case ')' =>
  111.         balance match {
  112.           case Balanced                       => new ParenBalance(NotBalanced)
  113.           case Imbalance(count) if count == 1 => new ParenBalance(Balanced)
  114.           case Imbalance(count)               => new ParenBalance(Imbalance(count - 1))
  115.           case _                              => this
  116.         }
  117.       case _   => this
  118.     }
  119.  
  120.     def result: Either[String, Unit] = balance match {
  121.       case Balanced    => Right(())
  122.       case _           => Left("Incorrect")
  123.     }
  124.   }
  125.  
  126.   /** класс для реализации метода `parseInt` */
  127.  
  128.   sealed trait ParsingState
  129.   case object NotFound                 extends ParsingState
  130.   case class  Found(value: BigInt)     extends ParsingState
  131.   case class  InProcess(value: BigInt) extends ParsingState
  132.  
  133.   class ParseInteger private[CharAutomata] (parse: ParsingState) extends CharAutomata[BigInt] {
  134.     def consume(char: Char): CharAutomata[BigInt] =
  135.       if (char.isDigit)
  136.         parse match {
  137.           case NotFound         => new ParseInteger(InProcess(char.asDigit))
  138.           case Found(_)         => this
  139.           case InProcess(value) => new ParseInteger(InProcess(value * 10 + char.asDigit))
  140.         }
  141.       else
  142.         parse match {
  143.           case NotFound         => this
  144.           case Found(_)         => this
  145.           case InProcess(value) =>
  146.             if (value == 0) new ParseInteger(NotFound)
  147.             else new ParseInteger(Found(value))
  148.         }
  149.  
  150.     def result: Either[String, BigInt] =
  151.       parse match {
  152.         case NotFound         => Right(0)
  153.         case Found(value)     => Right(value)
  154.         case InProcess(value) => Right(value)
  155.       }
  156.   }
  157.  
  158.   /** класс для реализации метода `and` */
  159.   class And[A, B] private[CharAutomata] (autoA: CharAutomata[A], autoB: CharAutomata[B]) extends CharAutomata[(A, B)] {
  160.     def consume(char: Char): CharAutomata[(A, B)] = new And(autoA.consume(char), autoB.consume(char))
  161.  
  162.     def result: Either[String, (A, B)] =
  163.       (autoA.result, autoB.result) match {
  164.         case (Right(valueA), Right(valueB)) => Right((valueA, valueB))
  165.         case _                              => Left("Error")
  166.       }
  167.   }
  168.  
  169.   /** класс для реализации метода `or` */
  170.   class Or[A, B] private[CharAutomata] (autoA: CharAutomata[A], autoB: CharAutomata[B]) extends CharAutomata[Either[A, B]] {
  171.     def consume(char: Char): CharAutomata[Either[A, B]] = new Or(autoA.consume(char), autoB.consume(char))
  172.  
  173.     def result: Either[String, Either[A, B]] =
  174.       autoA.result match {
  175.         case Right(value) => Right(Left(value))
  176.         case Left(_)      =>
  177.           autoB.result match {
  178.             case Right(value) => Right(Right(value))
  179.             case Left(error)  => Left(error)
  180.           }
  181.       }
  182.   }
  183. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top