{"id":27010,"date":"2018-01-02T20:44:07","date_gmt":"2018-01-02T15:14:07","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27010"},"modified":"2018-01-02T20:44:07","modified_gmt":"2018-01-02T15:14:07","slug":"check-balanced-parentheses-expression","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/check-balanced-parentheses-expression\/","title":{"rendered":"Check for balanced parentheses in an expression"},"content":{"rendered":"

Given an expression string exp , write a program to examine whether the pairs and the orders of \u201c{\u201c,\u201d}\u201d,\u201d(\u201c,\u201d)\u201d,\u201d[\u201c,\u201d]\u201d are correct in exp. <\/span>For example, the program should print true for exp = \u201c[()]{}{[()()]()}\u201d and false for exp = \u201c[(])\u201d<\/p>\n

Algorithm:<\/strong>
\n1) Declare a character stack S.
\n2) Now traverse the expression string exp.
\na) If the current character is a starting bracket (\u2018(\u2018 or \u2018{\u2018 or \u2018[\u2018) then push it to stack.
\nb) If the current character is a closing bracket (\u2018)\u2019 or \u2018}\u2019 or \u2018]\u2019) then pop from stack and if the popped character is the matching starting bracket then fine else parenthesis are not balanced.
\n3) After complete traversal, if there is some starting bracket left in stack then \u201cnot balanced\u201d<\/p>\n

Implementation:<\/p>\n

C Programming:<\/strong><\/p>\n

<\/div> 
#include<stdio.h>#include<stdlib.h>#define bool int \/* structure of a stack node *\/struct sNode{   char data;   struct sNode *next;}; \/* Function to push an item to stack*\/void push(struct sNode** top_ref, int new_data); \/* Function to pop an item from stack*\/int pop(struct sNode** top_ref); \/* Returns 1 if character1 and character2 are matching left   and right Parenthesis *\/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;} \/*Return 1 if expression has balanced Parenthesis *\/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 an 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*\/}  \/* UTILITY FUNCTIONS *\/\/*driver program to test above functions*\/int main(){  char exp[100] = "{()}[]";  if (areParenthesisBalanced(exp))    printf("\\n Balanced ");  else    printf("\\n Not Balanced ");    return 0;}     \/* Function to push an item to stack*\/void push(struct sNode** top_ref, int new_data){  \/* allocate node *\/  struct sNode* new_node =            (struct sNode*) malloc(sizeof(struct sNode));   if (new_node == NULL)  {     printf("Stack overflow \\n");     getchar();     exit(0);  }              \/* put in the data  *\/  new_node->data  = new_data;   \/* link the old list off the new node *\/  new_node->next = (*top_ref);     \/* move the head to point to the new node *\/  (*top_ref)    = new_node;} \/* Function to pop an item from stack*\/int pop(struct sNode** top_ref){  char res;  struct sNode *top;   \/*If stack is empty then error *\/  if (*top_ref == NULL)  {     printf("Stack overflow \\n");     getchar();     exit(0);  }  else  {     top = *top_ref;     res = top->data;     *top_ref = top->next;     free(top);     return res;  }}<\/code><\/pre> <\/div>\n
Time Complexity: O(n)
\nAuxiliary Space: O(n) for stack.<\/p>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
Check for balanced parentheses in an expression- Data Structure – Given an expression string exp , write a program to examine whether the pairs <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[73012,79607],"tags":[80614,80613,80615,80610,80616,80606,80608,80609,80611,80612,80607],"class_list":["post-27010","post","type-post","status-publish","format-standard","hentry","category-data-structures","category-stack","tag-balanced-parentheses-algorithm","tag-balanced-parentheses-geeksforgeeks","tag-balanced-parentheses-java","tag-balanced-parentheses-python","tag-balanced-parentheses-recursion","tag-balanced-parentheses-using-stack-in-java","tag-balanced-parentheses-without-stack","tag-check-for-balanced-parentheses-in-an-expression-in-python","tag-parenthesis-matching-algorithm","tag-parenthesis-matching-using-stack-in-c","tag-parenthesis-matching-using-stack-in-data-structure"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27010","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27010"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27010\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27010"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27010"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27010"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}