Using stacks, write an implementation that contains classes to evaluate a Prefix

Question

Using stacks, write an implementation that contains classes to evaluate a Prefix expression. Your implementation should include:

- A PreFixEvaluator class.

- A PreFixConsole Class.

- Any exception classes you need to write

You should model your classes after the classes in the text used for Postfix Evaluation, pages 137 – 140.

You should use the algorithm given in the Prefix Notation and Expressions Handout.

My advice is to first assume a valid prefix expression and get your implementation to work with that assumption. Next, go back and add exception handling and test with invalid prefix expressions. Your final implementation should return the result of a valid prefix expression or output an error message indicating what is wrong with the prefix expression.

You can use either the ArrayBoundedStack class or the LinkedStack class in your implementation. (DO NOT JUST REVERSE THE PREFIX EXPRESSION TO FORM A POSTFIX EXPRESION AND EVALUATE USING THE CODE IN THE BOOK. THIS WILL RESULT IN 0 CREDIT.)

Explanation / Answer

#include<iostream>
#include<cctype>
#include<stack>
using namespace std;

// returns the value when a specific operator
// operates on two operands
int eval(int op1, int op2, char operate) {
switch (operate) {
case '*': return op2 * op1;
case '/': return op2 / op1;
case '+': return op2 + op1;
case '-': return op2 - op1;
default : return 0;
}
}

// evaluates the postfix operation
// this module neither supports multiple digit integers
// nor looks for valid expression
// However it can be easily modified and some additional
// code can be added to overcome the above mentioned limitations
// it's a simple function which implements the basic logic to
// evaluate postfix operations using stack
int evalPostfix(char postfix[], int size) {
stack<int> s;
int i = 0;
char ch;
int val;
while (i < size) {
ch = postfix[i];
if (isdigit(ch)) {
// we saw an operand
// push the digit onto stack
s.push(ch-'0');
}
else {
// we saw an operator
// pop off the top two operands from the
// stack and evalute them using the current
// operator
int op1 = s.top();
s.pop();
int op2 = s.top();

s.pop();
val = eval(op1, op2, ch);
// push the value obtained after evaluating
// onto the stack
s.push(val);
}
i++;
}
return val;
}

// main
int main() {
char postfix[] = {'5','6','8','+','*','2','/'};
int size = sizeof(postfix);
int val = evalPostfix(postfix, size);
cout<<" Expression evaluates to "<<val;
cout<<endl;
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.