import scala.util.control.Breaks._

object Lab1 {
  def main(args: Array[String]): Unit = {
    println(balance("(()())".toList))
  }

  def Balance(text: String, stack: String): Boolean = {
    if (text.isEmpty){
      return stack.isEmpty
    }
    else if (text.head == '('){
      return Balance(text.tail, stack + text.head)
    }
    else if (text.head == ')'){
      return stack.nonEmpty && stack.last == '(' && Balance(text.tail, stack.substring(0, stack.length - 1))
    }

    return Balance(text.tail, stack)
  }

  def CountChange(nominals: Array[Int], index: Int, num: Int): Int = {
    if (num == 0) return 1
    if(num < 0 || index <= 0) return 0

    val withoutNum = CountChange(nominals, index - 1, num)
    val withNum = CountChange(nominals, index, num - nominals(index - 1))

    return withoutNum + withNum
  }

  /**
   * Трикутник Паскаля
   */
  def pascal(col: Int, row: Int): Int = {
    if (col == 0 || col == row) return 1

    return pascal(col - 1, row - 1) + pascal(col, row - 1)
  }

  /**
   * Балансування дужок
   */
//  def balance(chars: List[Char]): Boolean = {
//    if (chars.isEmpty) return true
//    if (chars.length == 1) return false
//    if (chars.head == ')') return false
//
//    val n = chars.length
//
//    var i = 1
//    var count = 0
//    breakable {
//      while (i < n) {
//        if (chars(i) == chars.head) {
//          count += 1
//        }
//        if (chars(i) == ')') {
//          if (count == 0) break
//          count -= 1
//        }
//
//        i += 1
//      }
//    }
//
//    if(i == n) return false
//
//    if(i == 2) return balance(chars.slice(i, n - 1))
//
//    return balance(chars.slice(1, i)) && balance(chars.slice(i + 1, n))
//  }
def balance(chars: List[Char]): Boolean = {
  if (chars.isEmpty) return true

  return balanced(chars.slice())
}

  /**
   * Підрахунок решти
   */
  def countChange(money: Int, coins: List[Int]): Int = {
    return 0
  }
}