## Description

100 points

Follow the instructions presented in the Programming Rules documents. Submit

the header and source files as well as your Makefile. Also submit the input file

you used for testing. Note that your program needs to compile in order to get any

credit at all.

Adhere to the style guidelines.

Start Early!

Algebraic Calculator

You are going to implement a simple calculator. Your calculator is going to parse

infix algebraic expressions, create the corresponding postfix expressions and

then evaluate the postfix expressions. The operators you are allowed to use are:

+, -, * and /. Your operands are integers. The input to your program is a file

infixFile that contains a sequence of infix expressions (one expression per line).

Your output is going to consist of one file: a resultFile that contains the postfix

expressions and their evaluation.

Part 1 (%60)

You need to read infix expressions from the input infixFile (one expression per

line) and produce the corresponding postfix expressions that you will save in file

resultFile. An example of an infix expression is the following:

(12 + 3) * ( 9 – 74) + 34 / ((85 – 93) +(3 + 5) * 3) – 5

You have to parse this expression from left to right, identify the operands, the

operators and the parentheses and ignore blanks. You will implement the infix to

postfix conversion algorithm using a stack of operators and parentheses. Use the

pointer-based stack implementation we used in class.

You should be able to handle syntactically wrong infix expressions using

exceptions. In this case you should output a message on the resultFile indicating

the type of error (i.e. “missing right parenthesis”).

Part 2 (%40)

Now you need to evaluate each postfix expression using the stack algorithm

described in class and place the results in the file resultFile.

Extra Credit (10 points)

Our algorithm transforms an infix to a postfix expression according to a left to

right association rule when the operators have the same precedence

(i.e. 5+4+3 becomes 5 4+3+ and not 5 4 3 + +).

The exponentiation operator though should follow a right to left association rule.

When we write 2^3^5 we mean 2^(3^5) which corresponds to the postfix

expression

2 3 5 ^ ^. Our algorithm though provides as a result the expression 2 3^ 5^ which

corresponds to the infix expression (2^3)^5. Modify the infix to postfix algorithm

so that the exponentiation operator is right to left associative.

Coding Instructions

Create a class (not templated) named InfixToPostfixCalculator. For this class use

a header file named InfixToPostFixCalculator.h and an implementation file named

InfixToPostfixCalculator.cpp.

This class needs to have one no-parameter constructor and two public functions.

The first one is

string ConvertInfixToPostfix(const string &input_infix)

It reads a string holding the infix expression, calculates the postfix expression

and then returns the postfix expression as a string.

In the output expression separate the various parts using a comma (,). So for

example the string corresponding to a valid postfix expression could look like:

3,134,76,+,-

Note that there are no parentheses in the output postfix expression.

The other function is

double CalculatePostfix(const string &input_postfix)

It reads an input postfix expression (in the format described above), calculates

the result and returns it.

Both functions should throw exceptions when the input expressions are not of the

right form.

Add as many private functions and data members as necessary.

In the main file you will create an object of type InfixToPostfixCalculator. Then

you will read the input file line by line. Each line will be a string that you will pass

to ConvertInfixToPostfix(). You will save the result to the result file. Finally, if

ConvertInfixToPostfix() returns without an exception, you will run the

CalculatePostfix() function on the returned string. You will write the result on the

output file as well.

In conclusion you need to have the following files:

(a) The files required for the stack (StackInterface.h, LinkedStack.h,

LinkedStack.cpp) and its exceptions: PreconditionViolatedException.h,

PreconditionViolatedException.cpp).

(b) The InfixToPostfixCalculator.h and InfixToPostfixCalculator.cpp files as

well your exception files (not required if you use the same exceptions as

the stack).

(c) A main file Test.cpp that includes the InfixToPostfixCalculator.h and tests

the algorithms as described above.