856.score-of-parentheses.md

856. Score of Parentheses

Stack

Suppose we have the string: s = (()(())), we can use stack to solve this problem:

1. For (, we just push it into stack.
2. For ), we pop until we encounter (, then we calculate the score of the number between the parentheses and push it back to stack.
   • If the peek of stack is (, then we form () which has score 1.
   • If the peek of stack is a number, then we form (A, B) which has score A + B = C and then pattern (C), so 2 * C.

For example, the process of (()(())) is as follows:

s	action	stack	note
(	push (	(
((	push (	(, (
(()	pop until (	(, 1	→ it forms (), score 1, push 1
(()(	push (	(, 1, (
(()((	push (	(, 1, (, (
(()(()	pop until (	(, 1, (, 1	→ it forms (), score 1, push 1
(()(())	pop until (	(, 1, 2	→ it forms (1), score 2 * 1 = 2, push 2
(()(()))	pop until (	6	→ it forms (1, 2), score A + B = C, then (C), so 2 * 3 = 6

Nice diagram to explain: https://leetcode.cn/problems/score-of-parentheses/solutions/1878748/zhua-wa-mou-si-by-muse-77-hy72/

Similar idea: https://leetcode.cn/problems/score-of-parentheses/solutions/39148/kan-bu-dong-bie-ren-de-ti-jie-zi-ji-you-xie-liao-y/

fun scoreOfParentheses(s: String): Int {
    val stack = Stack<String>()
    for (c in s) {
        // For `(`, we just push it into stack.
        if (c == '(') {
            stack.push(c.toString())
        } else {
            // For `)`, we pop until we encounter `(`, then we calculate the score of `()` and push it back to stack.
            if (stack.peek() == "(") { // For the case "()" in stack
                // Pop the left '('
                stack.pop()
                // Form "()" which has score 1.
                stack.push(1.toString())
            } else {
                // For the case "(A,B,C)" in stack
                var num = 0
                while (stack.isNotEmpty() && stack.peek() != "(") {
                    num += stack.pop().toInt()
                }
                // Pop the left '('
                stack.pop()
                // Form "(A,B,C)" which has score 2 * (A + B + C).
                num *= 2
                stack.push(num.toString())
            }
        }
    }
    // Sum up all scores in stack.
    var result = 0
    while (stack.isNotEmpty()) {
        result += stack.pop().toInt()
    }
    return result
}

• Time Complexity: O(n) to iterate all characters in string.
• Space Complexity: O(n) for stack.

I don't understand the following solution, but it works.

fun scoreOfParentheses(s: String): Int {
    val stack = Stack<Int>()
    var num = 0
    for (c in s) {
        if (c == '(') {
            stack.push(num)
            num = 0
        } else {
            num = stack.pop() + maxOf(1, num * 2)
        }
    }
    return num
}

From ChatGPT, need to verify.

fun scoreOfParentheses(s: String): Int {
    val stack = ArrayDeque<Int>()
    stack.push(0) // Initial score at base level

    for (ch in s) {
        if (ch == '(') {
            stack.push(0) // Push placeholder for a new level
        } else {
            val top = stack.pop() // Get the current level's score
            val newScore = if (top == 0) 1 else 2 * top
            stack.push(stack.pop() + newScore) // Add to the previous level
        }
    }
    
    return stack.pop()
}