% Function Name: recursiveParens % Inputs (1): - (char) A string including some
ID: 3538962 • Letter: #
Question
% Function Name: recursiveParens
% Inputs (1): - (char) A string including some number of parentheses
% (and possibly other characters)
% Outputs (2): - (logical) True if the parentheses are not unbalanced at
% ANY point in the string, and false otherwise
% (double) A double representing the imbalance in
% parentheses
%
% Function Description:
% Write a function called "matchParens" that takes in a string that has
% some number of parentheses and determines whether or not
% the expression is valid as well as the total imbalance of the string.
%
% An expression is valid if it contains the same number of open and
% closed parentheses while containing no open parentheses which have no
% matching closed parentheses and vice versa. The total imbalance of the
% expression is then defined as the number of open parentheses minus the
% number of closed parentheses.
%
% For example: '(())', '()()()', and '((())((())))' are all valid strings
% that should return true and an imbalance of 0.
%
%
% However: '()))' is unbalanced and should return false and -2
%
% '(((((' is unbalanced and should return false and 5
%
% '())(' is unbalanced and should return false and 0
%
% Be careful of strings that have the same number of open and closing
% parentheses but are imbalanced at some point in the string,
% like in the last example.
%
% Additionally, do not assume that an input string is composed entirely
% of parentheses. Any character that is not '(' or ')' should have no
% bearing on the outputs of your function.
%
% Constraints:
% - Do not use the sum(), strfind(), findstr(), find(), or any other
% similar functions. They will most likely overcomplicate the problem
% anyway.
% - You must use recursion to solve this problem.
%
% Test Cases:
%
% str1 = '(())())))(())'
% str2 = '(k((vx)((z/)))7)'
% str3 = ''
%
% [log1 imbalance1] = recursiveParens(str1);
% log1 => false
% imbalance1 => -3
%
% [log2 imbalance2] = recursiveParens(str2);
% log2 => true
% imbalance2 => 0
%
% [log3 imbalance3] = recursiveParens(str3);
% log3 => true
% imbalance2 => 0
Explanation / Answer
% I found this very tough
% there should be easier way to do this
% however i could not come up with it
% NOTE: in MATLAB 1 is true and 0 is false
function [log imbalance]=recursiveParens(s)
len=length(s);
log=true;
imbalance=0;
if len==0
log=true;
imbalance=0;
elseif len==1
if s(1)=='('
log=false;
imbalance=1;
end
if s(1)==')'
log=false;
imbalance=-1;
end
else
if s(1)==')'
log=false;
[~, im]=recursiveParens(s(2:len));
imbalance=imbalance+im-1;
elseif s(1)=='('
i=2;
valid=false;
k=1;
while(i<=len)
if s(i)=='('
k=k+1;
elseif s(i)==')'
k=k-1;
if k==0
valid=true;
break;
end
end
i=i+1;
end
if valid
[lg1 im1]=recursiveParens(s(2:i-1));
log=log & lg1;
imbalance=imbalance+im1;
if(i<len)
[lg2 im2]=recursiveParens(s(i+1:len));
log=log & lg2;
imbalance=imbalance+im2;
end
else
log=false;
[~, im]=recursiveParens(s(2:len));
imbalance=imbalance+im+1;
end
else
[log, imbalance]=recursiveParens(s(2:len));
end
end
end
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.