Your assignment for this program is to evaluate a numeric expression in postfix notation using a dynamic (pointer based) stack. As stated in the handout, in order to evaluate a numeric expression, a compiler converts an infix numeric expression to postfix notation and then it uses an algorithm and a stack to evaluate the expression. Your program should implement the pseudocode algorithm described in the attached handout.

Your program will read and evaluate expressions stored in an input file (infile.txt). The process will continue until the end of file is read. After each expression is read and evaluated, the expression and its value should be output to a text file using the following format.

EXPRESSION: XXXXXXXXXXXXXXXXXXXXXXXXXXX

VALUE:XXXXXX

You may assume all expressions in the file will be in postfix notation. You may also assume that the expressions will only have the following operators: +, -, *, /. The variables found in the expressions will be either A, B, C or D. No other variables will be used. The variables should be assigned the following values in your program:

A = 4.0, B = 6.0, C = 10.0, D = 20.0

Assume that all variables will be uppercase. You may store the expression in a string and extract one character at a time. Please use the data file shown below for the program run.

Output your run to another file.

Please note: Your stack should include a working destructor.

infile.dat

DC-

ABC++

ABCD*+A/-

AB+CD-*

Hint: You can use this code to help you input the string and process each character in the string.

while(!in.eof()){

in>>s; // s is a string, read the entire string on the line

// process each character in the string using s.length() and a for loop

for (int i = 0; i < s.length(); i++)

//check to see if the character is an operator (+,-,*,/)

// or operand A,B,C,D

if(s.substr(i,1)== ) // use the handout algorithm for the rest

}

Given s, declared as a string then s.length() returns the number of characters in the string; s.substr(i,1) returns the character in the ith position of the string. The string library contains the length and substr methods; substr(i,n), another method, will return n characters starting at position i of a string.

Please pass in:

main.cpp

Stack.h

Stack.cpp

Your Problem Solving Lifecycle design Answer all questions and include a flowchart for the main function. The PSP is attached for a reference.

A UML diagram for the Stack class.

Problem Solving Lifecycle The Problem Solving Lifecycle description is on Blackboard for students who have not seen this before.

1. Describe the problem.

2. Analyze the problem (the second step of the PSL)

(a) What does the solution require as input? What data types will you use?

(b) What outputs should be made by the solution?

(c) How are the inputs and outputs related (equations, conversions, how to get from input to output)?

(d) Are there constraints on the input (ranges, minimums, maximums, etc.)?

3. Design an algorithm to solve the problem. You need a flow chart for the main. Draw/design the flowcharts on a separate piece of paper, stapled to your packet.

4. Test Case Design.

(a) What are the test inputs? Use the inputs shown on page 2

(b) What are the corresponding expected outputs?

(c) What are the corresponding actual outputs via a trace?

Test Inputs Expected Output Implementation/Run Output

5. Implement the Design. Create the Source Code and Run it.

6. Test the Implementation. Show your run results in Table 4. Do they match?