algorithms/src/algorithmdesignmanualbook/datastructures/BalancedParentheses.kt at master · realpacific/algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
package algorithmdesignmanualbook.datastructures

import _utils.UseCommentAsDocumentation
import java.util.*
import kotlin.test.assertEquals
import kotlin.test.assertFalse
import kotlin.test.assertTrue

fun main() {
    assertTrue { checkIfBalancedParentheses("()()()()") }
    assertTrue { checkIfBalancedParentheses("()") }
    assertTrue { checkIfBalancedParentheses("()(())") }
    assertFalse { checkIfBalancedParentheses("((())") }
    assertFalse { checkIfBalancedParentheses("(()") }
    assertFalse { checkIfBalancedParentheses("))") }
    assertFalse { checkIfBalancedParentheses("))") }
    assertFalse { checkIfBalancedParentheses(")") }
    assertFalse { checkIfBalancedParentheses(")())") }
    assertFalse { checkIfBalancedParentheses("())(") }

    assertEquals(findPositionOfInvalidParenthesesOrNull("()()"), null)
    assertEquals(findPositionOfInvalidParenthesesOrNull("()"), null)
    assertEquals(findPositionOfInvalidParenthesesOrNull("(())"), null)
    assertEquals(findPositionOfInvalidParenthesesOrNull("()()()()"), null)
    assertEquals(findPositionOfInvalidParenthesesOrNull("(()"), 2)
    assertEquals(findPositionOfInvalidParenthesesOrNull("(()))"), 4)
    assertEquals(findPositionOfInvalidParenthesesOrNull(")))"), 0)

}

fun findPositionOfInvalidParenthesesOrNull(string: String): Int? {
    if (string.isEmpty()) return null
    val stack = Stack<String>()
    string.forEachIndexed { index, c ->
        if (c == '(') {
            stack.push("(")
        } else if (c == ')') {
            if (stack.isEmpty()) {
                return index
            }
            stack.pop()
        }
    }
    return if (stack.isEmpty()) null else string.lastIndex
}

/**
 * Check if a string contains properly nested and balanced parentheses, and false if otherwise.
 */
@UseCommentAsDocumentation
fun checkIfBalancedParentheses(string: String): Boolean {
    if (string.isEmpty()) return true
    val stack = Stack<String>()
    string.forEachIndexed { index, c ->
        if (c == '(') {
            stack.push("(")
        } else if (c == ')') {
            if (stack.isEmpty()) {
                return false
            }
            stack.pop()
        }
    }
    return stack.isEmpty()
}