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: sprakash24oct
linkedin

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 :)