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
- Initialize a stack of doubles
- 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);
- At this point, the stack contains one number which is the result of the expression
Infix to Postfix Pseudo Code
- initialize stack to hold operation symbols and parenthesis
- 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)
- 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.