Description
Stack Project
infix to postfix conversion and postfix evaluation with stacks
CS2420
1 50 pts
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 ata time)
• display the infix equation
• create an InToPostfx() 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 postfix equation (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:
• have not used any code other than my own (or that in the textbook) for this project. understand that any violation of this
disclaimer will result in a O for the project.
Correct Output
infix: 4
postfix: 4
answer: 4
infix: 5 +7
postfix: 5 7 +
answer: 12
infix: 7 *5
postfix: 7 5 *
answer: 35
infix: (5-3)
postfix: 5 3 –
answer: 2
infix: 5/5
postfix: 5 5 /
answer: 1
infix: 8*5+3
postfix: 8 5 * 3 +
answer: 43
infix:
postfix: 8 5 3 + *
answer: 64
infix: 8+3*5-7
postfix: 83 5 * +7 –
answer: 16
infix:
6-
• -11
postfix:
answer.
83+5
infix: ((8+3)*(2-7))
postfix:
answer :
83+2
-55
infix: ((8+3)*2)-7
postfix: 8 3 + 2 * 7
answer: 15
infix:
postfix: 8 5 * 3
2
answer: 20
infix:
postfix: 8 5
answer: 21
infix:
postfix: 7 9
answer: 39
Evaluating a Postfix Expression
Initialize a stack of doubles
7
5
i f (next i aput is a nurnber)
Read the next input and push onto the stack
else
Read the next character, which is an operator symbol
use Lop and pcp Lo get the Lwo num_bezs off Che Lop of the stack
Combine these two numbers With the operation (using the second number
popped as the left operand)
Push the result onto the Stack
while (there is more oe the expression to read)
3. AL this point, the stack contains one nurnher which is the result of Zhe expression
Infix to Postfix Pseudo Code
initialize stack tc hcLd operaticn symbols and parenthesis
. do
if (the next input is a left parenthesis)
Read the left parenthesis and push onto the stack
else if (the next input is a number cr operand)
Read the operand (or number) and WE ite it to Ehe output
else if (the next input is
While ( stack not
stack ‘s
stack ‘s
one of the operation symbols)
empty AND
top is not left parenthesis AND
top is an operation With equal or higher precedence
than the next input symbol)
print the stack’s top
pop the stack’s top
push the next ope:ation symbol onto the stack
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 syrnbol on stack and pop s Lack
pop and discard the last left parenthesis
While (there is more the expression to read)
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 InToPostfix(const string& infix)
• double EvaJuatePostfix(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. (i.e. *include if you wish.
