Description

Instructor: Prof. Ilwoo Lyu
Teaching Assistants: Seunghwan Lee, Jiwon Son, Juncheol Shin, Wonjun Lee

**** PLEASE READ THIS GRAY BOX CAREFULLY BEFORE STARTING THE ASSIGNMENT ****

EvaluaAon Policy:
● Late Submission Penalty
Late submission penalty (30%)
■ will be applied to the total score.
100% penalty
■ will be applied for the submission and marked as zero.
● We do not accept any submission via email; they will be ignored.
keyboard-typed submissions for the wriPen assignment
● We do not accept any .
● You can do your wriUen assignment in two ways:
○ Use tablet (i.e. Galaxy Tab, iPad, etc) and stylus pen, and save your work as .pdf.
○ Write on any paper, scan it, and save as .pdf file
■ We recommend using MicrosoR Lens to scan your works.
your process of solving the problems
○ Please describe as detailed as possible.
○ If you write down your answer only, you will not earn a point.
● Please write neatly when showing your work.
○ Hardly unrecognizable work might be marked as zero points.
● Your code will be automa]cally tested using an evalua]on program.
○ Each problem has the maximum score.
○ A score will be assigned based on the behavior of the program
○ Full points will be given only if all test cases are passed; there are no parAal points if only some por]on of the test cases work, and the others don’t.
○ Points will be deducted for any typos or incorrect formaVng
● Compile your code using “Replit” and check your program before submission.
You should not use C++ standard template library
● other than given ones.
○ DO NOT INCLUDE <queue>, <vector>, <stack>, or other container libraries ○ Any submission using such STL library will be disregarded.
○ Using only the given libraries will suffice.
○ <iostream>, <fstream>, <string>, <cstdlib>, “ds.h”

Files You Need to Submit:
[your_student_id]_assignment2.zip
● .zip file named (i.e. 20241234_assignment2.zip) containing:
○ task_1.cpp
○ task_2.cpp
○ task_3.cpp
○ ds.h
○ wa2.pdf (your wriUen assignment)

as soon as possible
If You Find Bugs in the Program:
● Please noAfy us

Any other quesAons? Please use PLMS Q&A board in English.

Wri.en Assignment #2

Q1. (Total 2pt, 1pt each)
Descrip)on
Given the postorder and inorder sequences of a binary tree, reconstruct the tree and visually represent each step at the node level. At every step, show how the tree evolves as you insert nodes. If tree reconstruc]on is impossible for specific step, please stop drawing and write the reason.

1) postorder: <8, 16, 12, 20, 18, 25, 32, 30, 28, 22> inorder: <8, 12, 16, 18, 20, 22, 25, 28, 30, 32>

2) postorder: <20, 10, 5, 15, 55, 50, 25, 30, 35> inoder: <20, 10, 15, 5, 55, 25, 50, 30, 35>

Q2. (2pt)
Descrip)on
Given a tree represented by Tree[] and Label[] array, perform the following tasks:
1. Draw the corresponding tree structure.
2. Convert the tree into its LeS Child-Right Sibling (LC-RS) form and draw it.
You can choose the order of the children freely, but ensure that the LC-RS representa]on accurately reflects the order of original tree structure you drew.
You can refer lecture note 7_tree_2.

Programming Assignment #2

Basic Instruc@on
Please refer to C++ Environment Setup Guide, which is on PLMS.
Use the command below to compile your code:
$ g++ -std=c++11 -o task_* task_*.cpp
For example, you can command $ g++ -std=c++11 -o task_1 task_1.cpp
[Task 0] Data Structure Implementa@on (0pts)
In this assignment, you are encouraged to define all necessary data structures in a file named “ds.h”. For example, implement essen]al structures such as Queue and Stack in this file. These structures are shared across all tasks. For each task, create separate files (e.g., “task_*.cpp”) that include “ds.h” to solve the given problem. Although it is not for grading, it is highly recommended to improve your programming skills, code readability, and reusability. To simplify the compila]on process, make sure to include #include “ds.h” in all your task files.

[Task 1] Construct Ternary Tree (4pts)
Descrip)on
Your task is to construct tree, especially ternary tree which has children up to three. The tree starts with root node (index 0), and you need to process a series of opera]ons to either add(ADD) or delete(DEL) nodes in the tree. Your task is to write a program that reads these opera]ons from an input file “input_1.txt”, processes them to construct the tree, and finally outputs the tree structure to an output file “output_1.txt”. Assume there is no duplicate index.
The opera]ons consist of two types:
ADD P C: Add node C as a child of node P (if P has at most two children).
DEL X: Delete node X and all of its descendants from the tree.
● Implement a “task_1.cpp” that constructs tree according to input.

