Project 03 Stack Project Solution



infix to postfix conversion and postfix evaluation with stacks


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


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.