|
S t a c k |
Stack is called last in first out (LIFO).
Example 1 : Opening and Closing parenthesis are equal.
Example 2 : Recursive calls
Stack Operations
(1) Push = add item on top of the stack , increment the stack by 1
(2) Pop = remove item from the top of the stack , decrement the stack by 1.
(3) Get Top Value
(4) Isfull
(5) Isempty
(6) Get Top index
Mathematical Expressions and the Stack:
Operand : A,B ..
Operator : + ,- , / ,*
Examples
infix form A + B
prefix form +AB
postfix form AB+
Advantage : elimination of the parenthesis to represent the order of evaluation used with infix expression .
Example1:
infix A+(B*C)
prefix form A+(*BC) (Convert the multiplication )
+A(*BC) (Convert the addition )
+A*BC ( prefix form )
postfix form ABC*+
Example2
infix (A+B)*C
prefix *+ABC
postfix AB+C*
The stack ADT can be used to convert an infix expression to postfix and evaluate it after that .
The operation with higher precedence are converted first and after a portion of the expression is converted , it is to be treated as a single operand.
(1) Push operands into the stack
(2) If the character being read is operator ,applies it to the top 2 operands of the stack by poping them .
(3) Push the result of the operation onto the stack.
The final result will be the value at the top of the stack.
A pseudocode algorithm that evaluates postfix expressions
for ( each character Ch in the string)
{
if (Ch is an operator named Op)
{
Oprnd2 = top of stack
Pop the stack
Oprnd1 = top of stack
Pop the stack
Result = Oprnd1 Op oprnd2
Push Result onto stack
}
else // Ch is operand
Push Ch onto stack
}
A pseudocode algorithm that converts an infix expression to postfix form (we use the PE string to store the postfix form)
for ( each character Ch in the infix expression )
{
switch (Ch)
{
case operand : append C to PE
case ' ( ' : push C to the stack
case ' ) ' :
while ( top of the stack not ' ( ' ) )
{
append top of the stack to PE
pop the stack
}
pop the stack
case operator :
while ( ( stack is not empty) and
( top of the stack is not ' ( ' ) and
( precedence top of stack >=precedence C))
{
append top of the stack to PE
pop the stack
}
push C to the stack
} // end switch
while ( stack not empty )
{
appeand top of stack to PE
pop the stack
}