Lab 05 - Expressions Toggle navigation CS 235 Info References Schedule Syllabus Admin TA Hours Content Labs Lab 01 - Grades Lab 02 - SNAP Lab 03 - Linked List Lab 04 - Iterator Lab 05 - Expressions Lab 06 - Railroad Lab 07 - 3D Maze Lab 08 - BST Lab 09 - Maps and Sets Lab 10 - Quicksort Lab 11 - AVL Test Labs Lab 00 - Hello World Lab 00a - Day Of Week C++ Exercises Code Review Quizzes Help Queue _ Discord (General) Email/Zoom (Section 001) Lab 05 - Expressions (03/01/2022) References expressions.pptx FAQ Expressions FAQ, Valgrind Files ExpressionManagerInterface.h Expand All Collapse All Description "In computer science, the shunting-yard algorithm is a method for parsing an infix mathematical expression to either a postfix notation expression (also known as Reverse Polish notation), or an abstract syntax tree. A similar algorithm produces a prefix expression (known as Polish notation). The algorithm was invented by Edsger Dijkstra and is named the 'shunting yard' algorithm because its operation resembles that of a rail road shunting yard." Learning Outcomes By completing the Expressions Lab, you will be able to: Use an STL stack in parsing expressions into an infix vector. Convert expressions from infix to postfix notation. Convert expressions from infix to prefix notation. Evaluate postfix expressions using an operator and operand stack. Discussion Infix, Postfix and Prefix notations are three different but equivalent ways of writing expressions. In all three versions, the operands occur in the same order, and just the operators have to be moved to keep the meaning correct. InFix Notation Operators are written in-between their operands. Unfortunately for the computer, infix is the usual way we write expressions. An expression such as "A * ( B + C ) / D" is usually taken to mean something like: "First add B and C together, then multiply the result by A, then divide by D to give the final answer." Infix notation needs extra information to make the order of evaluation of the operators clear: rules built into the language about operator precedence and associativity, and parentheses/braces/brackets which allow users to override these rules. For example, the usual rules for associativity say that we perform operations from left to right, so the multiplication by A is assumed to come before the division by D. Similarly, the usual rules for precedence say that we perform multiplication and division before we perform addition and subtraction. PostFix Notation To evaluate a mathematical expression in infix notation, you read a number, then an operator, then a number and evaluate... unless there's a set of parenthesis in there... oh and you have to check for order of operations first. As you might imagine, it can be very difficult for a computer to procedurally evaluate infix expressions because of all of the rules and exceptions. As an example, consider the following expression: 2 + 3 * 5 = ? We can easily evaluate this to be 17, but imagine trying to come up with an algorithm that knows to go back and check for order of operations! It would be a much easier algorithm to simply read from left to right evaluating each piece of expression as you get to it. In fact, that's what postfix is. The above infix expression is converted to postfix as follows: 2 + 3 * 5 = 3 5 * 2 + To evaluate a postfix expression, you do what you would for infix, but instead of number, operator, number, you evaluate it as number, number, operator. So, in the above example we read from left to right 3 and 5 will be multiplied together and the the result of that and 2 will be summed together. In other words, 3 5 * = 15 and 15 2 + = 17. This technique allows for a very simple left-to-right procedural evaluation of mathematical expressions and is commonly used in simple computers. PreFix Notation In prefix notation, operators come before their operands. The infix expression "A * ( B + C ) / D" is the same as the prefix expression "/ * A + B C D". The prefix expression can be fully parenthesized (totally unnecessary) for clarity at "(/ (* A (+ B C) ) D)". As with postfix, operators are evaluated left-to-right and parentheses/braces/brackets are superfluous. Operators act on the two nearest values on the right. Although prefix "operators are evaluated left-to-right", they use values to their right, and if these values themselves involve computations then this changes the order that the operators have to be evaluated in. In the example above, although the division is the first operator on the left, it acts on the result of the multiplication, and so the multiplication has to happen before the division (and similarly the addition has to happen before the multiplication). Because postfix operators use values to their left, any values involving computations will already have been calculated as we go left-to-right, and so the order of evaluation of the operators is not disrupted in the same way as in prefix expressions. Shunting-yard Algorithm You may also refer to Edsger Dijkstra's "Shunting-yard algorithm" for additional help, which can be viewed here. The Lab Lab guidelines: Expression strings are already tokenized (i.e., separated by any number of spaces) and consist of the following: integers (any number of digits) brackets ([]), braces ({}), and parentheses (()) and +, -, *, /, and % (modulo) operators. Operators for this lab have both precedence and associativity as follows: OPERATOR PRECEDENCE ASSOCIATIVITY *, /, % 2 Left to Right +, - 1 Left to Right (, [, { 0 Left to Right Valid expressions need to satisfy standard infix rules of precedence and associativity. Your calculations should perform integer operations and produce integer results. {,},(,),[, and ] are the only symbols considered for brace/parenthesis types that we will use. You may use the STL stack and vector classes found in the C++ Standard Template Library (ie. #include and #include ). You are given the interface file (ExpressionManagerInterface) to help with member function definitions and organization. Do NOT hard code any solutions into your code (unless you want 0 points for the lab). Lab requirements: An ExpressionManager class contains the input string as well as vectors of infix, postfix, and prefix tokens. Your class should be derived from the abstract interface class ExpressionManagerInterface. Input consists of any combination of the following commands: Expression:
Infix:
Postfix:
Prefix:
Value: The Expression command stores the argument string in an instantiated ExpressionManager object. Output the expression string exactly as read from the input file. The Infix command parses the Expression string into a vector and outputs the the vector tokens separated by a single space. The Infix command detects infix expression errors but outputs only the first one according to the following order: First check for an unbalanced expression ->> throw "Unbalanced" then throw the appropriate error immediately when an error is found. Two adjacent operators ->> throw "Missing Operand" Illegal operator ->> throw "Illegal Operator" Too many operands for the number of operators (operators = operands + 1) ->> throw "Missing Operator" Adjacent operands without operator ->> throw "Missing Operator" Expression: 43 + 2 * 19
Infix: 43 + 2 * 19 For this lab only, the autograder will NOT squish horizontal spaces (including spaces at the end of the line)! Make sure there is only one space between expression tokens when outputting the infix vector values. The Postfix command outputs the postfix representation of the ExpressionManager object. Expression: 43 + 2 * 19
Postfix: 43 2 19 * + The Prefix command outputs the prefix representation of the ExpressionManager object. Expression: 43 + 2 * 19
Prefix: + 43 * 2 19 The Value command outputs the value of the ExpressionManager object expression. Expression: 43 + 2 * 19
Value: 81 Your calculations should perform integer division and produce integer results. Steps to Success: Step 1 - Begin with a main function. Use argv[1] for the name of the input file and argv[2] as the name for the output file. The first word on each input line will be the Expression command followed by an expression string. Read and print the lines of the input file. Step 2 - Design and implement an ExpressionManager class. The following member functions are to be implemented: /** Return the infix tokens of the expression string (separated by a space)
Throw an error if not a valid infix expression as follows:
First check to see if the expression is balanced ("Unbalanced"),
then throw the appropriate error immediately when an error is found
(ie., "Missing Operand", "Illegal Operator", "Missing Operator") */
virtual string infix(void); /** Return a postfix representation of the infix expression */
virtual string postfix(void); /** Return the integer value of the infix expression */
virtual int value(void); /** Return a prefix representation of the infix expression */
virtual string prefix(void) Step 3 - Implement and debug each function in turn before preceding to the next function. Step 4 - Once you've tested each part individually, put it all together and run your code against the provided test cases. Videos: A short video has been created for this lab which you may find very helpful. Keep in mind, we have simplified and renamed this lab from what it used to be, so the first couple portions of the video will not be directly applicable, but you may find value in understanding those parts which have been removed. You can watch it here. Helps and Hints Reading from a File.(collapse) Use extraction operator (">>") to read from the input stream. For example: // process input strings
string line, command;
while (getline(in, line))
{
try
{
if (line.size() == 0) continue;
istringstream iss(line);
iss >> command;
if (command == "Expression:")
{
// procession expression ...
continue;
}
else if (...)
{
// ...
continue;
}
}
catch (std::exception& e)
{
out << e.what() << endl;
}
} Understanding Valgrind Output.(collapse) You can find helpful hints and explanations of Valgrind output here. Expressions Grading Criteria Instructions for submitting your lab: Zip all your lab source files (.cpp, .hpp, .h) into one folder. DO NOT INCLUDE YOUR WHOLE PROJECT! Submit your zipped lab source using the "Labs" tab on the class website. Your submitted lab source will be compiled and executed using a lab g++ compiler. Both input and output files will be specified by command line arguments. An auto-grader will compare your output files with expected results and you will momentarily receive your score via email. The auto-grade process may abort on the first error. If so, correct the error and try again. You may re-submit your zipped source as many times as you like. Use the following test input and resulting output files in testing your Expressions lab. Input File Output File Test #1 lab05_in_01.txt lab05_out_01.txt Test #2 lab05_in_02.txt lab05_out_02.txt Test #3 lab05_in_03.txt lab05_out_03.txt Given the following input file: Expression: 33 @ 127
Infix:
Expression: 4 % 2 -
Infix:
Expression: 4 2 & -
Infix:
Expression: 3 % { 7 - ( 2 / [ 5 - 81 ] } + 1 )
Infix:
Expression: 2 * 3 + ( 6 / 4 ) - 6
Infix:
Expression: 2 * 3 + ( 6 / 4 ) - 7
Postfix:
Expression: 2 * 3 + ( 6 / 4 ) - 8
Value:
Expression: 2 * 3 + ( 6 / 4 ) - 9
Prefix: the auto-grader will be expecting to find in your output file the following sections: Fail Pass Auto-graded Section Requirements (50 points) Score = 0 Expression: 2 * 3 + ( 6 / 4 ) - 6
Infix: 2 * 3 + ( 6 / 4 ) - 6 Note: The autograder will NOT squish horizontal spaces! 10 points Expression: 2 * 3 + ( 6 / 4 ) - 7
Postfix: 2 3 * 6 4 / + 7 - 10 points Expression: 2 * 3 + ( 6 / 4 ) - 9
Prefix: - + * 2 3 / 6 4 9 10 points Expression: 2 * 3 + ( 6 / 4 ) - 8
Value: -1 10 points Expression: 33 @ 127
Infix: Illegal Operator
Expression: 4 % 2 -
Infix: Missing Operand
Expression: 4 2 & -
Infix: Missing Operator
Expression: 3 % { 7 - ( 2 / [ 5 - 81 ] } + 1 )
Infix: Unbalanced 10 points Memory leaks, g++ compiler warnings, or array out-of-bounds detected. -10 points The lab source will be peer reviewed using the following rubric: No Partial Yes Peer Review Score = 0 An ExpressionManager class is used to contain an expression and is derived from the abstract interface class ExpressionManagerInterface. Your ExpressionManager class throws an error for invalid expressions. Header Files #define header guards used to prevent multiple inclusion in all .h files. (No "#pragma once" directives.) Class member functions of 10 or less lines of code are implemented in the function declaration. Member functions of more than 10 lines of code are implemented outside the class declaration (.h or .cpp file.) No global variable or object definitions (instantiations) in .h files. Objects and Classes Upper CamelCase (or Underscore_Case) class names. Member functions that don't mutate data members declared const. All class data members and helper functions private (getter's and setters's for private data members only as needed.) All derived classes have public toString and friend insertion member functions. Functions and Variables Descriptive lower camelCase (or underscore_case) function and variable names. Constant and #define names all capital letters. If needed, "reasonable" documentation precedes function declarations. Program Format One statement per line. Consistent usage of braces with 3 or 4 space indention per scope. One space around binary operators and other appropriate items. Overall Rating Easy to follow, readable, organized, scaleable, well commented. Excellent Good Average Poor ***NOTE: Any attempt to circumvent any lab requirement (ie, hard coding output, using loops instead of iterators where required, modifying a class interface, etc.) will be reported by peer reviewers and result in a zero score for the lab. Total Score = 0
