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.
Example:
Solution:
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 currentDepth
and 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.
Complete Code:
Output:
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