package daily.mid

import java.util.*

fun main() {
    // 856. 括号的分数
    // https://leetcode.cn/problems/score-of-parentheses/
    println(scoreOfParentheses("(()(()))"))
}

fun scoreOfParentheses(s: String): Int {
    // 影响分数的，只有()，至于一对()能贡献多少分数，要看它位于第几层
    // 如 (()) ，()位于第二层，根据题意，可以贡献 1*2 = 2 分
    // ((())) ，() 位于第三层，则可以贡献 1*2*2 = 4 分
    // 即 () 位于第 n 层，则可以贡献 2^(n-1) 分
    // 而没有互相嵌套的 () 之间，则使用加法累计分数，累加到 result 中就可以了
    var depth = 0
    var result = 0
    val one = 1
    for (i in s.indices) {
        val c = s[i]
        if (c == '(') {
            depth++
        }else {
            // c == ')'
            depth--
            if (s[i-1] == '(') {
                // 成对
                result += one.shl(depth)
            }
        }
    }
    return result
}

fun scoreOfParentheses1(s: String): Int {
    var depth = 0
    var result = 0
    val one = 1
    for (i in s.indices) {
        if (s[i] == '(') {
            depth++
        }else if (s[i] == ')') {
            depth--
            if (i > 0 && s[i-1] == '(') {
                result += one.shl(depth)
            }
        }
    }
    return result
}