This post is completed by 2 users
|Add to List|
Maximum Depth of Valid Nested Parentheses in an arithmetic expression
Given an arithmetic expression which operators, operands and brackets. You need to find out the maximum depth of valid nested parentheses. If parentheses are not valid ( means not well formed ) then return -1.
Input: 1 + (2*((3+4)/(2-1)))/2+56 Maximum Depth: 3 Input: 1 + (4/2) Maximum Depth: 1 Input: ((1)) Maximum Depth: 2 Input: 5 Maximum Depth: 0 Input: )1 + (2*((3+4)/(2-1)))/2+56( Maximum Depth: -1 (not well formed)
Earlier we solved a similar problem - Valid Brackets. Please read before continuing. We will use a similar approach with some enhancements. Use variables
maxDepth. Whenever there is an open parenthesis, increment the count of currentDepth by 1 and compare it with maxDepth and update the maxDepth with currentDepth if maxDepth<currentDepth. Similarly, whenever there is a close parenthesis, decrement the currentDepth by 1. If anytime you find that parentheses are not well-formed, set maxDepth = -1 and break the loop. See the code below for more understanding.
Input: 1 + (2*((3+4)/(2-1)))/2+56, Maximum Depth: 3 Input: 1 + (4/2), Maximum Depth: 1 Input: ((1)), Maximum Depth: 2 Input: 5, Maximum Depth: 0 Input: )1 + (2*((3+4)/(2-1)))/2+56(, Maximum Depth: -1