CMPT 225 Assignment 2: Evaluating an arithmetic expression

CMPT 225 Assignment 2: Evaluating an arithmetic expression

Due Sunday Oct 15th, 2017, 23:59 pm

Introduction

As it is defined in question C-5.8 in your textbook, postfix notation is an unambiguous way of writing an arithmetic expression without parentheses. It is defined so that if "(exp1 ) ⊗ (exp2 )" is a normal fully parenthesized expression whose operation is "⊗", then the postfix version of this is "pexp1 pexp2 ⊗", where pexp1 is the postfix version of exp1 and pexp2 is the postfix version of exp2 . The postfix version of a single number or variable is just that number or variable. So, for example, the postfix version of "((5 + 2) * (8 - 3))/4" is "5 2 + 8 3 - * 4 /".

A normal expression may have more than one acceptable fully parenthesized version though. For example 2 + 3 + 4 + 5 can be fully parenthesized as ((2 + 3) + (4 + 5)) or (((2 + 3) + 4 ) + 5). It follows that a normal expression may have more than one equivalent postfix notation. Here are some examples of normal (not necessarily fully parenthesized) expressions and one possible postfix notation for them.

  normal expression   postfix notation
  (5+2+3*4)*((2+3)*(5-3))     5 2 + 3 4 * + 2 3 + 5 3 - * *   
  ((8-12) + 4 * 20) / (14 - 12) + 7     8 12 - 4 20 * + 14 12 - / 7 +  
  12 + 3 - 6 + 8     12 3 + 6 - 8 +  
  5 * 2 / 4 * 3     5 2 * 4 / 3 *  
  ( 12 + 3 ) - (6 + 8)     12 3 + 6 8 + -  

The assignment

postfix expressions can be evaluated non-recursively using stack ADT. The goal of this assignment is to write a program that evaluates a given normal (not necessarily fully parenthesized) expression by transforming it into an equivalent postfix notation, and evaluating that using stacks.

The assignment is broken into 4 steps for you:

  1. Implement a generic stack based on a Linked List. The name of the class MUST be genericLinkedListStack and you MUST put it in genericLinkedListStack.h file. You are not allowed to use any of the STL containers but you are welcome to use whatever code that is provided for you on the course homepage or on the slides. Also, make sure you add a print() function so that we can test this class independently. (15%)
  2. Write a function getPostfix (with the following signature) that takes a normal (not necessarily fully parenthesized) expression and returns one of its equivalent postfix notations. You can do this recursively if you wish. Put this function in the postfixUtility.h file. (40%)
    3. string getPostfix(string nexp)
  3. Write a function evaluatePostfix (with the following signature) that takes a postfix expression and evaluates it. Put this function in postfixUtility.h and .cpp files. You will get a full mark for this step even if you use the STL stack. To get a full mark on the next step however, you MUST use your implementation of genericLinkedListStack in evaluatePostfix function. (30%) 
    4. float evaluatePostfix(string pexp)
  4. Write a main function in main.cpp file that takes a string containing a normal (not necessarily fully parenthesized) expressions as an argument and prints its numerical equivalent to the standard output. You MUST use the functions you implemented in postfixUtility.h. If you want a full mark on this step, you MUST use your implementation of genericLinkedListStack in your implementation of evaluatePostfix function. Your file MUST compile and run as follows: (15%)
    5. g++ -c postfixUtility.cpp
g++ -o main.o main.cpp postfixUtility.o
./main.o "(4+3* 12)/ ( 12+ 3/ 2+ 46 /4)"
1.6

What to submit?

  1. genericLinkedListStack.h
  2. postfixUtility.h
  3. postfixUtility.cpp
  4. main.cpp
  5. ExtraFiles.zip (should contain all other files that your code depend on)

Where to submit?

In CourSys under CMPT 225 Assignment2 activity.

Watch out for seemingly small mistakes

You can assume there will be only integers, four primitive operators, parentheses, and spaces in the input. Spaces may or may not be present between numbers and operators (or parentheses) in the input but they will appear between separate numbers (for example 5 2 means 5 and then 2 whereas 52 means fifty-two).

Final Note

While it is OK for you to discuss the high-level idea of how to tackle each of these steps among yourselves, I encourage you to try coming up with the idea yourself. Remember, one of the most important goals of the course is to build your problem-solving skills.