Given an expression string exp, write a program to examine whether the pairs and the orders of “{“,”}”,”(“,”)”,”[","]” are correct in exp. For example, the program should print true for exp = “[()]{}{[()()]()}” and false for exp = “[(])”
Algorithm:
1) Declare a character stack S.
2) Now traverse the expression string exp.
a) If the current character is a starting bracket (‘(‘ or ‘{‘ or ‘[') then push it to stack.
b) If the current character is a closing bracket (')' or '}' or ']‘) then pop from stack and if the popped character is the matching starting bracket then fine else parenthesis are not balanced.
3) After complete traversal, if there is some starting bracket left in stack then “not balanced”
Read full article from Check for balanced parentheses in an expression | GeeksforGeeks
Algorithm:
1) Declare a character stack S.
2) Now traverse the expression string exp.
a) If the current character is a starting bracket (‘(‘ or ‘{‘ or ‘[') then push it to stack.
b) If the current character is a closing bracket (')' or '}' or ']‘) then pop from stack and if the popped character is the matching starting bracket then fine else parenthesis are not balanced.
3) After complete traversal, if there is some starting bracket left in stack then “not balanced”
bool isMatchingPair(char character1, char character2){ if(character1 == '(' && character2 == ')') return 1; else if(character1 == '{' && character2 == '}') return 1; else if(character1 == '[' && character2 == ']') return 1; else return 0;}bool areParenthesisBalanced(char exp[]){ int i = 0; /* Declare an empty character stack */ struct sNode *stack = NULL; /* Traverse the given expression to check matching parenthesis */ while(exp[i]) { /*If the exp[i] is a starting parenthesis then push it*/ if(exp[i] == '{' || exp[i] == '(' || exp[i] == '[') push(&stack, exp[i]); /* If exp[i] is a ending parenthesis then pop from stack and check if the popped parenthesis is a matching pair*/ if(exp[i] == '}' || exp[i] == ')' || exp[i] == ']') { /*If we see an ending parenthesis without a pair then return false*/ if(stack == NULL) return 0; /* Pop the top element from stack, if it is not a pair parenthesis of character then there is a mismatch. This happens for expressions like {(}) */ else if ( !isMatchingPair(pop(&stack), exp[i]) ) return 0; } i++; } /* If there is something left in expression then there is a starting parenthesis without a closing parenthesis */ if(stack == NULL) return 1; /*balanced*/ else return 0; /*not balanced*/}
No comments:
Post a Comment