Specification of Programming #3: Expression Evaluator

Purpose of the module

Given a table storing the values of a number of variables, the functions in this module are implemented to evaluate any infix arithmetic or logic expression with parentheses, arithmetic operators (+, −, *, /, %), relational operators (>, >=, <, <=, = =), logical operators (&&, ||, !), numerical constants, and the variables in the table.

Algorithms and data structures

· Evaluating arithmetic expressions and logic expressions: Arithmetic expressions and logic expressions are infix expressions (for example, in 3*4, the binary operator * appears between the two operands 3 and 4) involving various arithmetic, relational, and logocal operators ( e.g. +, −, *, /, %, >=, <, <=, = =, &&, ||, !) with different precedence levels. One major hurdle to evaluate these infix expressions is to apply the operators to evaluate portions of the expressions in the right order respecting the precedence levels of the operators. For example, in 2+3*4, we need to evaluate 3*4 first, instead of doing 2+4.

· Infix-to-postfix conversion and Postfix evaluation: To deal with this, one possibility is to first convert a given infix expression into a corresponding postfix expression and then use a stack to help evaluate the postfix expression. The issue of operator precedence levels is resolved by conversion into the postfix expression since the postfix expression uniquely defines the order for applying the operators during the evaluation. Very carefully read and understand the following descriptions regarding the details of the algorithms and data structures for infix-to-postfix conversion and Postfix evaluation.

· Using vectors to simulate the operations of stacks: We will use the vector class (as a sequential container) in the C++ Standard Template Library together with its methods such as push_back( ) and pop_back( ) operation to simulate the operator of a stack needed in the conversion and evaluation algorithms.

· Using associative maps to keep the names and values of variables: We will use the associative map class (as an associative container) in the C++ Standard Template Library to handle the storage and update of the values of the variables used in the expression evaluation. You should carefully study the examples on how to use the associative map in map.cpp and mapAsAssociativeArray.cpp as described in Lab#3. Another useful resource is the map container description in the SGI online tutorials on the C++ Standard Template Library.

About the Sample Skeleton Project

· Download this sample executable and this zipped sample skeleton project. Play with the sample executable and read the code in the sample skeleton project carefully. The project contains the following header files and source code files: lexScanner.h, lexScanner.cpp, expEvaluator.h, expEvaluator.cpp, and testExpEvaluator.cpp. See the descriptions below.

· The header file lexScanner.h and the source code file lexScanner.cpp: They are the header file and the implementation of the lexical scanner module in programming #2. You should replace the empty lexScanner.cpp file with your own lexScanner.cpp file.

· The header file expEvaluator.h: It contains the information of several type definitions and the ExpressionEvaluator class that should be implemented in expEvaluator.cpp. The static member functions of the ExpressionEvaluator class should provide services to callers outside expEvaluator.cpp. Callers outside expEvaluator.cpp can simply include the header file expEvaluator.h and then call the static member functions of the ExpressionEvaluator class in expEvaluator.cpp according to the prototype information in expEvaluator.h.

· The source code file expEvaluator.cpp: This is the code of the expression evaluator module, and in it we have the implementation of functions providing expression-evaluation service to one another and/or to the outside callers.

· The source code file testExpEvaluator.cpp: This is actually not a part of the expression-evaluator module. Instead, it simply includes the header files lexScanner.h and expEvaluator.h to play the role of a user of the scanner module and the expression-evaluator module to test the implementation in expEvaluator.cpp.

Things to do:

Complete the implementation of all functions in expEvaluator.cpp and then integrate it with what you have from Programming #2.

1. Recognize != as an additional relational operator: Enhance the code you have for the lexical scanner module (examine and enhance getPerLineTokenVectFromOneCharArray in lexScanner.cpp) so that getPerLineTokenVectFromOneCharArray can recognize != as a separate token while isRELATIONAL_OP can recognize != as an additional relational operator.
2. Incorporate != and % : Enhance the code of the static member function ExpressionEvaluator::precedenceLevel in expEvaluator.cpp and the code in the static member function ExpressionEvaluator::postfixEvaluator in expEvaluator.cpp so that we are able to apply both the != relational operator and the % modulus operator in our expressions. The modulus operator % should have the same precedence level as the * and / operators while the relational operator != has the same precedence level as the = = operator. Note: for the % modulus operator to deal with possible non-integral operands, you should cast the operands involved in the modulus operation into integers and then apply the standard integer modulus operation.
3. Complete the static member function ExpressionEvaluator::infixToPostfixConversion in expEvaluator.cpp so that it can (i) determine whether a given infix arithmetic expression is a valid expression, and (ii) convert this infix arithmetic expression into an equivalent postfix arithmetic expression if it is a valid infix expression.
4. Extensively test your implementation (through the tests in main function in testExpEvaluator.cpp) to make sure it works in all situations. Your code should be able to evaluate any infix arithmetic or logic expression with parentheses, arithmetic operators (+, −, *, /, %), relational operators (>, >=, <, <=, = =, !=), logical operators (&&, ||, !), numerical constants, and the variables in the given variable table.
5. Integration with what you have from Programming #2: When you are all set with the implementation in expEvaluator.cpp, you should include expEvaluator.h and expEvaluator.cpp into the project of your integrated user interface module and lexical scanner module. In your user interface module (interface.cpp), you should implement one more option for the user: a calculator option to evaluate whatever arithmetic or logic expression involving only numerical constants (no variables), parentheses, and arithmetic or logical operators. You should implement this by appropriately reading in one line of input from the user, passing it to some appropriate member function of the LexicalScanner class to get a token vector out of it, and then appropriately passing things to call some member function in the expEvaluator class to evaluate the expression. In other words, it is very similar to what the code in the main function of testExpEvaluator.cpp did.
6. Submission: Fill out the self-evaluation form and submit it together with all your source code as a zip file through Canvas. Make sure you have done Step 5 to integrate all the modules together and add an option of lexical analysis when interacting with the user.