CISC220 F2023 Lab4

Requirements

A vector-based implementation of a binary tree of strings is provided in string_binary_tree.cpp (zipped along with a few simple test inputs). Your task is to complete the 4 functions below that depend on recursive traversals of a tree read from a file. The main() function expects a single input filename on the command line (reading it and creating the tree are taken care of for you) and an output type: PREPRINT, INPRINT, POSTEVAL, or POSTCOUNTCHARS. Each output type triggers a call to one of the functions you must write, as follows:

[1 point] PREPRINT: void preOrderPrint(node)

Using a pre-order traversal, print every non-NULL element in the subtree with the node specified as its root. Each string printed, including the last, should be followed by a space. A newline is printed automatically at the end of the no-argument version of this function that starts off the whole recursion.

[1 point] INPRINT: void inOrderPrint(node)

Using an in-order traversal, print every non-NULL element in the subtree with the node specified as its root.

[2 points] POSTEVAL: int postOrderEvaluate(node)

Treat the tree as an "expression tree" for integer arithmetic. Using a post-order traversal, evaluate the expression represented by the subtree with node as its root and return the integer value.

There are 6 operators (4 binary and 2 unary). All should be evaluated with integer arguments. The binary operators are +, -, *, and / for addition, subtraction, multiplication, and division, respectively. The 2 unary operators are strings: fact and abs, for the factorial operation and taking the absolute value, respectively. For unary operators, the operand should be the left child and the right child should be empty/NULL.

If there is an error or exception of any kind, print "ERROR\n" and exit with code 1.

Otherwise, the result is printed automatically when the no-argument version of this function finally returns.

[1 point] POSTCOUNTCHARS: int postOrderCountChars(node)

Using a post-order traversal, return the total number of characters in the non-NULL strings in the subtree with the node specified as its root.

As above, the result is printed automatically when the no-argument version of this function returns.

Submission

• Once again, you will submit two files completely through Gradescope: (1) README and (2) your modified string_binary_tree.cpp. As before, the README should contain your name, any AI tool citations/explanations, notes on any limitations or issues with your code, and your interpretation of any ambiguities in the assignment instructions. The code file should also have your name and AI citations per the syllabus.
• Resubmit as many times as you like until the deadline, but be aware that the submission window is kept open for some students to use late days, so a resubmission 2 days after the deadline is not free.
• The 5 possible points assigned by the autograder are provisional. They are not final until published and they may be revised if we determine that your code and/or README do not satisfy the assignment requirements even though they pass the tests. In rare cases, we may also revise your grade upward if we believe that the score you received does not reflect the work you put into the assignment.