Program in C As you most probably know, any boolean expression can be expressed

Question

Program in C

As you most probably know, any boolean expression can be expressed in either a disjunctive normal form or a conjunctive normal form. In a disjunctive normal form, a boolean expression is written as a disjunct (logical or) of one-or more sub-expressions where each of these sub-expressions is written in a conjunctive normal form. Similarly, an expression written in a conjunctive normal form is a conjunct (logical and) of sub-exp each written in a disjunctive normal form. An AND/OR tree is a tree-like graphical representation of boolean expressions written as either conjunctive- or disjunctive-normal form. Since the sub-expressions of a normalized form alternate in being either disjunctive or conjunctive forms, you'd expect the sub-trees on an AND/OR tree to alternate in being AND- or OR- trees depending on the sub-tree's depth-level. The example on the right illustrates this observation for the boolean expression (A (B C)) (D E) where the trees in the 1st (top-most) and 3rd levels are AND-trees. Write a program that evaluates a given and/or tree. Input Format Your program will be tested on one or more test cases. Each test case is specified on exactly one line (which is no longer than 32,000 characters) of the form: (E_1 E_2...E_n) where n > 0 and E_i is either T for true, F for false, or a sub-expression using the same format. The trees at the deepest level are AND-trees. The last test case is followed by a dummy line made of (). Output Format For each test case, print the following line: Where k is the test case number (starting at one, ) and E is either true or false depending on the value of the expression in that test case.

Explanation / Answer

/*
* The logic is as follows :
* Scan the expression and push onto stack, if char is not ending parenthesis.
* If scanned char is opening parenthesis, then increase level cnt.
* If scanned char is ending parenthesis, then evaluate by poping stack,
* until we get opening parenthesis.
* If level cnt is odd, then we need to do AND, otherwise do OR.
*/

#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);

/*
* Return 0 if expression evaluates to FALSE
* Return 1 if expression evaluates to TRUE
* Return 2 if expression is ()
*/
int eval_expr(char exp[])
{
int cnt = 0, flag = 0;
int result = 2;
int i = 0;

/* Declare an empty character stack */
struct sNode *stack = NULL;

/* Traverse the given expression to evaluate */
while (exp[i])
{
/*If the exp[i] is a not ending parenthesis then push it*/
if (!(exp[i] == ')')) {
  push(&stack, exp[i]);
  /* Increase cnt, if opening parenthesis. */
  /* cnt is used to track depth of and-or tree. */
  if(exp[i] == '(')
      cnt++;
  i++;   
  continue;
}
   
    /*
     * If the exp[i] is ending parenthesis, then evaluate expression
     * from stack, untill opening parenthesis is found.
     * cnt is used to determine if we need to AND or OR at this level.
     */
   
    char c_val = pop(&stack);
int value;

if(c_val == 'T')
     value = 1;
else if(c_val == 'F')
     value = 0;
    
while (!(c_val == '('))
{
        if(cnt%2 == 1) {
            if (flag == 0) {
                result = value;
                flag = 1;
            } else
                result = result & value;
        } else {
            if (flag == 0) {
                result = value;
                flag = 1;
            } else
                result = result | value;
        }       
        c_val = pop(&stack);
        if(c_val == 'T')
         value = 1;
     else if(c_val == 'F')
         value = 0;
}
cnt--;
i++;
}

return result;
}

int main()
{
char exp[100];
int idx = 0;
int ans = 0;
do {
    scanf("%s", exp);
    idx++;
   
    ans = eval_expr(exp);
    if(ans==0)
        printf("%d. false ", idx);
    else if(ans==1)
        printf("%d. true ", idx);
       
} while (ans != 2);
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 ");
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 ");
getchar();
exit(0);
}
else
{
top = *top_ref;
res = top->data;
*top_ref = top->next;
free(top);
return res;
}
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.