Description

Given an infix Boolean expression with parentheses, which has at most 4 variables ‘A’, ’B’, ‘C’, and ‘D’, and two operators ‘&’ and ‘|’. Build a corresponding syntax tree for it and print it's truth table.

For example, if input is "(A&C)|(A|B)", then result will be

A B C D output

0 0 0 0 0
0 0 0 1 0
0 0 1 0 0
0 0 1 1 0
0 1 0 0 1
0 1 0 1 1
0 1 1 0 1
0 1 1 1 1
1 0 0 0 1
1 0 0 1 1
1 0 1 0 1
1 0 1 1 1
1 1 0 0 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 1

 

To parse the infix expression with parentheses, use the grammar below.

EXPR = FACTOR | EXPR OP FACTOR

FACTOR = ID | (EXPR)

EXPR is the expression, ID is one of ‘A’, ‘B’, ’C’, or ‘D’, and OP is one of ‘&’ or ‘|’.

 

You will be provided with main.c and function.h. main.c contains the implementation of functions printPrefix and freeTree. function.h contains the definition of tree node and variables. You only need to implement the following four functions in function.c.

BTNode* makeNode(char c)   // create a node without any child

BTNode* EXPR()   // parse an infix expression and generate a syntax tree

BTNode* FACTOR()   // use the parse grammar FACTOR = ID | (EXPR) to deal with parentheses

void printResult(BTNode *root)    // print the truth table

 

For OJ submission:

        Step 1. Submit only your function.c into the submission block.(Please choose C compiler)

        Step 2. Check the results and debug your program if necessary.

main.c

#include <stdio.h> #include <string.h> #include <stdlib.h> #include "function.h" int main() { sym[0]='A'; sym[1]='B'; sym[2]='C'; sym[3]='D'; sym[4]='&'; sym[5]='|'; while (scanf("%s", expr)!=EOF) { pos = strlen(expr) - 1; BTNode *root = EXPR(); printResult(root); printf("\n"); freeTree(root); } return 0; } /* clean a tree.*/ void freeTree(BTNode *root) { if (root!=NULL) { freeTree(root->left); freeTree(root->right); free(root); } }

function.h

#include <stdio.h> #include <stdlib.h> #define MAXEXPR 256 #define NUMSYM 6 char expr[MAXEXPR]; // string to store the input expression. int pos; // current position of parsing, from end to start typedef enum {ID_A, ID_B, ID_C, ID_D, OP_AND, OP_OR} TokenSet; char sym[NUMSYM]; typedef struct _Node { TokenSet data; struct _Node *left, *right; } BTNode; BTNode* EXPR(); BTNode* FACTOR(); BTNode* makeNode(char c); void freeTree(BTNode *root); void printResult(BTNode *root);

Input

The input contains a sequences of prefix expression. It only has at most 4 variables ‘A’, ‘B’, ‘C’, and ‘D’, and 2 operators, AND ‘&’ and OR ‘|’. The length of prefix expression is shorter than 30.

Output

It has 5 variables 'A', 'B', 'C', 'D', and output, each variable is separated by a space.

Sample Input  Download

Sample Output  Download

Partial Judge Code

10982.c

Partial Judge Header

10982.h

Tags

Add Tag

Discuss