Project 03 Stack Project Solution

Description

infix to postfix conversion  and postfix evaluation with stacks

Purpose:

Give students practice using stacks, converting infix to postfix, and evaluating postfix equations.  Also reinforces the following concepts:

 

file i/o

• implementing pseudo-code
• standard template stacks

 

Create a Main.cpp and in it write code which will

 

• open the data.txt

read each infix equation from the data file (one line at a time)

• display the infix equation

create an InToPostflxO  function

• convert the equation to an equivalent postfix (using InToPostfixO which you have to write)

display the equivalent  postfix equation

• create an EvaluatePostfixO function

evaluate the POStfiXequation  (using EvaluatePostfixO which you have to write)

• display the result of the last step

At the top of Main.cpp, you MUST include a standard ‘honesty” statement similar to:

• I \<name\> have not used any code other than my own (or that in the textbook) for this project. I understand that any violation of this disclaimer will result in a 0 for the project.

 

Correct  Output

 

infix: (8+3)*(5-6) postfix:  8   3  + 5  6   –   * answer:  -11

 

infix: ((8+3)*(2-7» postfix:  8   3  +  2  7   –   * answer:  -55

 

: ((8+3)*2)-7 postfix:  8   3  +  2   * 7   – answer: 15

infix: (8*5)+((3-2)-7*3) postfix:  8   5   *  3  2   –   7   3 answer: 20

 

*  –   +

infix: ((8*5+3)-7)-(5*3)

postfix:  8   5   *  3  +  7   –   5  3   *  –

answer: 21

 

 

infix: 7*9+7-5*6+3-4

postfix: 7   9   * 7   + 5  6   *  – 3  + 4   –

answer: 39

 

 

Evaluating  a Postfix  Expression

 

1. Initialize a stack of doubles
2. do

if (next input is a number)

Read the next input and push it onto the stack

 

else

 

popped as the left operand)

 

Read the next character, which is an operator symbol

Use top and pop to get the two numbers off the top of the stack

Combine these two numbers with the operation (using the second number

Push the result onto the stack

whi Je (there is more of the expression to read);

3. At this point, the stack contains one number which is the result of the expression

 

Infix to  Postfix   Pseudo   Code

1. initialize stack to hold operation symbols and parenthesis
2. do

if (the next input is a left parenthesis)

Read the left parenthesis  and push it onto the stack else if (the next input is a number or operand)

Read the operand (or number) and write it to the output else if (the next input is one of the operation  symbols)

 

while ( stack is not empty AND

stack’s top is not left parenthesis  AND

stack’s top is an operation  ./ith equal or higher precedence

than the next input symbol)

 

print the stack’s top

pop the stack’s top

 

push the next operation  symbol onto the stack else

read and discard the next input symbol (should be a right parenthesis)

print the top operation and pop it

while ( stack’s top is not a left parenthesis)

print next symbol on stack and pop stack pop and discard the last left parenthesis

 

whi Le (there is more of the expression  to read)

 

 

3. print and pop any remaining operations on the stack (there should be no remaining left parenthesis)

Main.cpp MUST compile to an application and MUST contain at least the following two functions:

• string InToPostflx(const string& infix)

double EvaluatePostflx(const  string &postFixEquation)

 

You may add as many other functions as you need to finish this project. In this project, you MAY use the Standard Template Library’s stack class. (Le. #include <stack» if you wish.