Skip to content

Instantly share code, notes, and snippets.

@makiftutuncu
Last active May 27, 2021 23:01
Show Gist options
  • Save makiftutuncu/aa8bdc669280a09212129321d7118f07 to your computer and use it in GitHub Desktop.
Save makiftutuncu/aa8bdc669280a09212129321d7118f07 to your computer and use it in GitHub Desktop.
A Scala 3 exercise: simulates typing with backspace keys, removing designated backspace characters along with the character it's supposed to remove
import scala.annotation.tailrec
sealed trait Stack[A]:
def push(a: A): Stack[A]
def pop(): (Option[A], Stack[A])
def size: Int
def reverse(): Stack[A] =
@tailrec def go(s1: Stack[A], s2: Stack[A]): Stack[A] =
s1.pop() match
case (None, bottom) => s2
case (Some(top), bottom) => go(bottom, s2.push(top))
go(this, Stack.empty)
def mkString(prefix: String, separator: String, suffix: String)(converter: A => String): String =
@tailrec def go(builder: StringBuilder, stack: Stack[A], hasMore: Boolean): StringBuilder =
stack match
case EmptyStack() => builder
case NonEmptyStack(top, bottom) => go(
if hasMore then builder.append(converter(top)).append(separator) else builder.append(converter(top)),
bottom,
bottom.size > 1
)
go(new StringBuilder(prefix), reverse(), size > 1).append(suffix).toString()
object Stack:
def empty[A]: Stack[A] = EmptyStack[A]()
private final case class NonEmptyStack[A](top: A, bottom: Stack[A]) extends Stack[A]:
override def push(a: A): Stack[A] = NonEmptyStack(a, this)
override def pop(): (Option[A], Stack[A]) = Some(top) -> bottom
override lazy val size: Int = bottom.size + 1
override def toString: String = s"NonEmptyStack($top, $bottom)"
private final case class EmptyStack[A]() extends Stack[A]:
override def push(a: A): Stack[A] = NonEmptyStack(a, this)
override def pop(): (Option[A], Stack[A]) = None -> this
override val size: Int = 0
override def toString: String = s"EmptyStack"
extension (s: String) def backspaced(backspaceChar: Char = '#'): String =
s.foldLeft(Stack.empty[Char]) {
case (st, `backspaceChar`) => st.pop()._2
case (st, c) => st.push(c)
}.mkString(prefix = "", separator = "", suffix = "")(_.toString)
println("aa#bx#c#".backspaced()) // "abc"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment