Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
bool DuplicateBraces(const char * exp, int len)
{
stack<int> braceIndices;
int lastPop = 0;
int prevIndex = -1;
for (int i = 0; i < len; i++)
{
if (exp[i] == ' ')
continue;
if (exp[i] == '(')
{
braceIndices.push(i);
lastPop = 0;
}
else if (exp[i] == ')')
{
int topIndex = braceIndices.top();
if (((prevIndex - topIndex) == 1) && lastPop == 1)
return true;
braceIndices.pop();
prevIndex = topIndex;
lastPop = 1;
}
else
{
lastPop = 0;
}
}
return false;
}
public class Parenthesis{
public static void main(String []args){
System.out.println("Parenthesis valid : "
+ hasValidParenthesis("abcd"));
}
public static boolean hasValidParenthesis(String s) {
// negative conditions
if( null == s ) return false;
if( s.isEmpty() ) return false;
if( s.indexOf('(') == -1 && s.indexOf(')') == -1 ) return false;
// to track matching Parenthesis
int count = 0;
// to track each char
int index = 0;
// array to know if there is content between two parenthesis
boolean[] contentArray = new boolean[50];
for(char c : s.toCharArray()) {
if( c == '(') {
count++;
} else if ( c == ')') {
if( count == 0 ) {
// ')' encountered without any prior '('
return false;
}
// if content is not present between ( and ), then
// treat them as a duplicate entry
if( false == contentArray[count-1] ) {
return false;
}
contentArray[count-1] = false;
// decrement Parenthesis count
count --;
} else if( count > 0 ) {
// store the content between parenthesis
if(!contentArray[count-1])
contentArray[count-1] = true;
}
// increment index
index++;
}
return (count == 0);
}
}
Hi,can you describe what "duplicate" here means? I am understanding it means more than one ")" or "(" or "}" or "{"
public static int FindDuplicateParnth(string s)
{
s = s.Replace(" ", "");
Stack<Parenth> stack = new Stack<Parenth>();
char c;
int lastOpen = - 1, lastClose = -1;
for (int i = 0; i < s.Length; i++)
{
c = s[i];
if (c != '(' && c != ')')
continue;
if (c == '(')
{
stack.Push(new Parenth(c, i));
continue;
}
if(c == ')')
{
if(stack.Peek().position + 1 == lastOpen && i - 1 == lastClose)
{
return lastOpen;
}
lastOpen = stack.Pop().position;
lastClose = i;
continue;
}
}
return -1;
}
If white spaces are removed, then for any two pairs of parenthesis in the expression, there are 5 kinds of cases we need to take care of:
1.((exp)) such as ((a+b))
2.(exp(exp)) such as (a-(b+c))
3.((exp)exp) such as ((a+b)*c)
4.(exp(exp)exp) such as (a/(b-c)+d)
5.(exp)exp(exp) such as (a+b)/(c*d)
Only the first kind has redundant outside parenthesis, so all we need to do is find out the ocurrances of two pairs of parenthesis like the first kind.
Following is code in C++11:
#include <cctype>
#include <stack>
#include <vector>
#include <string>
#include <utility>
#include <iostream>
#include <unordered_map>
using namespace std;
void buildMapOfStringWithoutSpaces(string& s, unordered_map<int,int>& positionMap, const string& src)
{
for(int k = 0, i = 0, len = src.size(); i < len; ++i){
if(isspace(src[i])) continue;
s.push_back(src[i]);
positionMap[k++] = i;
}
}
void remap(vector<pair<int,int> >& v, unordered_map<int,int>& positionMap)
{
for(int i = 0, n = v.size(); i < n; ++i){
v[i].first = positionMap[v[i].first];
v[i].second = positionMap[v[i].second];
}
}
void findRedundantParenthesis(vector<pair<int,int> >& v, const string& exp)//exp has no spaces
{
v.clear();
if(exp.empty()) return;
stack<int> st;
for(int i = 0, len = exp.size(); i < len; ++i){
if(exp[i] == '('){
if(!st.empty() && exp[st.top()] == ')'){//previous right's pair has no reduntant
st.pop();
st.pop();
}
st.push(i);
}
else if(exp[i] == ')'){
if(exp[st.top()] == ')'){//check if this pair is redundant
int preRight = st.top();
st.pop();
int preLeft = st.top();
st.pop();
if(i == preRight + 1 && st.top() == preLeft - 1){//this pair is redundant
v.push_back(make_pair(st.top(), i));
}
}
st.push(i);
}
}
}
int main()
{
vector<pair<int,int> > v;
string expWithoutSpaces;
unordered_map<int,int> positionMap;
buildMapOfStringWithoutSpaces(expWithoutSpaces, positionMap, "((( a + b ) * (( c - d ))))");
findRedundantParenthesis(v, expWithoutSpaces);
if(!v.empty()){
remap(v, positionMap);
cout << "redundant parenthesis are at:\n";
for(int i = 0; i < v.size(); ++i){
cout << "(" << v[i].first << ", " << v[i].second << ")\n";
}
}
return 0;
}
time complexity O(n), space complexity O(n)
a naive approach is traverse the string, left to right, for occurrence of )) and replace then with some unicode char(which is not part of string). Traverse again in string from right to left to find occurrence of (( again replacing consequent pair with same unicode.
Then we can just check the balance using a stack. If its balanced we have duplicates.
let me know loopholes, as I am not entirely sure about this approach
From my understanding of the question, regexp are much more easier and should do too. Or am I ignoring something?
String inputData = "(( a + b ) + (( c + d )))";
inputData = inputData.replaceAll("\\(+", "\\(");
inputData = inputData.replaceAll("\\)+", "\\)");
expressionString = (( a + b ) + (( c + d )))
Step1 : In the expression look for "((" and store in a string - subStr
Step2: Look for the next occurrence of ')' and store its index
Step3: Look for the character at index+1
if(expressionString.charAt(index+1) == ')'){
print("expression contains duplicate parenthesis ");
break;
}
else{
subStr = " ";
}
@Miral and @Sehs -
For finding duplicate parenthesis... this simple means your statement would be having "((" i.e., two starting parenthesis... once you find this.. find the next closing parenthesis.. ')' and if the next character in the string is also ')' then this means duplicate parenthesis exist...
@Miral - Sorry that was a big miss-
Considered two examples
Eg1 - ((a+b)+((c+d)))
eg2 - (((a+b) + cc))
and I changed my algo to-
Step 1 - Store the index of '(' in an 'opening_paren' array from the expression.
Step 2 - On occurrence of ')' store its index in a 'closing_paren' array and now check for the next index and if the next index is also ')' then calculate the difference in indexes and if the last two elements of both array have difference in index as 1 then it means duplicate.
Lets see the below example -
eg1- (((a+b) + c))
opening_paren
0
1
2
closing_paren
6
and 7 index is not ')' i remove 2 and 6 from the list
opening_paren
0
1
closing_paren
9
10
Now as we can see the difference between indexes is 1 on both the arrays which would lead to duplicate parenthesis.
package com.sample;
import java.util.ArrayList;
import java.util.List;
public class Sample1 {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
String x = "(( a + b )) + (( c + d )))";
List list = new ArrayList();
for(int i=0;i<x.length();i++){
if(x.charAt(i)=='(' && x.charAt(i+1)!=')' && x.charAt(i+1)!='(' && i != x.length()-1){
list.add(i);
}
if(x.charAt(i)==')' && x.charAt(i-1)!=')' && x.charAt(i-1)!='(' && i!=0){
list.add(i);
}
}
System.out.println(list);
for(int i=0;i<list.size();i=i+2){
if(Integer.valueOf(list.get(i).toString())!=0 &&
x.charAt(Integer.valueOf(list.get(i).toString())-1)=='('&&
x.charAt(Integer.valueOf(list.get(i+1).toString())+1)==')'){
System.out.println("Duplicate braces found at starting position "+
(Integer.valueOf(list.get(i).toString())-1)+" and ending position "+
(Integer.valueOf(list.get(i+1).toString())+1));
}
}
}
}
public static void removeDuplicate(String exp){
int end = exp.length() - 1 ;
char [] chs = exp.toCharArray() ;
Stack<Character> stack = new Stack<Character>();
for (int i = 0 ; i <= end ; ++i){
if (chs[i] == '('){
if (!stack.isEmpty() && stack.peek() == '('){
System.out.println("find " + stack.peek() + chs[end--]);
stack.pop();
}
}
stack.push(chs[i]);
}
for (Character c : stack){
System.out.print(c);
}
}
public static void removeDuplicate(String exp){
int end = exp.length() - 1 ;
char [] chs = exp.toCharArray() ;
Stack<Character> stack = new Stack<Character>();
for (int i = 0 ; i <= end ; ++i){
if (chs[i] == '('){
if (!stack.isEmpty() && stack.peek() == '('){
System.out.println("find " + stack.peek() + chs[end--]);
stack.pop();
}
}
stack.push(chs[i]);
}
for (Character c : stack){
System.out.print(c);
}
}
There's a duplicate version of this question, could not post a link to the original post since careercup.com does not allow links in comments but the Question ID is 12011927.
Here's my version in C#:
// Iterate through the string and for each character,
// if the character is a '(' or any of the operators
// push it to the stack
// If the character is a ')', then pop any operators and the
// matching '('. However when you try to pop if you only find a '('
// then this means it is a duplicate paranthesis.
static int GetNumberOfDuplicateParanthesis(string input)
{
int countOfDuplicates = 0;
input = input.Replace(" ", "");
Stack<char> chars = new Stack<char>();
for (int i = 0; i < input.Length; i++)
{
if ((input[i] == '(') ||
(input[i] == '+') ||
(input[i] == '*') ||
(input[i] == '-') ||
(input[i] == '/'))
{
chars.Push(input[i]);
}
else if (input[i] == ')')
{
if (chars.Peek() == '(')
{
countOfDuplicates++;
Console.WriteLine("Duplicate paranthesis found at {0}", i);
}
else
{
bool done = false;
while (!done)
{
if (chars.Peek() == '(')
{
done = true;
}
chars.Pop();
}
}
}
}
return countOfDuplicates;
}
bool DuplicateBraces(const char * exp, int len)
{
stack<int> braceIndices;
int lastPop = 0;
int prevIndex = -1;
for (int i = 0; i < len; i++)
{
if (exp[i] == ' ')
continue;
if (exp[i] == '(')
{
braceIndices.push(i);
lastPop = 0;
}
else if (exp[i] == ')')
{
int topIndex = braceIndices.top();
if (((prevIndex - topIndex) == 1) && lastPop == 1)
return true;
braceIndices.pop();
prevIndex = topIndex;
lastPop = 1;
}
else
{
lastPop = 0;
}
}
return false;
}
bool DuplicateBraces(const char * exp, int len)
{
stack<int> braceIndices;
int lastPop = 0;
int prevIndex = -1;
for (int i = 0; i < len; i++)
{
if (exp[i] == ' ')
continue;
if (exp[i] == '(')
{
braceIndices.push(i);
lastPop = 0;
}
else if (exp[i] == ')')
{
int topIndex = braceIndices.top();
if (((prevIndex - topIndex) == 1) && lastPop == 1)
return true;
braceIndices.pop();
prevIndex = topIndex;
lastPop = 1;
}
else
{
lastPop = 0;
}
}
return false;
}
((a+b)) in this example one operator is there so there should be only one open braces should present, ((a)) in this case zero, ((a*b)+(a-b)) in this case three.
So just find out the count of open braces and number of operators.If they equal no duplicates, if not duplicates are present.
if it is wrong please correct me.
thanks.
push the open parenthesis and the operators and check the top element on seeing a closing parenthesis. If it is open one we have duplicate.
int check(char s[])
{
int i=0;
char ch;
while(s[i]!='\0')
{
if(s[i]=='(' || s[i]=='+' || s[i]=='-' || s[i]=='*' || s[i]=='/')
push(s[i]);
else if(s[i]==')')
{
ch=pop();
if(ch=='(')
return 1;
while((ch=pop())!='(')
;
}
i++;
}
return 0;
}
Here is a working version in Python.
def find_duplicate(expr):
stack=[]
char_in_between = 0
for i in range(0, len(expr)):
if expr[i] == '}' or expr[i] == ')':
pair = '{' if expr[i] == '}' else '('
pop=''
while(len(stack) > 0 and pop != pair):
pop = stack.pop()
if (pop != '{' and pop != '('): char_in_between +=1
if char_in_between == 0:
print "duplicate parenthesis!!"
break
char_in_between = 0
else:
stack.append(expr[i])
Step 1: Run through the code
Step 2: Search for the brackets
Step 3: search for a '( )' pair
Step 3a: If there is another opening bracket just before '(' and if there is a closing bracket just after ')' ;then there is a duplicate
Step 3b : Else; replace the section '(.....)' by some characters say 'XYZ..'.
Step 4: Repeat from step 3 until u reach the outermost bracket .
Am i correct??
package misc;
import java.util.*;
public class RemoveDupeBrackets2 {
public static void main(String[] args) {
String expression = "(((a+b)+c))";
new RemoveDupeBrackets2().removeDupes(expression);
}
private void removeDupes(String expression) {
char[] chars = expression.toCharArray();
LinkedList<BracketPair> pairs = new LinkedList<BracketPair>();
for (int i = 0; i < chars.length; i++) {
char aChar = chars[i];
if (aChar == '(') {
BracketPair pair = new BracketPair();
pair.leftIdx = i;
pairs.add(pair);
} else if (aChar == ')') {
ListIterator<BracketPair> iterator = pairs.listIterator(pairs.size());
while (iterator.hasPrevious()) {
BracketPair pair = iterator.previous();
if (pair.rightIdx == null) {
pair.rightIdx = i;
break;
}
}
}
}
for (BracketPair pair : pairs) {
System.out.println(pair);
}
HashSet<BracketPair> set = new HashSet<BracketPair>(pairs);
for (BracketPair next : set) {
BracketPair possibleDupe = new BracketPair();
possibleDupe.leftIdx = next.leftIdx - 1;
possibleDupe.rightIdx = next.rightIdx + 1;
if (set.contains(possibleDupe)) {
System.out.println("Dupe pair : " + possibleDupe);
chars[possibleDupe.leftIdx] = ' ';
chars[possibleDupe.rightIdx] = ' ';
}
}
System.out.println(String.valueOf(chars));
}
class BracketPair {
Integer leftIdx = null;
Integer rightIdx = null;
BracketPair() {
}
@Override
public String toString() {
return "BracketPair{" +
"leftIdx=" + leftIdx +
", rightIdx=" + rightIdx +
'}';
}
@Override
public boolean equals(Object o) {
BracketPair that = (BracketPair) o;
return this.leftIdx.equals(that.leftIdx) && this.rightIdx.equals(that.rightIdx);
}
@Override
public int hashCode() {
int result = leftIdx != null ? leftIdx.hashCode() : 0;
result = 31 * result + (rightIdx != null ? rightIdx.hashCode() : 0);
return result;
}
}
}
Hi,
Here is my implementation with Java.
I assumed that :
1. Given expression is valid, which means all open brackets are closed.
2. Given expression can not be null.
3. Given expression does not contain negatives. (-a + b) negative a is not possible.
Here is the main class :
public class RemoveUselessBracketsInExpression {
public String removeBrackets(String expression) {
String cleanExpression = removeSpaces(expression);
String result = remove(cleanExpression);
return result;
}
private String remove(String expression) {
Tree tree = createExpressionTree(expression);
walkOnTreeAndRemoveBrackets(tree.head);
return createExpressionFromNode(tree.head);
}
private Tree createExpressionTree(String expression) {
Tree tree = new Tree();
tree.head = trimBracketsAndCreateNode(expression);
return tree;
}
private void walkOnTreeAndRemoveBrackets(Node node) {
node.hasBrackets = false;
hasInnerExpressionWithDifferentOperator(node);
}
private String createExpressionFromNode(Node node) {
StringBuilder sb = new StringBuilder();
if (node.hasBrackets) {
sb.append("(");
}
if (node.operator != 0) {
sb.append(createExpressionFromNode(node.left));
sb.append(node.operator);
sb.append(createExpressionFromNode(node.right));
} else {
sb.append(node.expression);
}
if (node.hasBrackets) {
sb.append(")");
}
return sb.toString();
}
private void hasInnerExpressionWithDifferentOperator(Node node) {
if (node.operator != 0) {
if (node.operator == node.left.operator
|| getPrecedence(node.operator) <= getPrecedence(node.left.operator)) {
node.left.hasBrackets = false;
}
if (node.operator == node.right.operator
|| getPrecedence(node.operator) <= getPrecedence(node.right.operator)) {
node.right.hasBrackets = false;
}
hasInnerExpressionWithDifferentOperator(node.left);
hasInnerExpressionWithDifferentOperator(node.right);
}
}
private Node trimBracketsAndCreateNode(String expression) {
boolean hasBrackets = false;
boolean contuniue = true;
String trimmedExpression = expression;
while (contuniue) {
hasBrackets = checkHasBrackets(trimmedExpression);
if (hasBrackets) {
trimmedExpression = trimmedExpression.substring(1, trimmedExpression.length() - 1);
}
if (!checkHasBrackets(trimmedExpression)) {
contuniue = false;
}
}
return createNode(trimmedExpression, hasBrackets);
}
private Node createNode(String expression, boolean hasBrackets) {
System.out.println(expression);
int operatorIndex = getOperatorIndex(expression);
Node node = new Node();
node.expression = expression;
if (operatorIndex != -1) {
node.operator = expression.charAt(operatorIndex);
}
if (operatorIndex == -1) {
node.hasBrackets = false;
} else {
node.hasBrackets = hasBrackets;
}
if (operatorIndex != -1) {
node.left = trimBracketsAndCreateNode(expression.substring(0, operatorIndex));
node.right = trimBracketsAndCreateNode(expression.substring(operatorIndex + 1));
}
return node;
}
private boolean checkHasBrackets(String expression) {
int openBrackets = 0;
for (int i = 0; i < expression.length(); i++) {
char c = expression.charAt(i);
if (c == '(') {
openBrackets++;
}
if (c == ')') {
openBrackets--;
}
if (openBrackets == 0 && i < expression.length() - 1) {
return false;
}
}
return expression.charAt(0) == '(' && expression.charAt(expression.length() - 1) == ')';
}
private int getOperatorIndex(String expression) {
int openBrackets = 0;
for (int i = 0; i < expression.length(); i++) {
char c = expression.charAt(i);
if (c == '(') {
openBrackets++;
}
if (c == ')') {
openBrackets--;
}
if (openBrackets == 0) {
if (c == '-' || c == '+' || c == '*' || c == '/') {
return i;
}
}
}
return -1;
}
private String removeSpaces(String expression) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < expression.length(); i++) {
char c = expression.charAt(i);
if (c != ' ') {
sb.append(c);
}
}
return sb.toString();
}
private int getPrecedence(char operator) {
switch (operator) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
default:
return -1;
}
}
class Tree {
Node head;
}
class Node {
Node left;
Node right;
String expression;
boolean hasBrackets;
char operator;
}
}
I tested this implementation with these cases :
(testing more than one case in a test is not practical, but I preferred to keep simple for this page)
public class RemoveUselessBracketsInExpressionTest {
private RemoveUselessBracketsInExpression ru;
@Before
public void setup() {
ru = new RemoveUselessBracketsInExpression();
}
@Test
public void test01() {
assertEquals("a", ru.removeBrackets("a"));
assertEquals("a", ru.removeBrackets(" a "));
assertEquals("a+b", ru.removeBrackets(" (a + b) "));
assertEquals("a+b+c", ru.removeBrackets(" ( a + ( b + c ) ) "));
assertEquals("a+b+c+d", ru.removeBrackets(" ( ( a + b ) + ( c + d ) ) "));
assertEquals("(a+b)*(c+d)", ru.removeBrackets(" ( ( a + b ) * ( c + d ) ) "));
assertEquals("a*(b+c)", ru.removeBrackets(" ( a * ( b + c ) ) "));
assertEquals("a-b*(c+d)", ru.removeBrackets(" ( a - b * ( c + d ) ) "));
assertEquals("a-b*c+d", ru.removeBrackets("a - b * c + d"));
assertEquals("a-b*c*d", ru.removeBrackets("a - b * (c * d)"));
assertEquals("a-b*c*d/e", ru.removeBrackets("a - b * c * (d / e)"));
assertEquals("a-b*c*d/e", ru.removeBrackets("a - (b * c) * (d / e)"));
assertEquals("a-(b+c)*d/e", ru.removeBrackets("a - (b + c) * (d / e)"));
assertEquals("(a-b+c)*d/e", ru.removeBrackets("(a - b + c) * (d / e)"));
assertEquals("(a-b+c)*d/e", ru.removeBrackets("(a - (b) + c) * (d / e)"));
assertEquals("a+b-c+d/e", ru.removeBrackets("(a + (b - c) + (d / e))"));
assertEquals("a+b-c+d/e", ru.removeBrackets("(a + ((b - c)) + (d / e))"));
assertEquals("a+b-c*d/e", ru.removeBrackets("a + b - c * d / e"));
assertEquals("(a*b-c)/(d-e)", ru.removeBrackets("((a * b) - c) / (d - e)"));
assertEquals("(a-b+c)/d-e", ru.removeBrackets("((a - b) + (c)) / d - e"));
assertEquals("(a+b*c)*d*f*j", ru.removeBrackets("(a + (b*c)) * (d * ( f * j) ) "));
}
}
public class FindDuplicateParenthesis {
public static void main(String[] args) {
String str = "(( a + b ) ()+ ( c + d ))";
System.out.println(findduplicateparenthe(str));
}
public static boolean findduplicateparenthe(String str){
Stack st = new Stack();
int counter = 0;
char arr[] = str.toCharArray();
for (int i=0; i< str.length();i++){
if(arr[i] == '('){
st.push(arr[i]);
// System.out.println(arr[i]);
counter++;
if(arr[i] == '(' && arr[i] == '\0'){
System.out.println("false1");
return false;}
}
if(arr[i] == ')'){
st.pop();
// System.out.println(arr[i]);
counter--;
if(arr[i] == '\0') {
System.out.println("true1");
return true;
}
}
}
if(counter == 0){
return true;}
else{
return false;}
}
}
Here is the algorithm and implementation in Objective-C
Stacks is implemented using NSMutableArray
1.if ( --> check if lastObject in ORStacks is ( ; then append ( to String or push ( to ORStacks
2.if operator/operand append to String
3.if ) --> check if lastObject in ORStacks is ( ;then push ) to String,pop ORStacks if ORStacks is not empty;else move to the next one
//Eliminate duplicate parantheses in expression
#import<Foundation/Foundation.h>
#import<UIKit/UIKit.h>
@interface DuplicateParantheses
@property(nonatomic)NSMutableArray *stacks;
@property(nonatomic)NSString *output;
-(NSString*)removeDuplicateFromExpression:(NSString*)expression;
@end
@implementation DuplicateParantheses
-(NSMutableArray*)stacks
{
if(!_stacks)
{
_stacks = [[NSMutableArray alloc]init];
}
return _stacks;
}
-(NSString*)output
{
if(!_output)
{
_output = [[NSString alloc]init];
}
return _output;
}
-(NSString*)removeDuplicateFromExpression:(NSString*)expression
{
for(int i=0;i< expression.length-1;i++)
{
NSString *item = [NSString stringFromChar:[expression characterAtIndex:i]];
if([item isEqualToString@"("] && [[self.stacks lastObject]isEqualToString:@"("])
[self.output appendStringFromString:item];
elseif([item isEqualToString@"("]) [self.stacks addObject:item];
elseif([item isEqualToString@")"]&& [[self.stacks lastObject]isEqualToString:@"("])
{
[self.output appendStringFromString:item];
if([self.stacks length])[self.stacks removeLastObject];
}
else
{
[self.output appendStringFromString:item];
}
}
return output;
}
@end
#include <iostream>
#include <string>
using namespace std;
int main()
{
string expr;
char prev='0';
int count_at_suspect_duplicate;
cin >>expr;
int count=0;
for(int i=0; i<expr.length(); i++)
{
if (expr[i] == '(')
{
if (prev == '(') //assumption that string has had whitespace removed
count_at_suspect_duplicate=count;
count++;
}
if (expr[i] ==')')
{
if (prev==')')
if (count_at_suspect_duplicate==count)
cout<< "location "<<i+1<<" contains duplicate\n";
}
count--;
prev=expr[i];
}
}
As far as I understand this is parenthesis matching problem:
1- If you just want to check if all parenthesis are matching, you can do that in O(n) time and O(1) space. Loop over all chars in the string, whenever you find "(" increase a counter and whenever you find ")" decrease the counter and the final result must equal to 0. Here is a sample C# code:
bool CheckMatchingParenthesis(string expression)
{
int count = 0;
for(int I=0; I < expression.Length; I++)
{
if( expression[I] == '(' )
count++;
else if (expression[I] == ')' )
count--;
if(count < 0)
return false; //Closing ')' that is not matched
}
return count == 0;
}
2- If you want the index of all unmatched parenthesis, you need two stacks: one for opening '(' (say S1) and one for unmatched closing ')' (Say S2). Whenever you find an opening ( you add its index to the stack S1, whenever you find a closing ')' you remove the top element from S1, if S1 was already empty (unmatched closing tag), then add index of ')' to S2. Here is a sample code
int[] GetUnMatchedParenthesis(string expression)
{
Stack opening = new Stack();
Stack closing = new Stack();
for(int I=0; I < expression.Length; I++)
{
if( expression == '(' )
{
opening.Push(I);
}
if( expression == ')' )
{
if(opening.IsEmpty())
{
closing.Push(I);
}
else
{
opening.Pop();
}
}
}
int[] res = new int[0];
Array.AddRange(res, opening.ToArray());
Array.AddRange(res, closing.ToArray());
return res;
}
This will take O(n) time and worst case of O(n) space (if all parenthesis are opening or closing)
he didn't say it was a parenthesis matching problem. he said the requirement is to find duplicate paranetheses such as in the example he gave... a simpler example:
((a))
@Miral and @Sehs -
For finding duplicate parenthesis... this simple means your statement would be having "((" i.e., two starting parenthesis... once you find this.. find the next closing parenthesis.. ')' and if the next character in the string is also ')' then this means duplicate parenthesis exist...
You can use stack, start pushing each character from input string till you not hit close parenthesis. When you hit close parenthesis, start pop the element till you not hit open parenthesis. If the immediate pop hit open parenthesis than that is duplicate parenthesis.
Note: this algo will fail, if one put false parenthesis in string like: () .... Code as:
- Rajesh Kumar May 02, 2014