: Data Structures & Algorithm Analysis
• Chapter 5: Stack
1
Stack
− A list of data items processed via a last-in
first-out (LIFO) scheduling strategy is called
a stack.
− It is a (linked) list in which entries are
added to and removed from one
distinguished end, called top.
2
Stack
3
Stack Implementation
4
Array Implementation of Stack
Left as an exercise.
5
Pointer implementation of Stack
Node Construction/Declaration:
struct node {
<appropriate_type> data;
node * next;
};
Stack Construction:
node * top;
6
Create Stack
create(node* & top) {
top = NULL;
}
7
Is Stack Empty
int isEmpty(node * top) {
if (top == NULL) return 1;
else return 0;
}
8
Is Stack Full
It does not make sense in pointer implementation.
9
Push on to the Stack
10
Push Item on to the Stack
void push(node* & top, <appr_type> item) {
node * p;
p = new nothrow node;
if (p!=NULL) {
p->data = item;
p->next = top;
top = p;
}
} 11
Pop from the Stack
12
Remove the top and return it into item
void pop(node* & top, <appr_type>& item) {
node * p;
// if !isEmpty(top) – this can be checked by the calling module
item = top->data;
p = top;
top = top->next;
delete(p);
}
13
Copy the top and return it into item
without removing it
void onTop(node * top, <appr_type> &
item) {
// if !isEmpty(top) – this can be checked by
the calling module
item = top->data;
}
14
Stack Operations Analysis
All operations are the order of a constant, O(1).
15
Exercise: Decimal to Binary
void decimalToBinary (int num){
node * top;
int bin;
create(top); //Create stack
while (num > 0){
bin = num % 2;
push(top, bin); //push onto the stack
num = num / 2;
}
while (!isEmpty(top)){ //
pop(top, bin);
cout << bin;
}
}
16
Stack Application: Compiler
Compilers use an algorithm called operator precedence parsing to
convert an infix expression to a postfix expression in order to
evaluate the infix expression. The postfix form represents a natural
way to evaluate because precedence rules are not required.
A postfix expression is a series of operators and operands. A
postfix machine is used to evaluate a postfix expression as
follows:
• When an operand is seen, push it on to the stack
• When an operator is seen, pop the appropriate number of
operands, evaluate the operator, and then push the result
onto the stack.
• When the complete postfix expression is evaluated, the result
should be a single item on the stack that represents the answer.
17
Exercise: Evaluate Postfix Expression
1. 3 2 5 ^ * 1 -
2. 1 2 - 4 5 ^ 3 * 6 * 7 2 2 ^ ^ / -
18
Infix To Postfix Conversion
• Operands: Immediately output.
• Close parenthesis: Pop stack symbols until an
open parenthesis appears.
• Operator: Pop all stack symbols until a symbol of
lower precedence or a right-associative symbol of
equal precedence appears. Then push the
operator.
• End of input: Pop all remaining stack symbols.
19
Example: Associativity
Infix Expression Postfix expression Associativity
2+3+4 2 3 + 4 Left-associative:
Input + is lower
than stack +.
2^3^4 2 3 4 ^ ^ Right-associative:
Input ^ is higher
than stack ^.
20
Exercise: Infix To Postfix Conversion
1. 3 * 2 ^ 5 - 1
2. 1 - 2 ^ 3 ^ 3 - ( 4 + 5 * 5 ) * 7
3. ( 1 + 2 ) * 3 - ( 4 ^ ( 5 – 6 ) )
21
Exercise:
1. Write a C++ function that takes a C++ source code file
and checks whether symbols (parentheses, braces, and
brackets) are balanced. Note we should not consider a
parenthesis as a symbol if it occurs inside a comment,
string constant, or character constant. The function
should report for the calling module the line number and
the position of the offending symbol.
2. Using the technique to implement compiler, write a
simple calculator that evaluate infix expressions that
supports addition, subtraction, multiplication, division,
and exponentiation. Assume the values as double data
type.
22