关键词 >
CMPSC 132: Programming and Computation II
发布时间：2020-10-23
Goal: The goal of this homework is to create a class that can evaluate mathematical expressions.
By implementing this class, you should gain a deeper understanding of expression trees, as well as improve your string processing and object-oriented programming skills.
General instructions:
• The work in this assignment must be your own original work and be completed alone.• The instructor and course assistants are available on Piazza and with office hours to answer any questions you may have. You may also share testing code on Piazza.
• Students are allowed to show their code to other students only during Office Hour Party!
• A doctest is provided to ensure basic functionality and may not be representative of the full range of test cases we will be checking. Further testing is your responsibility.
• Debugging code is also your responsibility.
• Remove all testing code, code that produces syntax errors and any input() calls before you submit your file
Assignment-specific instructions:
• Download the starter code file from Canvas. Do not change the function names or givenstarter code in your script.
• Watch the Stack and Stack applications video lectures before you start this assignment.
Those lectures describe the main algorithms required to complete this assignment.
• Do not use the exec or eval functions, nor are you allowed to use regular expressions for
this homework assignment. No credit will be given if they are used in your code.
• This assignment includes multiple methods interacting with each other over the course of
execution. You will need to use the tools described in module 2 for debugging.
Submission format:
• Submit your code in a file named HW3.py to Gradescope before the due date.Point distribution:
• Section 1: The Stack class (20 points)• Section 2: The Calculator class (50 points)
o isNumber method (5 points)• Section 3: The AdvanedCalculator class (30 points)
o _getPostfix method (35 points)
o calculate method (10 points)
o isVariable method (5 points)
o replaceVariables method (10 points)
o calculateExpressions method (15 points)
Section 1: The Stack class (20 points)
This class represents the stack data structure discussed in this module. Use the implementation of the Node class to implement a stack that supports the following operations.
Make sure to update the top pointer accordingly as the stack grows and shrinks. You are not allowed to use any other data structures for the purposes of manipulating elements, nor may you use the built-in stack tool from Python. Your stack must use a linked list.
Attributes| Type | Name | Description |
| Node | top | A pointer to the top of the stack |
| int | count | The number of nodes in this stack |
| Type | Name | Description |
| None | push(self, item) | Adds a new node with value=item to the top of the stack |
| (any) | pop(self) | Removes the top node and returns its value |
| (any) | peek(self) | Returns the value of the top node without modifying the stack |
| bool | isEmpty(self) | Returns True if the stack is empty, False otherwise |
| Type | Name | Description |
| str | __str__(self) | Returns the string representation of this stack |
| str | __repr__(self) | Returns the same string representation as __str__ |
| int | __len__(self) | Returns the length of this stack (number of nodes) |
Do not modify the Node class.
Attributes
| Type | Name | Description |
| (any) | value | The value that this node holds |
| Node | next | A pointer to the next node in the data structure |
| Type | Name | Description |
| str | __str__(self) | Returns the string representation of this node |
| str | __repr__(self) | Returns the same string representation as __str__ |
Section 1: The Stack class
push(self, item)
Adds a new node with value=item to the top of the stack. Nothing is returned by this method.
| Input (excluding self) | ||
| (any) | item | The value to store in a node |
Removes the top node from the stack and returns that node’s value (not the Node object).
| Output | |
| (any) | Value held in the topmost node of the stack |
| None | Nothing is returned if the stack is empty |
Returns the value (not the Node object) of the topmost node of the stack, but it is not removed.
| Output | |
| (any) | Value held in the topmost node of the stack |
| None | Nothing is returned if the stack is empty |
Tests to see whether this stack is empty or not.
| Output | |
| bool | True if this stack is empty, False otherwise |
Returns the number of elements in this stack.
| Output | |
| int | The number of elements in this stack |
Returns the string representation of this stack. This has already been implemented for you, so do not modify it. If the class is implemented correctly, __str__ and __repr__ display the contents of the stack in the format shown in the doctest.
| Output | |
| str | The string representation of this stack |
Section 2: The Calculator class (50 points)
Implement a class that calculates mathematic expressions. The input passed to this Calculator is in infix notation, which gets converted to postfix internally, then the postfix expression is evaluated (we evaluate in postfix instead of infix because of how much simpler it is). More details about postfix can be found in the video lectures.
This calculator should support numeric values, five arithmetic operators (+, –, *, /, ^), and parenthesis. Follow the PEMDAS order of operations (you can define precedence of operators with a dictionary). Note that exponentiation is ** in Python.
You can assume that expressions will have tokens (operators, operands) separated by a single space.For the case of negative numbers, you can assume the negative sign will be prefixed to the number.
The str.split() method can be helpful to isolate tokens. Expressions are considered invalid if they meet any of the following criteria:
• Contains unsupported operators 4 $ 5• Contains consecutive operators 4 * + 5
• Has missing operands 4 +
• Has missing operators 4 5
• Has unbalanced parenthesis ) 4 + 5 ( or ( 4 + 5 ) )
• Tries to do implied multiplication 3(5) instead of 3 * 5
• Includes a space before a negative number 4 * - 5 instead of 4 * -5
Make sure to have proper encapsulation of your code by using proper variable scopes and writing other helper methods to generalize your code for processes such as string processing and input validation. Do not forget to document your code.
As a suggestion, start by implementing your methods assuming the expressions are always valid, that way you have the logic implemented and you only need to work on validating the expressions.
Attributes| Type | Name | Description |
| str | __expr | The expression this calculator will evaluate |
| Type | Name | Description |
| None | setExpr(self, new_expr) | Sets the expression for the calculator to evaluate |
| str | getExpr(self) | Getter method for the private expression attribute |
| bool | isNumber(self, txt) | Returns True if txt can be converted to a float |
| str | _getPostfix(self, expr) | Converts an expression from infix to postfix |
| float | calculate(self) | Calculates the expression stored in this calculator |
Section 2: The Calculator class
setExpr(self, new_expr)
Sets the expression for the calculator to evaluate. This method is already implemented for you.
| Input (excluding self) | ||
| str | new_expr | The new expression (in infix) for the calculator to evaluate |
Property method for getting the expression in the calculator. This method is already implemented
for you.
| Output | |
| str | The value stored in __expr |
Returns True if txt is a string that can be converted to a float, False otherwise. Note that float('4.56') returns 4.56 but float('4 56') raises an exception. A try/except block could be useful here.
| Input (excluding self) | ||
| str | txt | The string to check if it represents a number |
| Output | |
| bool | True if txt can be successfully casted to a float, False otherwise |
Converts an expression from infix to postfix. All numbers in the output must be represented as a float. You must use the Stack defined in section 1 in this method, otherwise your code will not receive credit. (Stack applications video lecture can be helpful here).
| Input (excluding self) | ||
| str | expr | The expression in infix form |
| Output | |
| str | The expression in postfix form |
| None | None is returned if the input is an invalid expression |
Section 2: The Calculator class
calculate(self) (10 points)
A property method that evaluates the infix expression saved in self.__expr. First convert the expression to postfix, then use a stack to evaluate the output postfix expression. You must use the Stack defined in section 1 in this method, otherwise your code will not receive credit.
| Input (excluding self) | ||
| str | txt | The string to check if it represents a number |
| Output | |
| float | The result of the expression |
| None | None is returned if the input is an invalid expression |
Section 3: The AdvancedCalculator class (30 points)
The AdvancedCalculator class represents a calculator that supports multiple expressions over many lines, as well as the use of variables. Lines will be split by semicolons (;), and every token will be separated by a single space. Each line will start with a variable name, then an ‘=’ character, then a mathematical expression. The last line will ask to return a variable.
You can assume that an expression will not reference variables that have not been defined yet.
You can assume that variable names will be consistent and case sensitive. A valid variable name is a non-empty string of alphanumeric characters, the first of which must be a letter.
You must use a Calculator to evaluate each expression in this class, otherwise, no credit will be given.
Attributes| Type | Name | Description |
| str | expressions | The expressions this calculator will evaluate |
| dict | states | A dictionary mapping variable names to their float values |
| Type | Name | Description |
| bool | isVariable(self, word) | Returns True if word is a valid variable name |
| str | replaceVariables(self, expr) | Replaces all variables in an expression with values |
| dict | calculateExpressions(self) | Calculates all expressions and shows state at each step |
|
>>> C = AdvancedCalculator() >>> C.setExpression('A = 1;B = A + 9;C = A + B;A = 20;D = A + B + C;return D') >>> C.states {} >>> C.calculateExpressions() # spacing added for readability {'A = 1': {'A': 1.0}, 'B = A + 9': {'A': 1.0, 'B': 10.0}, 'C = A + B': {'A': 1.0, 'B': 10.0, 'C': 11.0}, 'A = 20': {'A': 20.0, 'B': 10.0, 'C': 11.0}, 'D = A + B + C': {'A': 20.0, 'B': 10.0, 'C': 11.0, 'D': 41.0}, '_return_': 41.0} >>> C.states {'A': 20.0, 'B': 10.0, 'C': 11.0, 'D': 41.0} |
Section 3: The AdvancedCalculator class
isVariable(self, word) (5 points)
Determines if the input is a valid variable name (see above for rules for names). The string methods str.isalpha() and str.isalnum() could be helpful here.
| Input (excluding self) | ||
| str | word | The string to check if it is a valid variable name |
| Output | |
| bool | True if word is a variable name, False otherwise |
Replaces all variables in the input expression with the current value of those variables saved in
self.states.
| Input (excluding self) | ||
| str | expr | The input expression that may contain variables |
| Output | |
| str | The expression with all variables replaced with their values |
Evaluates each expression saved in self.expressions. For each line, replace all variables in the expression with their values, then use a Calculator object to evaluate the expression and update self.states. This method returns a dictionary that shows the progression of the calculations, with the key being the line evaluated and the value being the current state of self.states after that line is evaluated. The dictionary must include a key named ‘_return_’ with the return value as its value.
Hint: the str.split(sep) method can be helpful for separating lines, as well as separating the variable from the expression (for the lines that are formatted as var = expr). The str.strip() method removes the white space before and after a string
>>> 'hi;there'.split(';')
['hi', 'there']
>>> 'hi=there'.split('=')
['hi', 'there']
>>> ' hi there '.strip()
' hi there'
| Output | |
| dict | The different states of self.states as the calculation progresses. |
