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