Transcript Stack implementation..

Data Structures: CSCI 362 – Stack Implementation
Stack Implementation
Stacks can be Implemented by:
Static Arrays
Fixed size
Good is size is known
Dr. Nazli Mollah
Dynamic Arrays
Flexible
Good if insertion and deletion is infrequent
Linked Lists
Flexible
Dynamic
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 – Stack Implementation
Stack Implementation
All versions have common operations (STL)
Void pop()
// pop & removes the top item from the stack
Void push(const T & item)
//pushes/ adds items on top of stack
Bool empty() const
//returns true if stack is empty
Int size() const
//returns number of items in stack
T&top()
//returns a reference to the top of the stack without removing it
Const T& top() const
// constant version of top
Destructors (for linked list and dynamic arrays)
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 – Stack Implementation
Stack Errors
Stack underflow
//condition resulting from trying to access an item from an empty stack
Stack overflow
//condition resulting from trying to push/ add an item onto a full stack
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 – Stack Implementation
Postfix Expression - Introduction


aka Reverse Polish Notation (RPN) after Polish mathematician Jan Lukasiewwicz
Calculators use this format extensively

Postfix Format: an operator is entered in the expression as soon as 2 operands are
available

e.g. 8 + (4* 12 + 5%2) / 3



contains:
Operands: (8, 4, 12, 5, 2, 3)
Operators: (+, *, %, /)
Parenthesis: subexpressions
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 – Stack Implementation
Infix vs. Postfix


Infix
Postfix

a+b*c

abc*+

(a + b) * c

ab+c*

(a*b+c)/d + e

ab*c+d/e+

a*b – c/d

ab*cd/-

a*b*c*d*e*f

ab*c*d*e*f*

(b*b-4*a*c)/(2*a)

bb*4a*c*-2a*/
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 – Stack Implementation
Postfix Evaluation Algorithm

Scan each term of the expression from left to right

Use a single stack to hold the operands

If a term is an operand, push it onto the stack

If a term is a binary operator, evaluate its result because its 2 operands are already
on stack on the 2 top positions

Pop the stack to retrieve the operands

Evaluate the expression

Push the result back onto the stack
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 – Stack Implementation
Postfix Evaluation Algorithm


Consider the expression 4 3 5 *+
Its postfix requires 7 steps
Step 1
Step 2
Step 3
4
3
4
5
3
4
Push 4
Push 3
Push 5
Dr. Nazli Mollah
Step 4
Step 5
• Read * operator
• Pop first 2 operands on stack
• Compute 5*3 = 15
Step 6
Step 7
• Read + operator
• Pop first 2 operands on stack
• Compute 15+4 = 19
15
4
19
Push 15
Push 19
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 – Stack Implementation
Postfix - Detecting Errors


Errors can occur during the evaluation of a postfix expression
At each step in the algorithm, the state of the stack allows us to identify
when an error occurs and the cause of the error
 e.g. 38+*9 ERROR
 Too many successive operators
 * is missing a second operand
 e.g. 98+7 ERROR
 Too many operands
 What to do with 7?
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 – Stack Implementation
Designing Postfix Evaluation Class for Implementation d_rpn.h
Class postfixEval
{
public:
postfix Eval();
// default constructor
// postfix expression is a NULL string
string getPostfixExp() const;
// access member function which enables a programmer to retrieve the current
expression
void setPostfixExp(const string& postfixExp);
// operation which takes a string argument containing the postfix expression
int evalaute();
// key member function which attempts to compute the value of the postfix expression
// if successful, it returns the value of the expression
// if the expression contains an error, the function throws the expressionError exception
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 – Stack Implementation
Designing Postfix Evaluation Class for Implementation d_rpn.h
private:
String postfixExpression;
// the characters in the string include operands, operators, and white space characters
// such as blanks, tabs
//These are scanned by the evaluate() function
Stack<int> operandStack;
// stack pf operands stored during operations and used by evaluate() function
void getOperands (int& left, int& right);
// pops the left and right operands from stack
// precondition: checks that the stack is not empty and has at least 2 entries before each pop operation
// an empty stack prior to pop() operations indicates that there are too many operators and the
// function throws an expressionError exception
Utility functions
to implement
algorithm
int compute (int left, int right, char op) const;
// evalautes an operations
// pushes result onto a stack
// for (/) and remainder (%) operators, compute() checks the RH operator to see if it is 0
// If it is 0, the function throws an exressionError exception with the message “Divide by 0”
// for the exponentail operator (^), compute() checks for (0,0) and throws an ExpressionError exception
Bool isOPerator (char ch) const;
// determines whether a character is one of the valid operators (+, -, *, /, %, ^)
};
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL