· 7 years ago · Nov 26, 2018, 10:10 PM
1// Boolean Algebra Parser
2// By George Caley
3//
4// Based on the following grammar:
5// <not> ::= "!"
6// <var> ::= [A-Z]
7// <var> ::= "(" <or> ")"
8// <var> ::= <not> <var>
9// <and> ::= <var> (<and>)?
10// <or> ::= <and> ("+" <or>)?
11// <expr> ::= <or>
12//
13// After parsing, it spits out a nested representation of the parse tree
14// and a truth table for the expression.
15
16#include <stdio.h>
17#include <stdlib.h>
18#include <stdbool.h>
19#include <string.h>
20
21// Parser characters
22#define NOT_OPERATOR '!'
23#define OR_OPERATOR '+'
24#define PARENTHESIS_OPEN '('
25#define PARENTHESIS_CLOSE ')'
26
27// Indent chars, used for printing trees
28#define INDENT " "
29
30// NodeType, used to specify the type of node (duh)
31typedef enum {
32 AND_NODE,
33 OR_NODE,
34 NOT_NODE,
35 VAR_NODE
36} NodeType;
37
38// The node structure, represents a node in the (binary) parse tree
39typedef struct _Node {
40 struct _Node* left;
41 struct _Node* right;
42 NodeType type;
43 char name;
44} Node;
45
46// Parser variables
47int pointer; // Stores a pointer to the current token
48int length; // Stores the length of the input string
49char string[256]; // Stores the tokens (i.e. input string)
50
51// Node functions
52Node* newNode();
53void destroyNode(Node* node);
54bool validVariable(char token);
55bool evaluate(Node* node, bool map[]);
56void printIndent(int indent);
57void printTree(Node* root, int indent);
58int compareChars(const void* a, const void* b);
59void printTruthTable(Node* root);
60
61// Parser functions
62void reset();
63bool end();
64char peek();
65void next();
66Node* parse();
67Node* parseOr();
68Node* parseAnd();
69Node* parseVar();
70
71// Creates a new node
72Node* newNode() {
73 Node* node = (Node*)malloc(sizeof(Node));
74 // Initialise the node
75 node->left = NULL;
76 node->right = NULL;
77 return node;
78}
79
80void destroyNode(Node* node) {
81 // Traverse the node tree
82 Node* stack[1024]; // A stack to traverse the tree with
83 stack[0] = node; // Set the root node as the first element in the stack
84 int stack_ptr = 1; // A pointer to the next empty slot in the stack
85
86 Node* current; // Keep track of the current node
87 // Perform a DFS on the tree
88 while (stack_ptr > 0) {
89 // Pop the top node
90 stack_ptr--;
91 current = stack[stack_ptr];
92
93 // Push the node's children onto the stack, if either exists
94 if (current->left != NULL) {
95 stack[stack_ptr] = current->left;
96 stack_ptr++;
97 }
98 if (current->right != NULL) {
99 stack[stack_ptr] = current->right;
100 stack_ptr++;
101 }
102
103 // Dealloc the node
104 free(current);
105 }
106}
107
108// Checks whether a given token is a valid variable
109bool validVariable(char token) {
110 return (token >= 'A' && token <= 'Z');
111}
112
113// Evaluates the boolean expression contained within a parse tree
114// map is an array of 26 bools, each representing the value behind
115// a given letter in the evaluation
116bool evaluate(Node* node, bool map[]) {
117 switch (node->type) {
118 case AND_NODE:
119 return evaluate(node->left, map) & evaluate(node->right, map);
120 case OR_NODE:
121 return evaluate(node->left, map) | evaluate(node->right, map);
122 case NOT_NODE:
123 return !evaluate(node->left, map);
124 case VAR_NODE:
125 // subtract the char value of 'A' to get the letter within
126 // the range 0..25, and access the appropriate element of the
127 // value map
128 return map[node->name - 'A'];
129 }
130}
131
132// Prints the specified number of indents
133void printIndent(int indent) {
134 for (int i = 0; i < indent; i++) {
135 printf(INDENT);
136 }
137}
138
139// Pretty prints a parse tree
140// indent specifies the indent level
141void printTree(Node* root, int indent) {
142 printIndent(indent);
143
144 // Print the label for this node
145 switch (root->type) {
146 case AND_NODE:
147 printf("AND");
148 break;
149 case OR_NODE:
150 printf("OR");
151 break;
152 case NOT_NODE:
153 printf("NOT");
154 break;
155 case VAR_NODE:
156 // In the case of a var node, print the node name
157 printf("%c", root->name);
158 break;
159 }
160
161 // Store whether or not this node has left and right child nodes
162 bool hasLeft = (root->left != NULL);
163 bool hasRight = (root->right != NULL);
164
165 // If it has any children, print an opening brace
166 if (hasLeft || hasRight) {
167 printf(" {");
168 }
169 printf("\n");
170
171 // Call print tree again for the left and right nodes, while
172 // incrementing the indent level
173 if (hasLeft) {
174 printTree(root->left, indent+1);
175 }
176 if (hasRight) {
177 printTree(root->right, indent+1);
178 }
179
180 // If it has any children, print a closing brace
181 if (hasLeft || hasRight) {
182 printIndent(indent);
183 printf("}\n");
184 }
185}
186
187// Compares the two characters a and b
188// Used solely for sorting
189int compareChars(const void* a, const void* b) {
190 if (*(char*)a < *(char*)b) {
191 return -1;
192 } else if (*(char*)a > *(char*)b) {
193 return 1;
194 } else {
195 return 0;
196 }
197}
198
199// Prints out a truth table for the given node
200void printTruthTable(Node* root) {
201 char letters[26]; // Stores the letters found within the parse tree
202 int letter_ptr = 0; // A pointer to the next empty slot in the letters array
203
204 Node* stack[1024]; // A stack to traverse the tree with
205 stack[0] = root; // Set the root node as the first element in the stack
206 int stack_ptr = 1; // A pointer to the next empty slot in the stack
207
208 Node* current; // Keep track of the current node
209 // Perform a DFS on the tree
210 while (stack_ptr > 0) {
211 // Pop the top node
212 stack_ptr--;
213 current = stack[stack_ptr];
214
215 if (current->type == VAR_NODE) {
216 // Check whether the letter is already in the array
217 // Yeah, it's a linear search... but there's only 26 items,
218 // so who's counting.
219 bool in_array = false;
220 for (int i = 0; i < letter_ptr; i++) {
221 if (letters[i] == current->name) {
222 in_array = true;
223 break;
224 }
225 }
226
227 // Was it found?
228 if (!in_array) {
229 // Add it to the letters array and increment the pointer
230 letters[letter_ptr] = current->name;
231 letter_ptr++;
232 }
233 } else {
234 // Push the node's children onto the stack, if either exists
235 if (current->left != NULL) {
236 stack[stack_ptr] = current->left;
237 stack_ptr++;
238 }
239 if (current->right != NULL) {
240 stack[stack_ptr] = current->right;
241 stack_ptr++;
242 }
243 }
244 }
245
246 // Sort the variables into alphabetical order
247 qsort(letters, letter_ptr, sizeof(char), compareChars);
248
249 // Print the variables as the header for the truth table
250 for (int i = 0; i < letter_ptr; i++) {
251 printf("%c ", letters[i]);
252 }
253 printf("\n");
254
255 // Now print out the values of the table
256 int limit = 1 << letter_ptr; // 2^(number of variables), used to generate permutations
257 bool map[26]; // Keeps track of the values of the current permutation, later passed to evaluate()
258 // The indexes of map are the letters of the alphabet from A through Z
259
260 for (int i = 0; i < limit; i++) {
261 // Create and print a permutation based on the bits of i
262 for (int j = 0; j < letter_ptr; j++) {
263 bool value = (i & (1 << j)) > 0; // Stores whether the 2^jth bit of i is set
264 int letter = letters[j] - 'A'; // Stores the char in the range 0..25
265 map[letter] = value; // Assign the value to the appropriate slot of the map
266 printf("%d ", value); // Print the value
267 }
268 // Now evaluate the parse tree for the current permutation, as stored in map, and print
269 printf("%d\n", evaluate(root, map));
270 }
271}
272
273// Resets the parser's state
274void reset() {
275 pointer = -1; // Initialise the pointer
276 length = strlen(string); // Set the input string length
277 next(); // Bring the pointer forward to the first token, past any whitespace
278}
279
280// Returns whether the pointer is at the end of the string
281bool end() {
282 return (pointer >= length);
283}
284
285// Returns the token that the pointer is pointing at
286char peek() {
287 if (end()) {
288 return 0; // The pointer is pointing beyond the string, return null
289 } else {
290 return string[pointer];
291 }
292}
293
294// Moves the pointer to the next token, past any whitespace
295void next() {
296 do {
297 pointer++;
298 } while (string[pointer] == ' ');
299}
300
301// Parses the expression in its entirety
302Node* parse() {
303 Node* ret = parseOr(); // Parse an or node
304 if (ret == NULL) {
305 return NULL;
306 }
307 if (!end()) {
308 // We should have read in all the tokens by the end of the string!
309 printf("Unexpected token: %c\n", peek());
310 return NULL;
311 }
312 return ret;
313}
314
315// Parses an or node
316Node* parseOr() {
317 Node* left = parseAnd(); // Parse an and node
318 if (left == NULL) {
319 return NULL;
320 }
321 // Does an or operator follow?
322 if (peek() == OR_OPERATOR) {
323 next(); // Advance the pointer
324 Node* right = parseOr(); // Parse another or node
325 if (right == NULL) {
326 return NULL;
327 }
328 Node* or = newNode();
329 or->type = OR_NODE;
330 or->left = left;
331 or->right = right;
332 return or;
333 } else {
334 // Return the single left node if there was no or operator
335 return left;
336 }
337}
338
339// Parses an and node
340Node* parseAnd() {
341 Node* left = parseVar(); // Parse a var node
342 if (left == NULL) {
343 return NULL;
344 }
345 char next_char = peek(); // Stores the next token
346 // Verify we are not at the end of the expression, and that the next token is either
347 // a not operator, open parenthesis, or a valid variable (from the grammar)
348 if (!end() && (next_char == NOT_OPERATOR || next_char == PARENTHESIS_OPEN || validVariable(next_char))) {
349 Node* right = parseAnd(); // Parse another and node
350 if (right == NULL) {
351 return NULL;
352 }
353 Node* and = newNode();
354 and->type = AND_NODE;
355 and->left = left;
356 and->right = right;
357 return and;
358 } else {
359 return left;
360 }
361}
362
363// Parses a var node
364Node* parseVar() {
365 char next_char = peek(); // Stores the next token
366 if (end()) {
367 // If parseVar was called, we were expecting a variable...
368 printf("Expected variable\n");
369 return NULL;
370 } else if (next_char == NOT_OPERATOR) {
371 // Construct a not node around the succeeding var node
372 next();
373 Node* not = newNode();
374 not->type = NOT_NODE;
375 Node* var = parseVar();
376 if (var == NULL) {
377 return NULL;
378 }
379 not->left = var;
380 return not;
381 } else if (next_char == PARENTHESIS_OPEN) {
382 // Parse the or expression contained within the parentheses
383 next();
384 Node* or = parseOr();
385 // Verify the expression was closed properly
386 if (peek() != PARENTHESIS_CLOSE) {
387 printf("Mismatched parentheses\n");
388 return NULL;
389 }
390 next();
391 return or;
392 } else if (validVariable(next_char)) {
393 Node* var = newNode();
394 var->type = VAR_NODE;
395 var->name = next_char;
396 next();
397 return var;
398 } else {
399 printf("Invalid variable: %c\n", next_char);
400 return NULL;
401 }
402}
403
404int main(int argc, char* argv[]) {
405 // Continue until we receive an empty string from the user
406 while (true) {
407 printf("Expression: "); // Display a prompt
408 fgets(string, sizeof(string), stdin); // Read tokens from stdin
409 string[strlen(string)-1] = 0; // Strip the newline
410
411 if (strlen(string) == 0) {
412 break;
413 }
414
415 reset(); // Reset the parser
416 Node* result = parse(); // Parse
417 if (result != NULL) {
418 printf("\n");
419 printTree(result, 0); // Pretty print the tree
420 printf("\n");
421 printTruthTable(result); // Print the truth table
422 printf("\n");
423
424 destroyNode(result);
425 }
426 }
427
428 return 0;
429}