Lab 05 - Expressions (03/01/2022)

References

FAQ

Files

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 <stack> and #include <vector>).

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).

OPERATOR	PRECEDENCE	ASSOCIATIVITY
*, /, %	2	Left to Right
+, -	1	Left to Right
(, [, {	0	Left to Right

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: <string>
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:
1. First check for an unbalanced expression ->> throw "Unbalanced"
2. 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.
1. Use argv[1] for the name of the input file and argv[2] as the name for the output file.
2. The first word on each input line will be the Expression command followed by an expression string.
3. 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. "Reasonable" documentation (pre- and post- conditions) precede function declarations / definitions.
			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. "Reasonable" comments used to document program flow.
Overall Rating			Easy to follow, readable, organized, and 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