# CLEAN CODE: REDUNDANT BRACES | LIFO | STACK | DATA STRUCTURE PROBLEMS

By: Saurav

2018-02-07 01:27:00 UTC

Write a program to validate if the input string has redundant braces?
Return 0/1

false -> NO
true -> YES
Input will be always a valid expression

and operators allowed are only + , * , - , /

Example:

((a + b)) has redundant braces so answer will be 1
(a + (a + b)) doesn't have have any redundant braces so answer will be 0

InterviewBit

This problem is a little trickier yet the simple application of LIFO.

Algo:
The approach here is to add an element to a stack. except ")" while iterating through the string.
If we encounter "(",
we need to check if the top element on the stack is ")". In that case, there are redundant brackets
Otherwise, we need to remove all elements (that is an expression) from the stack. Also for few cases, (a) may be considered redundant. In that case, we need to keep a count of the number of elements in the expression as well. If the count is just 1. We have another redundancy.

Let's write some tests and see it in action:

```p extraparnth("(((a+b)+c))") == true
p extraparnth("(a+())") == true
p extraparnth("((a))") == true
p extraparnth("a") == false
p extraparnth("(((a)+(b))+c)") == true
p extraparnth("a+(a)") == true```

```def extraparnth(a)
return false if a.length < 2

stack = Array.new

(0..a.length-1).each do |i|
if a[i] == ")"
last = stack.pop
return true if last == "("
count = 0

while last != "(" and !stack.empty?
last = stack.pop
count += 1
end

return true if count == 1

else

stack << a[i]

end
end

return false
end ```

Looks good to me.

### Let me know what you think! twitter: sprakash24octlinkedin

Owned & Maintained by Saurav Prakash

If you like what you see, you can help me cover server costs or buy me a cup of coffee though donation :) 