CMPT 212 Assignment 1
Spring 1998 ------------
Due date: Start of class, Friday, February 6, 1998.
1. Goal
- To become familiar with C++ header files and separate compilation.
- To become familiar with pointers and dynamic memory allocation
and release.
- To become familiar with the Borland C++ IDE.
2. Overview
- The program will be a simple program to read in an arithmetic
expression, parse it, display it, and evaluate it. Future
assignments will be build on this assignment.
3. Description
3.1 Arithmetic Expressions
- An arithmetic expression is defined as follows:
An "expression" is a sequence of one or more terms
which are separated by "+" or "-".
A "term" is a sequence of one of more factors which are
separated by "*" or "/".
A "factor" is either a constant (such as -5 or 3.684) or
an expression enclosed in parentheses.
3.2 Parsing Hints (these are only hints -- you don't have to
use them)
- Have a function "parseExpr()" which parses an expression
using this algorithm:
1. parse the first term (call it expression "e1").
2. if the next character is a "+" or "-":
2.1 create a new expression "e" where "e1" is
the first operand and the operation is
either "Addition" or "Subtraction"
(depending on the character looked at
in 2.).
2.2 parse the next term (make it the second
operand of "e".
2.3 go to 2.
3. return "e"
- Have a function "parseTerm()" which parses a term
using this algorithm:
1. parse the first factor (call it expression "e1").
2. if the next character is a "*" or "/":
2.1 create a new expression "e" where "e1" is
the first operand and the operation is
either "Multiplcation" or "Division"
(depending on the character looked at
in 2.).
2.2 parse the next term (make it the second
operand of "e".
2.3 go to 2.
3. return "e"
- Have a function "parseFactor()" which parses a factor
using this algorithm:
1. if the next character is a "(":
1.1 skip over the "(".
1.2 parse an expression (call it "e").
1.3 skip over the ")".
1.4 return "e".
2. else, the factor is a constant (you can use
"strtod" to convert part of a string to a
"double").
- In class I will give other hints as to how to parse an
expression. If you miss a class, check the online
lecture notes to see what you missed.
3.3 Program Execution
- The program will prompt for user input:
"Enter an expression:"
- The user will enter an arithmetic expression.
- If the user enters an empty string (presses RETURN without
entering anything), then the program ends.
- On the next line, the program will display the expression
in prefix notation. In prefix notation, the operator
is displayed before each of its operands. Here are
some examples of infix and prefix notation:
infix notation prefix notation
1+3 + 1 3
25 25
3-5/7 - 3 (/ 5 7)
3+6-4 - (+3 6) 4
- On the following line, the program will display the
value of the expression.
- Note that the program must follow the normal rules of
precedence for arithmetic operations:
"*" and "/" have a higher precedence than "+" and "-",
and parentheses have the highest precedence.
So 3-5/7 is the same as 3-(5/7) and not (3-5)/7.
Operators at the same precedence are evaluate from
left to right. So 1-2+3 is the same as (1-2)+3
and not 1-(2+3).
- See Section 9 below for a sample run of the program.
4. Design of the Program
4.1 Modules
- The program will consist of three modules: a "Parse" module,
a "Evaluation" module, and "Main" module.
4.2 The Parse Module
- This module defines the data types and functions to
parse a character string into an expression.
- The source files for this module will be called "parse.h" and
"parse.cpp".
4.2 The Evaluation Module
- This module defines the data types and functions to
display an expression and evaluate an expression.
- The source files for this module will be called "eval.h" and
"eval.cpp".
4.4 The Main Module
- The source file for this module will be called "asgn1.cpp".
- This module contains the main function of the program.
5. Design Features
5.1 Error Checking
- Very little error checking needs to be done.
- The program does not have to check for out-of-memory errors
or input errors.
5.2 Given Code
- The header file for the Parse module and the Evaluation
module are given to you. You must use them. You must not
change them.
- You must implement all of the functions defined in these
files.
- These files will be available on the class web page and also
in the Assignment Lab on the N: drive.
5.5 Bool Type
- If you are using a compiler which does not support the "bool"
type, you must define the "bool" type yourself in a header
file called "bool.h". Your program must be able to compile
without errors under the Borland C++ in the Assignment Lab.
5.6 I/O
- You must do all output using the "<<" operator.
- You may use "cin.getline()" to read in the input character
string.
5.7 Miscellaneous
- Use "const" wherever possible.
- Do not define any classes for this assignment.
- Use the smallest scope and lifetime for every variable,
constant, and function.
6. Source Code Comments
- Your source code must be fully commented.
- See the Sample Assignment on the web page for an example of
the expected commenting style.
http://www.cs.sfu.ca/CC/212/simpson/98-1/assignments/sample.html
7. Test Runs
- Run the program with these input strings:
4
2+5
3-5+7
3+6/8*9-4
1+2*(3-4)
8. What to Hand In
- Title page containing:
a. Course number
b. Assignment number
c. Student name
d. Student number
e. Student email address
- Listing of the source code in this order:
a. main.cpp
b. parse.h
c. parse.cpp
d. eval.h
e. eval.cpp
f. bool.h (if written -- see Section 5.5 above)
- Scripts of the test run (see Section 7 above).
9. Sample Run
- Here is a sample run of the program:
Enter an expression: 56
56
56
Enter an expression: 6-4*2+7
(+ (- 6 (* 4 2)) 7)
5
Enter an expression: 5-7
(- 5 7)
-2
Enter an expression: 1/2-3
(- (/ 1 2) 3)
-2.5
(end of assignment)