title: Parenthesis Matching with Boolean Expression
body: <pre><code>//JOSE DENNIS CHUA 
  
  #include&lt;stdio.h&gt;
  #include&lt;stdlib.h&gt;
  #include&lt;string.h&gt;
  #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 == '(' &amp;&amp; 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] == '(')
          push(&amp;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] == ')')
        {
  
            /*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(&amp;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];
  
  printf("Enter String: ");
    gets(exp);
    if(areParenthesisBalanced(exp))
      printf("\n Balanced ");
    else
      printf("\n Not Balanced ");  \
    getchar();
  }    
  
  /* 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-&gt;data  = new_data;
  
    /* link the old list off the new node */
    new_node-&gt;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-&gt;data;
       *top_ref = top-&gt;next;
       free(top);
       return res;
    }
  }
  </code></pre>
  
  <p>This is my Code, and I dont have idea where to put the code for separating the boolean expression for the parenthesis.. can anyone give me code for this..</p>
  
  <h2>Problem Definition.</h2>
  
  <p>In computer science, a Boolean expression is an expression in a programming language that produces a Boolean value when evaluated, i.e. one of true or false. A Boolean expression may be composed of a combination of the Boolean constants true or false, Boolean-typed variables, Boolean-valued operators, and Boolean-valued functions [wiki]. Examples of Boolean expression are the following: </p>
  
  <pre><code>x&lt;=1
  ((x&gt;0) &amp;&amp; (x&lt;10))
  (!x || !y)
  </code></pre>
  
  <p>With the use of parenthesis in grouping Boolean expressions within another Boolean expression, your task is to develop a module that will identify if a given Boolean expression is correct in terms of the pairing of parenthesis present in the expression.</p>
  
  <h2>Example Program Output.</h2>
  
  <pre><code>Input String (Boolean Expression): xValue&lt;=1
  
  Identification Result: Parenthesis pairs complete
  
  Input String (Boolean Expression): ((teen&gt;9) &amp;&amp; (teen&lt;20))
  
  Identification Result: Parenthesis pairs complete
  
  Input String (Boolean Expression): (!myAge) || !yourAge)
  
  Identification Result: Parenthesis pairs incomplete
  
  Input String (Boolean Expression): (total&lt;=0( || )total&gt;=10)
  
  Identification Result: Parenthesis pairs incomplete
  </code></pre>
  
  <h2>Mandatory Requirement.</h2>
  
  <p>Apply the Stack ADT concept in solving the given problem. You are free to choose either array or linkedlist implementation provided that the only limit of the program during execution is the memory space.</p>