Purpose: To work with a real application for stacks Degree of Difficulty: Moderate. You have to learn a new algorithm, then implement it. In class, we saw how to evaluate numerical expressions expressed in post-fix (also known as reverse Polish notation). The code for that is available on the course Moodle. It turns out to be fairly easy to write a similar program to evaluate expressions using normal mathematical notation. Input The input will be a mathematical expression in the form of a string, using at least the four arithmetic opera- tors (+,-, X, / as well as pairs of brackets. To avoid problems that are not of interest to our work right now. we'll also use lots of space where we normally wouldn't. We'll use spaces between operators, numbers and brackets. This space is required so that split() can be used to split the different tokens. Here's a list of expressions for example: example1 = '( 1 + 1); # should evaluate to 2 example2 = ( ( 11 + 12 ) * 13 )' # should evaluate to 299 Notice particularly that we are using brackets explicitly for every operator. In every-day math, brackets are sometimes left out, but in this is not an option here. Every operation must be bracketed! The brackets and the spacing eliminate programming problems that are not of interest to us right now. Hint: You will find it useful to split the string into sub-strings using split() and even to put all the substrings into a Queue, as we did for the PostFix program. Algorithm We will use two stacks: one for numeric values, as in the PostFix program, and a second stack just for the operators. We take each symbol from the input one at a time, and then decide what to do with it: . If the symbol is '('.ignore it. If the symbol is a string that represents a numeric value (use the function isfloat(). provided in the script isfloat.py), convert to a floating point value and push it on the numeric value stack. If the symbol is an operator. push the operator on the operator stack. If the symbol is '' pop the operator stack, and two values from the numeric value stack, do the appropriate computation, and push the result back on the numeric value stack. You should write a function to do all this processing, OPPIDPIDO PELLILIOI PADI OTODAILL DUO LITION VOLO DELOIL. You should write a function to do all this processing. Since the objective here is to practice using stacks, you must use the Stack ADT provided for this assign- ment. Also, you may assume that the input will be syntactically correct, for full marks. For this question your program does not need to be robust against syntactically incorrect expressions. Using the Stack and Queue ADTS Download the ADT implementations named TStack.py TQueue.py from the Assignment 4 page on Moodle. To help you avoid errors, these implementations do not allow you to violate the ADT in a careless way. You do not need to understand the code in the files. You do not even need to look at it. We will study simpler and more accessible implementations later in the course. You should focus on using the ADT operations correctly. These versions have the same ADT operations, and have been thoroughly tested. If your script does not use these ADTs correctly, or if you violate the ADT Principle, a runtime error will be caused. If a runtime error points you to the code in the ADT, the error is almost certainly in your script, not the ADT code. Testing This is the first script whose testing needs to be very diligent, and will end up being extensive. Write a test. script that checks each arithmetic operation in very simple cases (one operator each), and then a number of more complicated cases using more complicated expressions. Your test script should do unit testing of your function to evaluate expressions. You can add tests of any other functions you write, but focus on testing the expressions. What to Hand In . Your function, written in Python, in a file named a4q3.py . Your test-script for the function, in a file called a4q3_test.py Be sure to include your name, NSID. student number, course number and laboratory section at the top of all documents Evaluation 6 marks: Your evaluation function correctly evaluates expressions of the form given above. It uses two Stacks, both are created by the TStack ADT. - 1 mark: The evaluation function correctly handles numeric data by pushing onto a numbers stack - 1 mark. The evaluation function correctly handles operators by pushing on an operator stack - 3 marks. The evaluation function correctly evaluates expressions when a '' is encountered. Two values are popped from the numbers stack, and an operator is popped from the operator stack The correct operation is performed, and the result is pushed back on the numbers stack. - 1 mark. When there is nothing left to evaluate the result is popped from the numbers stack. . 4 marks: Your test script covers all the operations individually once, and in combination - 2 marks: Every operator is tested. - 2 marks: Testing includes at least one expression with several nested operations. Purpose: To work with a real application for stacks Degree of Difficulty: Moderate. You have to learn a new algorithm, then implement it. In class, we saw how to evaluate numerical expressions expressed in post-fix (also known as reverse Polish notation). The code for that is available on the course Moodle. It turns out to be fairly easy to write a similar program to evaluate expressions using normal mathematical notation. Input The input will be a mathematical expression in the form of a string, using at least the four arithmetic opera- tors (+,-, X, / as well as pairs of brackets. To avoid problems that are not of interest to our work right now. we'll also use lots of space where we normally wouldn't. We'll use spaces between operators, numbers and brackets. This space is required so that split() can be used to split the different tokens. Here's a list of expressions for example: example1 = '( 1 + 1); # should evaluate to 2 example2 = ( ( 11 + 12 ) * 13 )' # should evaluate to 299 Notice particularly that we are using brackets explicitly for every operator. In every-day math, brackets are sometimes left out, but in this is not an option here. Every operation must be bracketed! The brackets and the spacing eliminate programming problems that are not of interest to us right now. Hint: You will find it useful to split the string into sub-strings using split() and even to put all the substrings into a Queue, as we did for the PostFix program. Algorithm We will use two stacks: one for numeric values, as in the PostFix program, and a second stack just for the operators. We take each symbol from the input one at a time, and then decide what to do with it: . If the symbol is '('.ignore it. If the symbol is a string that represents a numeric value (use the function isfloat(). provided in the script isfloat.py), convert to a floating point value and push it on the numeric value stack. If the symbol is an operator. push the operator on the operator stack. If the symbol is '' pop the operator stack, and two values from the numeric value stack, do the appropriate computation, and push the result back on the numeric value stack. You should write a function to do all this processing, OPPIDPIDO PELLILIOI PADI OTODAILL DUO LITION VOLO DELOIL. You should write a function to do all this processing. Since the objective here is to practice using stacks, you must use the Stack ADT provided for this assign- ment. Also, you may assume that the input will be syntactically correct, for full marks. For this question your program does not need to be robust against syntactically incorrect expressions. Using the Stack and Queue ADTS Download the ADT implementations named TStack.py TQueue.py from the Assignment 4 page on Moodle. To help you avoid errors, these implementations do not allow you to violate the ADT in a careless way. You do not need to understand the code in the files. You do not even need to look at it. We will study simpler and more accessible implementations later in the course. You should focus on using the ADT operations correctly. These versions have the same ADT operations, and have been thoroughly tested. If your script does not use these ADTs correctly, or if you violate the ADT Principle, a runtime error will be caused. If a runtime error points you to the code in the ADT, the error is almost certainly in your script, not the ADT code. Testing This is the first script whose testing needs to be very diligent, and will end up being extensive. Write a test. script that checks each arithmetic operation in very simple cases (one operator each), and then a number of more complicated cases using more complicated expressions. Your test script should do unit testing of your function to evaluate expressions. You can add tests of any other functions you write, but focus on testing the expressions. What to Hand In . Your function, written in Python, in a file named a4q3.py . Your test-script for the function, in a file called a4q3_test.py Be sure to include your name, NSID. student number, course number and laboratory section at the top of all documents Evaluation 6 marks: Your evaluation function correctly evaluates expressions of the form given above. It uses two Stacks, both are created by the TStack ADT. - 1 mark: The evaluation function correctly handles numeric data by pushing onto a numbers stack - 1 mark. The evaluation function correctly handles operators by pushing on an operator stack - 3 marks. The evaluation function correctly evaluates expressions when a '' is encountered. Two values are popped from the numbers stack, and an operator is popped from the operator stack The correct operation is performed, and the result is pushed back on the numbers stack. - 1 mark. When there is nothing left to evaluate the result is popped from the numbers stack. . 4 marks: Your test script covers all the operations individually once, and in combination - 2 marks: Every operator is tested. - 2 marks: Testing includes at least one expression with several nested operations