Maximum Nesting Depth of the Parentheses

🏠 ⬅️ ➡️

A string is a valid parentheses string (denoted VPS) if it meets one of the following:

  • It is an empty string " ", or a single character not equal to "( " or ") ",
  • It can be written as AB (A concatenated with B), where A and B are VPS's, or
  • It can be written as (A), where A is a VPS.

We can similarly define the nesting depth depth(S) of any VPS S as follows:

  • depth( " ") = 0
  • depth(C) = 0, where C is a string with a single character not equal to "( " or ") ".
  • depth(A + B) = max(depth(A), depth(B)), where A and B are VPS's.
  • depth( "( " + A + ") ") = 1 + depth(A), where A is a VPS.

For example, " ", "()() ", and "()(()()) " are VPS's (with nesting depths 0, 1, and 2), and ")( " and "(() " are not VPS's.

Given a VPS represented as string s, return the nesting depth of s.

Example 1:

Input: s = "(1+(2*3)+((8)/4))+1 " Output: 3 Explanation: Digit 8 is inside of 3 nested parentheses in the string.

Example 2:

Input: s = "(1)+((2))+(((3))) " Output: 3

Constraints:

  • 1 <= s.length <= 100
  • s consists of digits 0-9 and characters '+', '-', '*', '/', '(', and ')'.
  • It is guaranteed that parentheses expression s is a VPS.
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    ! Solves the problem:
    ! A string is a valid parentheses string (denoted VPS) if it meets one of the following:
    ! - It is an empty string " ", or a single character not equal to "( ".
    ! - It can be written as AB (A concatenated with B), where A and B are VPS's.
    ! - It can be written as (A), where A is a VPS.
    implicit none

    integer :: i, j, k, n, depth
    character(len=100) :: s

    ! Examples
    print '("Example 1:")'
    s = "(1+(2*3)+((8)/4))+1"
    print '(*(g0,1x))', s, depth(s)
    print '("Example 2:")'
    s = "(1)+((2))+(((3)))"
    print '(*(g0,1x))', s, depth(s)

contains

    function depth(s) result(d)
        ! Returns the nesting depth of a valid parentheses string (VPS)
        implicit none
        character(len=*), intent(in) :: s
        integer :: d

        d = 0
        do i = 1, len(s)
            select case(s(i:i))
                case(' ')
                    cycle
                case('(')
                    d = d + 1
                case(')')
                    d = d - 1
            end select
        end do
    end function depth

end program main
❌ Compiled
❌ Executed
❌ Correct 
module ParenthesesDepth
    implicit none
    private
    public :: depth
contains
    function depth(s) result(depth_)
        character(len=*), intent(in) :: s
        integer :: depth_
        integer :: i, j, k
        character :: c
        logical :: is_open_paren

        ! Initialize variables
        depth_ = 0
        i = 1
        j = 1
        k = 1
        is_open_paren = .false.

        ! Iterate over the characters in the string
        do while (i <= len(s))
            c = s(i:i)

            ! If we encounter an opening parenthesis, increment the nesting depth
            if (c == '(') then
                depth_ = depth_ + 1
                is_open_paren = .true.
            ! If we encounter a closing parenthesis, decrement the nesting depth
            else if (c == ')') then
                depth_ = depth_ - 1
                is_open_paren = .false.
            end if

            ! If we encounter a digit and we are not in a nested expression,
            ! increment the index
            if (c >= '0' .and. c <= '9' .and. .not. is_open_paren) then
                j = j + 1
            end if

            ! Increment the index
            i = i + 1
        end do

        ! Return the nesting depth
        depth_ = depth_ + 1
    end function depth
end module ParenthesesDepth

! Test the function with some examples
program test_depth
    use ParenthesesDepth
    implicit none
    integer :: depth

    ! Test case 1: " "
    depth = depth(" ")
    write (*,*) "Test case 1: ", depth

    ! Test case 2: "()() "
    depth = depth("()() ")
    write (*,*) "Test case 2: ", depth

    ! Test case 3: "()(()()) "
    depth = depth("()(()()) ")
    write (*,*) "Test case 3: ", depth

    ! Test case 4: ")("
    depth = depth(")(")
    write (*,*) "Test case 4: ", depth

    ! Test case 5: "(() "
    depth = depth("(() ")
    write (*,*) "Test case 5: ", depth

    ! Test case 6: "(()())"
    depth = depth("(()())")
    write (*,*) "Test case 6: ", depth

    ! Test case 7: "(((((18)))))"
    depth = depth("(((((18)))))")
    write (*,*) "Test case 7: ", depth

    ! Test case 8: "(1+(2\*3)+((8)/4))+1 "
    depth = depth("(1+(2*3)+((8)/4))+1 ")
    write (*,*) "Test case 8: ", depth

    ! Test case 9: "(1)+((2))+(((3))) "
    depth = depth("(1)+((2))+(((3))) ")
    write (*,*) "Test case 9: ", depth
end program test_depth
🌐 Data from online sources 
def maxDepth(s: str) -> int:
    depth = 0
    max_depth = 0

    for c in s:
        if c == '(':
            depth += 1
            max_depth = max(depth, max_depth)
        elif c == ')':
            depth -= 1

    return max_depth

Iterate through the string s. When an opening parenthesis '(' is encountered, increment the depth value, update the max_depth with the maximum between the current max_depth and the depth. In contrast, when a closing parenthesis ')' is encountered, decrement the depth. The max_depth will be the nesting depth of the given valid parentheses string.

🌐 Data from online sources 
int maxDepth(std::string s) {
    int depth = 0, max_depth = 0;

    for (char c : s) {
        if (c == '(') {
            depth++;
            max_depth = std::max(depth, max_depth);
        } else if (c == ')') {
            depth--;
        }
    }

    return max_depth;
}

Iterate through the string s. When an opening parenthesis '(' is encountered, increment the depth value, update the max_depth with the maximum between the current max_depth and the depth. In contrast, when a closing parenthesis ')' is encountered, decrement the depth. The max_depth will be the nesting depth of the given valid parentheses string.