The best data structure to check whether an arithmetic expression has balanced parentheses is a (GATE CS 2004)
(A) queue
(B) stack
(C) tree
(D) list
Answer: (B)
Explanation: There are three types of parentheses [ ] { } (). Below is an arbit c code segment which has parentheses of all three types.
void func(int c, int a[]) { return ((c +2) + arr[(c-2)]) ; } |
Stack is a straightforward choice for checking if left and right parentheses are balanced. Here is a algorithm to do the same.
/*Return 1 if expression has balanced parentheses */bool areParenthesesBalanced(expression ) { for each character in expression { if(character == ’(’ || character == ’{’ || character == ’[’) push(stack, character); if(character == ’)’ || character == ’}’ || character == ’]’) { if(isEmpty(stack)) return 0; /*We are seeing a right parenthesis without a left pair*/ /* Pop the top element from stack, if it is not a pair bracket of character then there is a mismatch. This will happen for expressions like {(}) */ else if (! isMatchingPair(pop(stack), character) ) return 0; } } if(isEmpty(stack)) return 1; /*balanced*/ else return 0; /*not balanced*/ } /* End of function to check parentheses */ /* Returns 1 if character1 and character2 are matching left and right parentheses */bool isMatchingPair(character1, character2) { if(character1 == ‘(‘ && character2 == ‘)’) return 1; else If(character1 == ‘{‘ && character2 == ‘}’) return 1; else If(character1 == ‘[‘ && character2 == ‘]’) return 1; else return 0; } |
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
