IN C LANGUAGE As you most probably know, any boolean expression can be expressed
ID: 3810892 • Letter: I
Question
IN C LANGUAGE
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-expressions 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. V W A V B C W D E 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:
( E1 E2 ... En ) where n > 0 and Ei is either T for true, F for false, or a sub-expression using the same format. Where 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:
kuE
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.
Sample Input/Output tree.in:
((F(TF))
(TF))
(TFT)
((TFT)T)
()
OUTPUT
1. false
2. false
3. true
Explanation / Answer
#include<stdio.h>
typedef struct node {
char ch;
struct node *next;
} Node;
int parse(char *str) {
Node *head = malloc(sizeof(Node));
Node *temp;
Node *tail = head;
int i;
void reduceTree(Node *);
head->ch = str[0];
head->next = NULL;
for (i=1; str[i]!=''; i++) {
temp = malloc(sizeof(Node));
temp->ch = str[i];
temp->next = NULL;
tail->next = temp;
tail = temp;
}
reduceTree(head);
return head->ch == 'T';
}
void reduceTree(Node *head) { //this function recursicvely reduces the tree
Node *temp = head->next;
char and, or;
or = 'F';
and = 'T';
int flag = 0;
while (temp!=NULL) {
if (temp->ch == '(') {
reduceTree(temp);
flag = 1; //indicates that it is not leaf operator
continue;
}
if (temp->ch == ')') {
if (flag)
head->ch = or; //if not leaf use or result
else
head->ch = and;
head -> next = temp->next; // replace the sub tree with its result
return;
}
if (temp->ch == 'T')
or = 'T';
if (temp->ch == 'F')
and = 'F';
temp = temp->next;
}
if (flag)
head->ch = or;
else
head->ch = and;
head -> next = temp->next;
return;
}
void main() {
char *str = malloc(sizeof(char)*32000);
int c = 0;
FILE *fp = fopen("tree.in", "r");
if (fp == NULL) {
printf("cannot open file" );
return;
}
while(1) {
fscanf(fp,"%s",str);
If(strcmp(str, "()")==0)
break;
printf("%d. ",++c);
if (parse(str))
printf("true ");
else
printf("false ");
}
}
I codded this for you. The programing logic is tough, but once you start understanding the working, it will become easy