Sha256: 481ff1d2886d696b471fa6627b17fa0a3d2a8fec0ceb1690fd3369aeda1a7117
Contents?: true
Size: 1.56 KB
Versions: 396
Compression:
Stored size: 1.56 KB
Contents
import java.util.*
import java.util.Collections.asLifoQueue
object BracketPush {
private val CLOSING_TO_OPENING_MAP = mapOf(
'}' to '{',
')' to '(',
']' to '['
)
private val OPENING_BRACKETS = CLOSING_TO_OPENING_MAP.values
private val CLOSING_BRACKETS = CLOSING_TO_OPENING_MAP.keys
private val ALL_BRACKET = OPENING_BRACKETS + CLOSING_BRACKETS
fun isValid(input: String): Boolean {
val onlyBracketChars = input.filter { it.isBracket() }.toList()
return isValidRec(onlyBracketChars, asLifoQueue(ArrayDeque<Char>()))
}
private tailrec fun isValidRec(bracketChars: List<Char>, stack: Queue<Char>): Boolean {
if(bracketChars.isEmpty()) {
return stack.isEmpty()
}
val firstChar = bracketChars.first()
if(firstChar.isOpeningBracket()) {
return isValidRec(bracketChars.tail(), stack.push(firstChar))
}
else {
val stackHead = stack.poll() ?: return false
val isMatch = firstChar.matchingOpeningBracket() == stackHead
return if(isMatch) isValidRec(bracketChars.tail(), stack) else false
}
}
fun Char.isBracket() = this in ALL_BRACKET
fun Char.isOpeningBracket() = this in OPENING_BRACKETS
fun Char.matchingOpeningBracket() = CLOSING_TO_OPENING_MAP[this] ?: throw IllegalArgumentException("Char ${this} is not a closing bracket")
}
fun <T> List<T>.tail() = this.subList(1, this.size)
fun <T> Queue<T>.push(element: T): Queue<T> {
this.add(element)
return this
}
Version data entries
396 entries across 396 versions & 1 rubygems