Input
● N: the number of opera]on lines. (N is unsigned integer < 1,000)
● Opera]on 1~N: ADD P C or DEL X, (P, C, X are unsigned integer < 1,000)
○ e.g.) ADD 0 3: Add child 3 to the parent 0
○ e.g.) DEL 5: Delete subtree which has node 5 as root

Output
The program should output each parent node index followed by its corresponding children indices. The parent indices must be in ascending order, and for each parent, the children indices should also be in ascending order.
1. No node is available for dele]on,
2. The parent node for adding children does not exist
3. There is no space to add more nodes the program should output “Error” in “output_1.txt” and then terminate.

e.g.) input_1.txt output_1.txt

e.g.) input_1.txt output_1.txt

e.g.) input_1.txt output_1.txt

e.g.) input_1.txt output_1.txt

[Task 2] Lowest Common Ancestor (LCA) (6pts)
Descrip)on
Given a mul]-ary tree (assume that they are always connected), we are finding the Lowest Common Ancestor (LCA) of two given nodes. The LCA of two nodes ! and ” in a tree is defined as the deepest node that is an ancestor of both ! and “.
● Implement a “task_2.cpp” that can find LCA of tree given.

Input
● N: the number of input lines. (N is unsigned integer < 1,000)
● Line 1~N: the index of parent and its children. (unsigned integers, separated by space)
○ The leSmost value is the parent node index, and the remaining values are the indices of its children.
○ e.g.) 12 9 14 8: Parent index 12 has three children which have index 9, 14, and 8.
● ! and ” (unsigned integer < 1,000)
○ e.g.) 3 11: LCA of node 3 and 11 (note that ! and ” can be same) For example, if “input_2.txt” is given as:

The corresponding tree can be visualized as:

Output
● Implement a program that outputs the index of LCA for the tree from “input_2.txt”.
● For invalid input, such as when there is no node corresponding to either ! or “, the program should output “Error” in the “output_2.txt”.
e.g.) input_2.txt output_2.txt

e.g.) input_2.txt output_2.txt

e.g.) input_2.txt output_2.txt

[Task 3] Parsing and Evalua@ng Complex Nested Ternary Expressions Using Binary Trees (8pt)
(recommend to use string header file)
Descrip)on
You are tasked with parsing and evalua]ng a nested ternary expression that refers to values from the array. The ternary expression will be provided in a single-line format. Your goal is to construct this nested expression as a binary tree, where each node contains a condi]on, and the children represent the True and False cases based on the Boolean outcome of the condi]on. Once the ternary expression is constructed as a binary tree, evaluate it by looking up the values referred in the array. You can assume that parentheses () are always given for grouping the case statements in all input.
Ternary Expression Format: condi]on ? (true_case_statement) : (false_case_statement)
Opera]ons used in this task are: [ ‘>’, ‘<’, ‘==’ ]
e.g.) 5 > 0 ? (2 > -1 ? (1) : (3)) : (-3) Output: 1

Input
● N: the number of array values. (N is unsigned integer < 1,000)
● Line 1~N: array values from index 0 (signed integers) ● Nested Ternary Expression (string, length < 1,000)
Output
● Implement a program that outputs the outcome of nested ternary expression from “input_3.txt”.
● For invalid input such as syntax error, output “Error”.

For example, if “input_3.txt” is given as:

Given N=6, the array contains 6 elements: [1, 2, -1, 3, 5, 2].
• i0 refers to the 0-th element: 1,
• i3 refers to the 3-rd element: 3,
• i4 refers to the 4-th element: 5, and so on.
Then, parse Nested ternary expression line (recommend you to use string header file) i1 > 0 ? (i3 == -1 ? (i5) : (1 > 2 : (1) : (3))) : (i5 < 4 ? (i1) : (-1))
This expression can be represented as a binary tree, where each node represents a condi]on (leaf node for value) and branches lead to the True or False cases.

Now, let’s solve it manually.
The root node is a condi]on (i1 > 0). (Tip: right term can be referring value such as i2) Referring to the array, i1 is 2, so the condi]on becomes (2 > 0), which is True.
Since this is True, we follow the leS branch to evaluate (i3 == -1).
Referring to the array, i3 is 3, so the condi]on becomes (3 == -1), which is False.
Since this is False, we follow the right branch to evaluate (1 > 2).
(Tip: without “i” nota]on, it is assumed to be constant)
Since (1 > 2) is False, we follow the right branch, which leads to a leaf node with the value 3.
Result: The final output of the ternary expression is 3.
e.g.) input_3.txt output_3.txt