Interview Question
Country: India
Interview Type: Written Test
Great job!
I implemented it in java
public static boolean hasRedundantBraces(String str) {
Stack<Integer> stack = new Stack<Integer>();
stack.push(0);
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (c == '(') {
stack.push(0);
} else if (c == ')') {
if (stack.pop() == 0) {
return true;
}
} else {
stack.push(stack.pop() + 1);
}
}
return stack.pop() == 0;
}
Can't figure out Guillaume's code. So I test it and for the both sample strings, it yields true.
// parenthesis redundancy and balancing check ((a+b)) is redundant
//algorithm is simple keep pushing numbers on stack for open bracketts,
//consecutive bracketts are numbered as same
//pop stack on encountering closed brackett symbols,
//if we encounter same numbers being popped for consecutive closed brackets
//then the string is redundant
//example ((a+b)) first open brackett will be numbered as "1" and pushed and
//same will be the number of second open brackett
//on encountering the closed brackett we pop the stack (1 will be popped)
//consecutively next brackett will also pop a value 1 which is same as previous and hence redundant.
//example (a+(b+c)) first and second brackett will be numbered as 1 and 2 resp.
// and while popping due to consecutive closed brackett we will get different values (1 & 2)
#include<stdio.h>
int stack[100],top=-1;
int pop()
{
return stack[top--];
}
void push(int x)
{
stack[++top]=x;
}
int main()
{
int temp,count,i=0,SAW_O=0,SAW_C=0,SAW_CHAR=0,pop_val=-1; //SAW_O=saw open brackett,
//SAW_C=saw closed brackett
char s[100];
scanf("%s",s);
count=1;
while(s[i]!='\0')
{
if(s[i]=='(')
{
if(SAW_O==1)
push(count);
else
{
SAW_O=1;
push(count);
}
}
else if(s[i]==')')
{
if(SAW_C)
{
temp=pop();
if(pop_val==temp){
printf("redundant %d \n",1);// cases of the type ((a+b))
return 1;
}
pop_val=temp;
i++;
continue;
}
if(SAW_O)
{
printf("redundant \n",2); // cases of the type a+b()
return 2;
}
else
{
pop_val=pop();
SAW_C=1;
}
}
else
{
if(SAW_O==1)
{
SAW_O=0;
count++;
}
SAW_C=0;
}
i++;
}
if(top>-1)
{
printf("incorrect parenthesis %d \n",3); //case when uneven number of brackets are present
return 3;
}
printf("non redundant string");
return 0;
}
/**
* Author: Yasir , Pramod, Awais
* We are using Stack to hold operators and String to hold characters
*
* @param s
* @return true if it contains redundant () else false
*/
public static Boolean isReduntentBracket(char[] s) {
Stack<Character> stack = new Stack<Character>();
StringBuffer postFix = new StringBuffer();
for (int i = 0; i < s.length; i++) {
if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/')
stack.push(s[i]);
else if (s[i] == ')') {
if (stack.isEmpty()) {
return true;// yes it contains redundant
}
postFix.append(stack.pop()).append(s[i]);
} else
postFix.append(s[i]);
}
return false;
}
/*
* write code to validate if the input string has redundant braces?
* eg ((a+b+c))
*/
package com.uta.careerCup;
import java.util.Stack;
public class RedundantBraces {
public boolean isRedundant(String input) {
if (input.length() == 0) {
return false;
}
Stack<Character> st = new Stack<Character>();
int index = 0;
for (char eachChar : input.toCharArray()) {
if (eachChar != ')') {
st.push(eachChar);
} else {
while (!st.isEmpty() && st.peek() != '(') {
st.pop();
}
st.pop();
if (index + 1 < input.length()
&& (input.charAt(index + 1) == ')') && st.peek() == '(') {
return true;
}
}
index++;
}
return false;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
String expr = "(a+b+c)";
System.out.println(new RedundantBraces().isRedundant(expr));
}
}
bool FindIfBalanced(char *exp) {
int count = 0
while (*exp) {
if (*exp == '(') {
count++;
} else if (*exp == ')'){
if (count == 0)
return false;
else
count--;
}
exp++;
}
if (count == 0)
return true;
else
return false;
}
void Test_FindIfBalanced() {
char *exp[] = { "(a+b)", "()", "(a+b)+c", "((a+b))+c", "(((" };
for(int i=0;i<5;i++)
std::cout<<exp[i]<<" is "<<(FindIfBalanced(exp[i])?"Balanced":"NoBalanced")<<"\n";
}
import java.util.Stack;
public class RedundantBraceChecker {
public boolean isRedundantBrace(String string) {
boolean isRedundant = false;
boolean squaredOff = false;
Stack<Character> stack = new Stack<Character>();
char[] charArray = string.toCharArray();
for(char c:charArray){
if(c!=')'){
stack.push(c);
}else{
char popped = Character.MIN_VALUE;
do{
popped = stack.pop();
if(popped!='('){
squaredOff = false;
}
}while(popped!='(');
if(squaredOff && (stack.isEmpty() || !stack.contains('('))){
isRedundant = true;
squaredOff = false;
}
if(!squaredOff){
squaredOff = true;
}
}
}
return isRedundant;
}
}
public static void main(String[] args) {
String str = "...x.x..x..x.x";
int median=median(str);
int hops=shifts(str,median);
System.out.print(hops);
}
public static int shifts(String str,int median)
{
int count=0,temp=0;
for (int i=0;i<str.length();i++)
{
if(str.charAt(i)=='x')
{
temp=abs(i-median);
count=count+temp;
}
}
return count;
}
public static int median(String str){
int count=0,j=0;
for (int i=0;i<str.length();i++){
if (str.charAt(i)=='x'){
count++;
}
}
count=(count+1)/2;
for (int k=0;k<str.length();k++)
{ if(str.charAt(k)=='x')
j++;
if(j==count)
return k;
}
return -1;
}
public static boolean hasRedundantBraces(String str){
// this will store the position in the str for each of the open braces
Stack<Integer> positions = new Stack<Integer>();
// for each character
for(int i = 0; i < str.length(); i++){
char c = str.charAt(i);
//if it's an open brace, push it
if(c == '{'){
positions.push(i);
}
// if it's a close brace, check for redundancies
else if(c == '}'){
int lastPos = positions.pop();
//if there were other open braces and there are more chars
if(!positions.empty() && i < str.length() -1){
//if the previous open is right before this one and the next char is a close
if(positions.peek() == lastPost -1 && str.charAt(i+1) == '}'){
return true;
}
}
}
}
return false;
}
I assume the use of braces in the input is valid. We traversal the input, if the character is (, +, -, *, /, we put the character into the stack. If the character is ), we peek the stack, if the value is (, then the braces are redundant.
public static boolean hasRedundantBraces(String str) {
Stack<Character> stack = new Stack<Character>();
int index = 0;
while(index < str.length()){
char c = str.charAt(index);
if(c == '(' || c == '+' || c == '-' || c == '*' || c == '/'){
stack.push(c);
} else if(c == ')'){
if(stack.peek() == '('){
return true;
} else{
while(!stack.isEmpty() && stack.peek() != '('){
stack.pop();
}
stack.pop();
}
}
index++;
}
return false;
}
simple c++ code handling all corner cases :)
int Solution::braces(string A) {
int n = A.length();
int i,j,k = 0,l;
stack<char> s;
for(i = 0; i < n; i++) {
if(A[i] != ')') {
s.push(A[i]);
}
if(A[i] == ')') {
if(s.top() == '(') return 1;
while(s.top() != '(') {
s.pop();
k++;
}
if(k == 1) {
return 1;
} else {
if(!s.empty())
s.pop();
k = 0;
}
}
}
return 0;
}
Implemetation in c++
#include<bits/stdc++.h>
using namespace std;
int main()
{
string s;
cin >> s;
int i;
stack<int> st;
st.push(0);
for(i=0;i<s.length();i++)
{
if(s[i]=='(')
st.push(0);
else if(s[i]==')')
{
int x=st.top();
st.pop();
if(x==0)
{
cout << "Redundant" << endl;
break;
}
}
else
{
int x=st.top();
st.pop();
st.push(x+1);
}
}
}
def has_redundant(s): stack = [0] for c in s: if c == '(': stack.append(0) elif c == ')': if stack.pop() == 0: return True else: stack[-1] += 1 # Treat (expr) as redundant return stack.pop() == 0 assert has_redundant("()") assert has_redundant("(a+b)") assert not has_redundant("(a+b)+c") assert has_redundant("((a+b))+c")O(number of braces) space, O(n) time
- bowl November 03, 2014Assuming that braces are balanced.