Last active
May 29, 2017 13:45
-
-
Save anil477/b7b0a9e86080b1768ed99d41183c21ef to your computer and use it in GitHub Desktop.
Minimum number of bracket reversals needed to make an expression balanced
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// the code is not tested completly | |
import java.util.Deque; | |
import java.util.LinkedList; | |
class RemoveExtraBrackets { | |
public int remove(char input[]){ | |
// ) ) ) ( ) ( ( ( | |
// ) ) ) ( ) ( ( ( | |
if(input == null){ | |
return 0; | |
} | |
Deque<Character> dq = new LinkedList<Character>(); | |
for(int i=0; i < input.length; i++){ | |
if(input[i] == '(') | |
{ | |
dq.addLast(input[i]); | |
} | |
else if(input[i] == ')') | |
{ | |
if(!dq.isEmpty() && dq.peekLast() == '('){ | |
//if(!dq.isEmpty() && dq.peekLast().equals('(')){ | |
// System.out.println(" same "); | |
// System.out.println(dq.removeLast()); | |
dq.removeLast(); | |
}else{ | |
dq.addLast(input[i]); | |
} | |
} | |
System.out.println(dq.toString()); | |
} | |
System.out.println(dq.toString()); | |
int index = 0; | |
while(!dq.isEmpty()){ | |
if(dq.size() == 1) { | |
index = -1; | |
break; | |
} | |
if( (dq.peekFirst() == '(' && dq.peekLast() == ')' ) ) | |
{ | |
dq.removeLast(); | |
dq.removeFirst(); | |
} else if ((dq.peekFirst() == '(' && dq.peekLast() == '(' )) { | |
index++; | |
dq.removeLast(); | |
dq.removeFirst(); | |
} | |
else if (dq.peekFirst() == ')' && dq.peekLast() == ')' ) | |
{ | |
index++; | |
dq.removeLast(); | |
dq.removeFirst(); | |
} | |
else if(dq.peekFirst() == ')' && dq.peekLast() == '(' ) | |
{ | |
index++; | |
index++; | |
dq.removeLast(); | |
dq.removeFirst(); | |
} | |
System.out.println(dq.toString()); | |
} | |
System.out.println(" Changed: " + index); | |
return index; | |
} | |
public static void printArray(char input[], int size) { | |
for(int i=0; i < size; i++){ | |
System.out.print(input[i] + " "); | |
} | |
System.out.println(); | |
} | |
public static void main(String args[]){ | |
RemoveExtraBrackets reb = new RemoveExtraBrackets(); | |
//char input1[] = ")(".toCharArray(); | |
//char input1[] = ")))()(()".toCharArray(); | |
//char input1[] = "((((".toCharArray(); | |
//char input1[] = "(((())".toCharArray(); | |
char input1[] = ")(())(((".toCharArray(); | |
int pos = reb.remove(input1); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment