README Assignment 3 Name: Aly Sibak Student ID: 1276226 Date: Nov 18, 2024
Overview This assignment implements solutions to the following problems:
Question 1: Arithmetic Expression Parser A program (a3q1) that parses a mathematical expression provided as a command-line argument, constructs a binary tree for the expression, and supports:
Preorder, inorder, and postorder traversals of the expression tree. Evaluation of the expression after assigning values to variables. Question 2: Max-Heap Implementation A program (a3q2) that manipulates a max-heap data structure by:
Providing functionality for downHeap operation. Swapping rows in a 2D array. Checking if a position is a parent in the heap. Usage Instructions Compilation Use the provided makefile to compile the programs. Run the following command in the terminal:
make This will generate two executables:
- a3q1 for Question 1.
- a3q2 for Question 2.
Question 1: Arithmetic Expression Parser The program takes a fully parenthesized arithmetic expression as a command-line argument. The expression can include:
- Variables (e.g., x1, x2).
- Floating-point numbers.
- Binary operators: +, -, *, /.
Example: ./a3q1 '(((x1+5.12)*(x2-7.68))/x3)'
Upon running, the program will display a menu: Preorder Traversal: Displays the preorder traversal of the expression tree. Inorder Traversal: Displays the inorder traversal with fully parenthesized expressions. Postorder Traversal: Displays the postorder traversal of the expression tree. Calculate: Prompts the user for variable values and evaluates the expression. Exit: Exits the program.
Sample Input: ./a3q1 '(((x1+5.12)*(x2-7.68))/x3)'
Sample Output: Menu:
- Preorder
- Inorder
- Postorder
- Calculate
- Exit Enter choice: 1 / * + x1 5.12 - x2 7.68 x3
Question 2: Max-Heap Implementation The program manipulates a max-heap structure, ensuring heap properties using a downHeap function.
How to Run: ./a3q2
Question 1 Test the program with the following input expressions: ./a3q1 '(((x1+5.12)*(x2-7.68))/x3)'
Menu:
- Preorder
- Inorder
- Postorder
- Calculate
- Exit
/ * + x1 5.12 - x2 7.68 x3 = preorder
((((x1)+(5.12))*((x2)-(7.68)))/(x3)) = inorder
x1 5.12 + x2 7.68 - * x3 / = postorder
Enter value for x1: 1 Enter value for x2: 2 Enter value for x3: 3 Result: -11.59 = Calculate
Question 2 Verify the downHeap functionality by providing: A test max-heap as a 1D key array and a corresponding 2D array of data. Ensure rows are swapped correctly during heapifying.
The following files are included in this submission: a3q1_main.c = Main program for Question 1. a3q1_functions.c = Functions for parsing and evaluating expressions. a3q1_header.h = Header file for Question 1. a3q2_main.c = Main program for Question 2. a3q2_functions.c = Functions for max-heap operations. a3q2_header.h = Header file for Question 2. makefile = Compiles the programs. README = This file. Compilation Details Compiler: GCC Flags: -Wall -std=c99 -pedantic Tested on: School server environment
Error Handling Question 1: Detects invalid input expressions and division by zero during evaluation.
Question 2: Ensures heap properties and detects invalid indices.
Submission Requirements: The folder structure follows the requirements: Folder Name: 1276226_a3 Files included: Source files (.c and .h) makefile README
No additional files, such as .o files or test data, are included.