2 Programming Part [70pts+10pts(Bonus)] Given an arithmetic expression in infix or postfix notation, the goal of this assignment is to : 1. Write a program that converts the expression to another notation using expression trees. 2. Evaluate the expression. The main idea consists of the following steps : 1. Convert the given (input) expression into a postfix notation (if it is not the case). 2. Construct the expression tree from the postfix representation. 3. Evaluate the expression tree or print it into another notation. The expression contains only the arithmetic operators +, *, - and /, integers and (, ) if the expression is in infix form. * and / have more priority than + and -. You should leave at least 1 space between operators, operands and symbols (the minus sign(-) for negative numbers should however be attached to the number, -23 for instance).

2.1 Infix to Postfix Conversion Implement the algorithm that converts an expression from infix to postfix (a description of this algorithm is provided in subsection 3.3.3 of the textbook). Below are some examples for conversion from infix to postfix. -12 + 13 --> -12 13 + 13 + 24 * 35 / 46 --> 13 24 35 * 46 / + ( 4 + 8 ) * ( 6 - 5 ) / ( 3 - 2 ) * ( 2 + 2 ) --> 4 8 + 6 5 - * 3 2 - / 2 2 + * ( ( ( ( 1 * ( 2 + 3 ) ) - 3 ) + 4 ) * 5 ) --> 1 2 3 + * 3 - 4 + 5 * 2.2 Constructing an expression tree from a postfix notation Implement the algorithm that converts a postfix expression into an expression tree (a description of this algorithm is provided in subsection 4.2.2 of the textbook) . You may reuse the array implementation of the ADT Stack provided by the author (TestStackAr.cpp, StackAr.cpp and StackAr.h are available in the textbook homepage). 2.3 Printing an arithmetic expression from the expression tree Using the following tree traversal algorithms, write a program that prints an arithmetic expression in a given notation (prefix, infix or postfix) from an expression tree. 2.3.1 Inorder traversal An overly parenthesized infix expression can be produced by recursively producing parenthesized left expression, then printing out the operator at the root, and finally recursively producing parenthesized right expression. This general strategy (left,node,right) is known as an inorder traversal. 2.3.2 Postorder traversal The algorithm consists in recursively print out the left subtree, the right subtree, and then the operator. 2.3.3 Preorder traversal This method consists in printing out the operator first and then recursively print out the left and the right subtrees. 2.4 Evaluating an arithmetic expression from the expression tree Write a program that evaluates an arithmetic expression represented by an expression tree. 2.5 Marking scheme of the programming part: total = 70pts + 10pts (Bonus) 1. Readability (program style) : 10pts Program easy to read, well commented, good structured (layout, indentation, whitespace, . . .) and designed(following the top-down approach). 2. Compiling and execution process : 10pts

program compiles w/o errors and warnings robustness : execution w/o run time errors 3. Correctness : 50pts code produces correct results (output) : (a) infix postfix notation 8pts (b) infix prefix notation 8pts (c) postfix infix notation 8pts (d) postfix prefix notation 8pts (e) evaluate the expression tree 6pts (f) Handling numbers with more than 1 digit 6pts (g) Detecting the type of expression in input(prefix, infix or postfix) 6pts 4. Bonus : 10pts Handling expressions in prefix form in input 5pts Detecting the type of errors (missing operator or operand, unknown symbol . . . etc) 3pts Other features that increase functionality and/or presentation 2pts

3.2 Programming Part 3.2.1 Single file submission Using URCourses, submit the file containing the C++ code of the programming part assign1username.cpp. At the top of this file add the following comments : 1. Your first name, last name and ID #, 2. the compiling command you have used, 3. an example on how to execute the program, 4. and other comments describing the program 3.2.2 Multiple files submission Using UR Courses, submit all files required by the programming part : 1. README (file including your name and ID #; and explaining the compilation and execution of your program including the format of input and other details) 2. headers (.h) 3. implementations (.cpp) 4. the Makefile : should be named makefile. In the makefile, the generated executable should be named : assign1username You can give any name to your source files. The marker will only have to run make to compile your program and assign1username to execute it. All your source files should be submitted in one single zip file named: assign1username.zip

NEED A CORRECT SOLUTION WITH ALL THE ALGORITHM AND FULL CODE WITH THE OUTPUT GIVING ALL THE ANSWERS ABOVE AND EVEN THE BONUS .LOTS OF ANSWERS TO THIS ARE IN CORRECT SO AND ALL THE FILES CORRECTLY MADE AND A SCREENSHOT OF AN OUTPUT