继续完成语法树，熟悉 Traversal ，解析表达式。
Overview
Over the past several weeks we have gotten quite familiar with the tree
traversal application. Originally, it could parse and execute simple math
expressions using just the +, -, *, and / operations. In class, you added
support for the modulus “%” operator and began adding support for the “get”
command. You do not need to support negative exponents.
For this assignment you must continue extending the application to support the
common exponent (^) and factorial (!) operations. Also add support for the
ceiling (|) operator - this binary operator returns the larger of the two
numbers, and the floor (_) operator - returns the smaller of the two numbers.
Clearly three of these operators are binary and the other unary (and left-
associative). Make sure your application supports the proper order of
operations for these operators - | and _ have the same precedence as multiply.
I have provided example automated tests for the ^ operator, you need to add
unit tests for the other new operators.
Second, you must fully implement the “get” command begun in class. This
command is only used in verbose mode. It can be executed at any time the
application is running in verbose mode. It will print out the current value
for the requested variable. The get command should appear in the “menu” of
available commands only after at least one variable has been set. If get is
called on an invalid variable (i.e. one that hasn’t been given a value) print
out an appropriate error message. Also implement automated tests for the GET
command. Use other testing examples in the test directory to inform you on how
to write tests for a command.
Third, you must implement the “list” command. This command is only used in
verbose mode. It can be executed at any time the application is running in
verbose mode. It will print out all declared variables and their current
value. The list command should appear in the “menu” of available commands only
after at least one variable has been set. List executed when there are no
variables prints out nothing. Implement automated tests for the LIST command.
Fourth, add a “history” command that prints out the last 5 valid commands
entered in verbose mode (fewer if the user hasn’t entered 5 since the program
began running - never more than 5). An invalid expression is not considered a
valid command. This command is only for verbose mode, and it should appear in
the verbose menu only after one or more valid commands have already been
executed. Add automated tests for the HISTORY command. See below for a sample
end-user execution of the command (I have omitted the verbose menu for
clarity):
> format in-order
> expr 5 + 5
> print pre-order
+ 5 5
> eval post-order
> history
1) format in-order
2) expr 5 + 5
3) print pre-order
4) eval post-order
> history
1) format in-order
2) expr 5 + 5
3) print pre-order
4) eval post-order
—|—
Lastly, a couple of usability issues frustrates me:
A) Some invalid expressions can cause the program to fail. For example, on my
computer the following will cause a crash:
- 3 +
- 3 * 5 /
- / 4
I suspect it is any time an operation doesn’t have all of its needed operands.
Fix this so that it at least doesn’t crash. You do not need to worry about
returning a correct answer since there isn’t one.
B) In verbose mode I have to perfectly type commands (in lower case) or the
program quits. Make it so that capitalization of the commands does not matter
and that an un recognized command just results in an appropriate error
message. Case should continue to matter for defining and using variables in
verbose mode.
Sample Test Cases - Not Exhaustive!!!
Test Cases:
operator !
- 5! = 120
- 1! = 1
- 1+5! = 121
- -5! = -120
- 5! + 1 = 121
- 2 * 4! + 1 = 49
- 0! = 1
- 13! –> Error: Factorials of up to 12 are supported
operator % - 5 % 3 = 2
- 5 * 2 % 3 = 1
- 5 - 7 % 3 = 4
- 4! % 7 = 3
- 4 + 1 % 5 = 5
operator | - 5 | 3 _4 = 20
- 5 _ 3 | 4 = 15
- 5 * (3 | 4) = 20
- 5 - 3 | 4 = 1
- -5 | -4 = -4
- 4 | 4 = 4
- 3! | 5 = 6
operator _ - 1 _3 = 1
- -5 _ -4 = -5
- 4 _4 = 4
- 5 | 4 _ 3 = 3
- 5 * 4 _ 19 = 19
get command - set a = 10
- get a
a: 10
—|— - get b
Error: unknown variable “b”
—|—
list command - set a = 10
- set b = 92
- list
a: 10
b: 92
—|—
Expressions That Cause Failure on My Machine - 3 +
- 5 * 9 -
- / 4
Grading Criteria
This assignment will be graded differently than other assignments. Do read the
following carefully:
- Your submission must still compile successfully on both GCC and Clang and must pass the linter test. The automated tests are there to inform your development, but are not exhaustive. Graders will download, compile and run your code against a number of manual test cases that go beyond what are in the automated tests.
- Deductions will be based on the proportion of the automated and manual tests that your application passes. You will not be given the comprehensive list of tests (that is for your grader). But, they will cover many of the same areas as the example tests listed above.
- The graders will verify that the new operators are usable in both the verbose and succinct modes (see sample test cases). And that the get, list and history commands are available in verbose mode.
- You must create appropriate new classes in both the “front-end” and “back-end” (i.e. new classes inheriting from Symbol, ComponentNode and Visitor). The new operations must be supported throughout the application, from the interpreter parsing the expression, to the generation of symbols, to all of the visitors. Your solution must follow the patterns already established within the application. You must use and extend the existing class structure to handle the new features.
- You are free to modify any and all files (include CMakeLists.txt) in order to implement the required functionality, but follow the norms and patterns already established in the code.
Beyond 100
You can earn even more points on this assignment. These extra points are
strictly on this assignment, and you MUST have completed all of the primary
portion of the assignment before you can earn any bonus points, and received
at least 95% on that portion. Only by earning at least 95% on the base part
of the assignment can you get bonus points . There will be no partial credit
for the Beyond 100 work - either you get it right or you do not.
Do or do not - there is no try - Yoda
Here we go:
- 15pts - add a “stats” command to print out the number of each operation used in the current expression. This command can only be executed in verbose mode after a valid expression has been entered. Only print statistics for operations that have been used. Statistics must be calculated using a new Visitor-derived class. The order in which the operations are printed is not relevant. The order in which the operators are printed is not important, nor do we want to print operators that were not used at all. So, for the expression
10 * 9 % (3 + 4) * 6, the stats command will output:
*: 2
%: 1
+: 1
—|— - 20pts - provide better debugging information for when a bad expression is entered. Currently, the application has really bad behavior when invalid expressions are entered. Make this better:
- Print a contextual error message and point to where the invalid character is (——–^)
- Don’t halt the program. Go back to the appropriate prompt (just “>” for succinct mode and list of valid choices for verbose mode)
- Example Test Cases (not exhaustive):
5 + 7 *
——–^ Error: Expecting right operand to *
/ 4
–^ Error: Expecting left operand to /
- 15pts - support floating point values in expressions and variables. Evaluated through trying the functionality in the application. This should work in both verbose and succinct modes. Visitors should properly handle floating point values too.
- Test Cases (not exhaustive):
- 1.5 + 2.25 = 3.75
- 1.5 * 2.25 = 3.375
- 1.5 / 2.25 = 0.66666666666667
- 1.5 - 2.25 = -0.75
- Notes:
- Your ! operator does not have to support floats - but all other operators must
- Notes:
- 30pts - I have always wanted to be able to enter expressions in something other than in-order notation. Enhance the front-end so that it supports both pre-order and post-order expression notation. This should only be available in verbose mode. Some points to consider:
- The verbose mode menu must reflect that this is possible.
- If you also are trying for the better debugger (see above), this enhancement must work in conjunction this that one.
- All valid expressions must be properly parsed, but don’t worry about handling parens.
- This work likely requires a heavy refactoring of the Interpreter class so that there are multiple subclasses. Take some time to think clearly about how you want to structure this.
Reminders
- Ensure that your name, vunetid, email address, and the honor code appear in the header comments of all files that you have altered. This work must be strictly your own.
- All students are required to abide by the CS 3251 coding standard, and provided to you on the first day of class. Points will be deducted for not following the coding standard.
- For full credit, your program must compile with a recent version of
clangorgccand run successfully.- The build will fail if your code is not properly formatted. This is by design. If your code is compiling and running successfully, but the build is failing, then your build is most likely failing because your code is not passing the linter. This can be confirmed by checking if a command involving
linterorclang-formatin the CI build output log has an exit code of 1.
- The build will fail if your code is not properly formatted. This is by design. If your code is compiling and running successfully, but the build is failing, then your build is most likely failing because your code is not passing the linter. This can be confirmed by checking if a command involving
- Your program(s) should always have an exit code of 0. A non-zero exit code (generally indicative of a segmentation fault or some other system error) is reason to worry and must be corrected for full points.
- When submitting the assignment, all files that are provided to you, plus your solution files have been submitted. All files necessary to compile and run your program must reside in the GitHub.com repository.
