Stacks
Stacks
- A stack is an ordered list in which insertions and deletions are made at one end called top
- Let stack S = (a0; a1 : : : ; an -1)
- a0 is known as bottom element
- an -1 is called top element
- Stack is also known Last-In-First-Out(LIFO) list
System Stack
- Program uses system stack when it calls a function
- Activation record or Stack frame is created by the program and is placed on top of the system stack
- Initially it contains a pointer to previous stack frame and return address
- Function to be executed is the one whose stack frame is on the top of the stack
- Local variables and parameters of the function is stored in the frame if the function calls another function
- Stack frame is removed on termination of the execution of the function
Stack Implementation
- One dimensional array: stack[MAX STACK SIZE]
- Bottom is at stack[0]
- Initially, top is set to -1 to denote empty stack
Stack CreateS(max_stack_size)::=
#define MAX_STACK_SIZE 100
typedef struct {
int key;
/* Other fields */
} element;
element stack[MAX_STACK_SIZE];
int top = -1;
Boolean IsEmpty(Stack) ::= top < 0 ;
Boolean IsFull(Stack) ::= top >= MAX_STACK_SIZE - 1
Stack Add(stack,item) ::=
void add(int *top, lement item)
{
if(*top >= MAX_STACK_SIZEe - 1)
{
stack_full();
return;
}
stack[++*top] = item;
}
Element Delete(stack) ::=
element delete(int *top)
{
if(*top == -1)
return stack_empty();
return stack[(*top)--];
}
Evaluation of Expressions
- An expression: x = a / b - c + d * e - a * c
- Precedence rules and Associativity
- Operator with highest precedence is evaluated first
- Parentheses overrides the precedence
- Innermost parentheses evaluated first
- Notations: Infix, Prefix, and Postfix
Postfix Notation
- Evaluation of expression in postfix notation is easier compared to infix notation
- Postfix notation is parentheses free
- Only one left to right scan is required
- Compiler generates postfix expression
- Each operator appears after its operands
Postfix Expression Evaluation
- Scan the posfix expression from left to right
- Place the operands on the stack till you find an operator
- Remove the required number of operands from the stack for the operator
- Evaluate the operator and put the result on the stack
- Continue this till you reach at the end of the expression
- Remove the answer from top of the stack
Infix to Postfix
- Fully parenthesize the expression
- Move all binary operators so that they replace their corresponding right parenthese
- Delete all parentheses
- Example:a/b - c + d * e - a * c
- ((((a/b) - c) + (d * e)) - a * c))
- ab/c - de * + ac * -
- Two pass required over expression
One Pass Infix to Postfix
- Order of operands are same both in infix and postfix
- Scan infix from left to right and pass the operands to the output expression as they are encountered
- The order in which operators are passed to the output depends on their precedence
- Higher precedence operator must be passed first
- Save the operators until their correct placement
Precedence of Left Parentheses
- Left parentheses has low precedence when it is on the stack and high precedence when it is unstacked
- Left parentheses are placed on the stack whenever it is found in the expresion
- It is unstacked only when its matching right parentheses is found
- Two types of precedence:
in-stack-precedence(isp) and
incoming-precedence(icp)