4 Stacks – Introduction to Data Structures in C

Chapter 4

Stacks

Chapter Outline

4.1 INTRODUCTION

In this chapter, we will study one of the most important simple data structures ‘stack’. Stack is an important tool in programming languages. Stack is one of the most essential linear data structures. Implementation of most of the system programs is based on stack data structure. We can insert or delete an element from a list, which takes place from one end. The insertion of element onto the stack is called as “push” and deletion operation is called “pop”, i.e. when an item is added to the stack the operation is called “push” and when it is removed the operation is called “pop. Due to the push operation from one end, elements are added to the stack, the stack is also known as pushdown list. The most and least reachable elements in the stack are respectively known as the “top” and “bottom” of the stack. A stack is an arranged collection of elements into which new elements can be inserted or from which existing new elements can be deleted at one end. Stack is a set of elements in a last-in-first-out technique. As per Fig. 4.1 the last item pushed onto the stack is always the first to be removed from the stack. The end of the stack from where the insertion or deletion operation is carried out is called top. In Fig. 4.1(a) a stack of numbers is shown.

Figure 4.1 (a) Stack

Figure 4.1 (b) A pot with plates

As shown in Fig. 4.1(a) the stack is based on the rule last-in-first-out. The element appended lastly is deleted first. If we want to delete element 3 it is necessary to delete the top elements 5 and 4 first.

In Fig. 4.1(b), you can see a pot containing plates kept one above the other. Plates can be inserted or removed from the top. The top plate can be removed first in case pop operation is carried out, otherwise plates are to be added on the top. In other words, the removal operation has to be carried out from the top. Thus, placing or removing takes place from top, i.e. from the same end.

Figure 4.2 Working of stack

As shown in the first half portion of Fig. 4.2, first integer 1 is inserted and then 2,3,4 and 5 are pushed on to the stack. In the second half portion of the same figure, the elements are deleted (pop) one by one from the top. The elements are deleted in the order from 5 to 1. The insertion and deletion operation is carried out at one end (top). Hence, the recently inserted element is deleted first. If we want to delete a particular element of the stack, it is necessary to delete all the elements present above that element. It is not possible to delete element 2 without deleting elements 5,4 and 3. The stack expands or shrinks with the passage of time. In the above example, the stack initially expands until element 5 is inserted and then shrinks after removal of elements. There is no higher limit on the number of elements to be inserted in the stack. The total capacity of stack depends on memory of the computer.

In practical life, we come across many examples based on the principle of stack.

Figure 4.3 Stack of books

Fig. 4.3 illustrates the stack of books that we keep in the order. Whenever we want to remove a book the removal operation is made from the top or new books can be added at the top.

Another example of stack that can be cited is a railway system for shunting the trains. Figure 4.4 shows a picture of a railway system. The incoming trains arrive in a sequence in the stack. The last entered train in the stack leaves first and it will be placed at first on the outgoing track.

Figure 4.4 A Railway Track

4.2 STACK-RELATED TERMS

Stack Stack is a memory portion, which is used for storing the elements. The elements are stored based on the principle of last-in-first-out. In the stack the elements are kept one above the other and its size is based on the memory.

Top The top of the pointer points to the top element in the stack. The top of the stack indicates its door from where elements are entered or deleted. The stack top is used to verify stack’s current position, i.e. underflow, overflow, etc. The top has value 0 when the stack is empty. Some programmers assign −1 to the top as initial value. This is because when the element is added, the top is incremented and it would become zero. The stack is generally implemented with the help of an array. In an array, counting of elements begins from 0 onwards. Hence, on the similar grounds stack top also begins from 0 and it is convenient to assign −1 to top as initial value.

Stack Underflow When there is no element in the stack or stack holds elements less than its capacity, the status of stack is known as stack underflow. In this situation, the top is present at the bottom of the stack. When an element is pushed, it will be the first element of the stack and top will be moved one step up.

Stack Overflow When the stack contains equal number of elements as per its capacity and no more elements can be added, the status of stack is known as stack overflow. In such a position, the top rests at the highest position.

Storage A function containing local variables and constants are stored in stack. Only global variables are stored in a stack frame.

Stack Frames This data structure holds all formal arguments; return address and local variables on the stack at the time when function is invoked.

4.2.1 Representation of Stack

The stack is represented in various ways. The stack can be shown as completely empty or fully filled or filled with few elements. When stack has no element, it is called empty stack which is shown in Fig. 4.5(a). The stack with completely filled elements is shown in the Fig. 4.5 (b) and no further elements can be inserted.

A top pointer maintains track of the top elements as shown in Fig. 4.5(c). For empty stack, the top value is zero. When stack has one element the value of top is one. Whenever an element is inserted (push operation) in the stack the value of pointer top is incremented by one. In the same manner, the value of pointer is reduced when an element is deleted from the stack (pop operation). The push operation can be applied to any stack, but before applying pop operation on the stack, it is necessary to make sure that the stack is not empty. If a pop operation is performed on empty stack, it results in underflow.

Figure 4.5 Representation of stack

Stack is very helpful in every ordered and chronological processing of functions. The most useful application of stack is in recursion (explained in previous chapter). It saves memory space. The mechanism of stack last-in-first-out (LIFO) is commonly useful in applications such as manufacturing and accounting calculations. It is a well-known accounting concept.

4.3 STACK IMPLEMENTATION

The stack implementation can be done in the following two ways:

4.3.1 Static Implementation

Static implementation can be achieved using arrays. Though, it is a very simple method, it has few limitations. Once a size of an array is declared, its size cannot be modified during program execution. It is also inefficient for utilization of memory. While declaration of an array, memory is allocated which is equal to array size. The vacant space of stack (array) also occupies memory space. In both cases, if we store less argument than declared, memory is wasted and if we want to store more elements than declared, array cannot be expanded. It is suitable only when we exactly know the number of elements to be stored.

4.3.2 Dynamic Implementation

Pointers can also be used for implementation of stack. The linked list is an example of this implementation. The limitations noticed in static implementation can be removed using dynamic implementation. The dynamic implementation is achieved using pointers. Using pointer implementation at run time there is no restriction on the number of elements. The stack may be expandable. The memory is efficiently utilized with pointers. Memory is allocated only after element is pushed to the stack. Both the above implementations are illustrated with suitable examples in the next section.

4.4 OPERATION ON STACK

The following fundamental operations on stack can be carried out through static implementation called array implementation. Operation on stack is also possible with the pointers, which is called dynamic implementation. We will perform the following operations on the stack:

  1. Creating a stack
  2. Checking stack—either empty or full
  3. Initializing a stack
  4. Insert (push) an element in the stack
  5. Delete (pop) an element from the stack
  6. Access the top element
  7. Display elements of stack
  8. Status: to identify present position of stack.

Some terms relevant to the stack operations are narrated below.

Push The procedure of inserting a new element to the top of the stack is known as push operation. After every push operation, the top is incremented by one. When the array is full (if static implementation is applied) the status of stack is full and this condition is called as stack overflow. In such a case, no further element can be inserted. After every push operation, the new element rests at the top. Fig. 4.6(a) shows the push operation.

Figure 4.6 (a) Push operation with stack

Pop The procedure of removing element from the top of the stack is called as pop operation. After every pop operation, the top is decremented by one. If there is no element in the stack, it is called as empty stack or stack underflow. In such a case, pop operation cannot be applied. Fig. 4.6(b) illustrates the pop operation.

Figure 4.6 (b) Pop operation with stack

The stack can be supposed as a one-dimensional array. The various operations listed above can be carried out with one-dimensional array. The following programs explain the operations listed above.

As mentioned earlier, one-dimensional array can be used as stack. We can add elements in the one-dimensional array. Using if statement we can check whether the stack is empty or full. Consider the following programs.

Example 4.1

Write a program to explain working of stack using array implementation.

Solution

# include <stdio.h>

# include <conio.h>

# include <process.h>

main ()

{

int j,stack[5]={0};

int p=0;

clrscr();

printf ("Enter Elements, put zero to exit: \n");

    while (1)

    {

    scanf ("%d",&stack[p]);

    if (stack[p]==0)

    {

        printf ("\n By choice terminated: ");

        exit(0);

    }

    p++;

    if (p>4)

    {

        printf ("Stack is full \n");

        break;

    }

    else

    printf ("Stack is empty\n");

}

printf ("\n Elements of stack are: ");

for (j=0;j<5;j++)

printf (" %d ",stack[j]);

}

OUTPUT

Enter Elements, put zero to exit:

4

Stack is empty

2

Stack is empty

6

Stack is empty

8

Stack is empty

3

Stack is full

Elements of stack are: 4 2 6 8 3

Explanation In this program an array stack [5] is declared. Using while loop, elements are read through the keyboard and placed in an array. The value of variable p is initially zero. The variable p increases in every iteration. The variable p acts as a top of stack. The if statement checks the value of p. If the value of p is greater than four it means that, the stack is full and no more elements can be added. When value of p is less than four it means more elements can be inserted in the stack. The for loop and printf statements display the array elements. In stack random insertion or deletion of element is not possible (Though in array it is possible, but here keep in mind that we are treating an array as a stack. Hence, we have to follow the restrictions that exist in stack implementation). If we want to delete any particular element, we have to delete every element present before that element. Program 4.2 explains deletion of elements.

Example 4.2

Write a program to store elements in the stack. Delete the specified element.

Solution

# include <stdio.h>

# include <conio.h>

main ()

{

int j,stack[5];

int p=0;

clrscr();

printf ("Enter Elements put zero to exit: \n");

    while (1)

    {

    scanf ("%d",&stack[p]);

    if (stack[p]==0)

    break;

    p++;

        if (p>4)

        {

        printf ("Stack is full \n"); break;

    }

}

printf ("\nStack elements are: ");

for (j=0;j<5;j++)

printf (" %d ",stack[j]);

printf ("\n Enter element position to delete: ");

scanf ("%d",&p);

p−−;

for (j=4j>=p;j−−)

stack[j]=NULL;

printf ("Stack elements are: ");

for (j=0;j<5;j++)

printf (" %d ",stack[j]);

getch();

}

OUTPUT

Enter Elements put zero to exit:

8

9

4

5

3

Stack is full

Stack elements are: 8 9 4 5 3

Enter element position to delete: 3

Stack elements are: 8 9 0 0 0

Explanation In this program, as usual, elements are entered and stored in the stack. The element number that is to be deleted from the stack will be entered from the keyboard. Recall that in a stack, before deleting any element, it is compulsory to delete all elements before that element. In this program, the elements before a target element are replaced with value NULL (0). The elements after target element are kept as it is. Recall that when an element is inserted in the stack the operation is called “push.” When an element is deleted from the stack the operation is “pop”. Program 4.3 explains the push and pop operations.

Example 4.3

Write a simple program to demonstrate push () and pop () operations

Solution

# include <stdio.h>

# include <conio.h>

static int stack[10], top=−1;

main ()

{

void push(int);

void pop(void);

void show(void);

clrscr();

printf ("\n\n push operation: ");

push(5);

show();

push(8);

show();

push(9);

show();

printf ("\n\n pop operation: ");

show();

pop();

show();

pop();

show();

}

void push (int j)

{

top++;

stack[top]=j;

}

void pop ()

{

stack[top]=0;

top−−;

}

void show ()

{

int j;

printf ("\n stack elements are: ");

for (j=0;j<10;j++)

    stack[j]!=0 ? printf (" %d ",stack[j]): printf("");

}

OUTPUT

push operation:

stack elements are: 5

stack elements are: 5 8

stack elements are: 5 8 9

pop operation:

stack elements are: 5 8 9

stack elements are: 5 8

Stack elements are: 5

Explanation In this program stack [] and top variables are declared as static. The variable top is initialized with −1. It is not necessary to declare top as static. The push () operation inserts an element into the stack. The next element pushed is displayed after the first element and so on. The pop () operation removes the element from the stack. The last element inserted is firstly deleted. In the output the element 9 is deleted first as it is entered at last. Then, element 8 is removed. At last, the stack holds only one element having number 5.

Example 4.4

Write a program to perform pop and push operation on the stack.

Solution

# include <stdio.h>

# include <conio.h>

# include <process.h>

int ch,p,z=6,top=0,stack[7],c;

main()

{

void make ();

void push();

void pop();

void show();

clrscr();

while(ch<5)

{

    printf("\n1] Stack creation");

    printf("\n2] Insert element");

    printf("\n3] Delete Element");

    printf("\n4] Display Element");

    printf("\n5] Exit\n");

    printf("Enter the choice:- ");

    scanf("%d",&ch);

    switch(ch)

    {

        case 1: make();

        continue;

        case 2: push();

        continue;

        case 3: pop();

        continue;

        case 4: show ();

        continue;

        default: exit(0);

    }

}

}

void make ()

{

printf("\n Enter number of elements in the stack (<7): ");

scanf("%d",&c);

for (top=0;top<c;++top)

{

    printf("Enter Element[%d]:- ",top);

    scanf("%d",&stack[top]);

}

}

void push ()

{

if (top>=z)

{

    printf("\n Stack is full ");

    getch();

}

else

{

    printf("\n Enter number to be pushed:- ");

    scanf("%d",&stack[top]);

    top++;

}

}

void pop ()

{

if (top<=0)

{

    printf("\nThe stack is empty ");

    getch();

}

else

top−−;

}

void show ()

{

for (p=top−1;p>=0;−−p)

printf(" %d ",stack[p]);

}

OUTPUT

1] Stack creation

2] Insert element

3] Delete Element

4] Display Element

5] Exit

1

Enter number of elements in the stack (<7): 4

Enter Elements: 1 2 3 4

1] Stack creation

2] Insert element

3] Delete Element

4] Display Element

5] Exit

4

0 4 3 2 1

1] Stack creation

2] Insert element

3] Delete Element

4] Display Element

5] Exit

Explanation In this program few variables and array stack [] are declared globally so that every program can access them. Functions make (), push (), void pop () and void show () are defined. When the user selects first option, the user is prompted to enter the number of elements. Immediately followed by this, the user has to enter choice by entering the integer number. These integers are stored in the array stack []. The user can see the stack elements by selecting fourth choice on the screen. When delete operation is performed, the top element of the stack is deleted. The user can confirm this operation by selecting display element operation. When insert operation is selected, the entered element is inserted at the top of the stack. The global variable top keeps track of the total number of elements present in the stack.

Example 4.5

Write a program to create a class stack and define member function push () and pop ().

Solution

# include <stdio.h>

# include <conio.h>

int stacks[10];

int top;

main ()

{

void show(void);

void push (int j);

void pop ();

int n,j;

top=−1;

stacks[10]=NULL;

clrscr();

printf("\nInsert four element in stack");

printf("\npush operation: ");

push(2);

push(5);

push(8);

push(3);

show();

printf("\n\nDeleting two elements from the stack");

printf("\npop operation: ");

pop();

pop();

show();

}

void push (int j)

{

  top++;

  stacks[top]=j;

  }

void pop ()

{

stacks[top]=0;

top−−;

}

void show ()

{

int j;

for ( j=0;j<=top;j++)

printf(" %d",stacks[j]);

}

OUTPUT

Insert four element in stack

push operation: 2 5 8 3

Deleting two elements from the stack

pop operation: 2 5

Explanation In this program an array stack is declared. Both two array variables, stacks [10] and top, are static and they are initialized. Three-functions push (), pop () and show () are defined. Invoking push () function elements are pushed. The pop () operation removes the elements. The show () function displays the elements of stack.

4.5 POINTERS AND STACK

We are already aware that array name itself is a pointer. Pointer implementation of a stack carried out is similar to array implementation. Stack is particularly straightforward version of linked lists. The implementation of array-like elements can be done using pointer. Like array, elements can be stored in successive memory location using pointer. First, we learn a simple program to create stack using pointer instead of array.

Example 4.6

Write a program to create an array-like list of integers using pointer.

Solution

# include <stdio.h>

# include <conio.h>

main ()

{

int *p,j,e;

clrscr();

printf ("\n Enter five Integers: ");

for (e=4;e>=0;e−−)

scanf ("%d",(p+e));

for (e=0;e<5;e++)

printf ("%d ",*(p+e));

}

OUTPUT

Enter five Integers: 4 5 8 7 5

5 7 8 5 4

Explanation In this program a pointer *p is declared. The first for loop is used to read numbers in association with scanf () statement. The value of variable e is added to the address of pointer p, so that successive locations are accessed and the number is placed in the location. For displaying elements, same logic is applied.

Example 4.7

Write a program to implement stack operation push and pop with pointer.

Solution

# include <stdio.h>

# include <conio.h>

# include <stdlib.h>

struct stack

{

int num;

struct stack *next;

    } *T=0;

    typedef struct stack it;

    void push ();

    int pop();

    void show ();

    main ()

    {

    char chr;

    int opt,no;

        do

        {

        clrscr();

        printf ("\n 1: push ");

        printf ("\n 2: pop ");

        printf ("\n 3: show ");

        printf ("\n >3: exit");

        printf ("\n Enter your option: ");

        scanf ("%d",&opt);

switch(opt)

{

    case 1: push (); break;

    case 2: no = pop ();

    printf ("\n The delete number was %d ", no);

    break;

    case 3: show (); break;

    default: printf ("\n Good Bye ");

    exit(0);

}

    printf ("\n Continue (y/n )" );

    fflush(stdin);

    chr=getche();

} while (chr=='Y' || chr=='y');

}

void push()

{

it *node;

node=(it*) malloc(sizeof(it));

printf ("\n Enter the number ");

scanf ("%d",&node->num);

node->next=T;

T=node;

}

int pop ()

{

it *temp;

temp=T;

    if (T==NULL)

    {

    puts ("\n Stack underflow ");

    getch();

    exit(0);

}

else

{

    T=T->next;

    free(temp);

}

return (temp->num);

}

void show ()

{

it *tmp;

tmp=T;

while (tmp->next !=NULL)

{

    printf (" %d ", tmp->num);

    tmp=tmp->next;

}

printf (" %d ", tmp->num);

}

OUTPUT

1: push

2: pop

3: show

>3: exit

Enter your option: 3

7 2

Continue (y/n)

Explanation In this program the structure stack is defined with variables num and a pointer variable *next of stack (itself) type. Later *T a pointer is declared. The prototype declaration of pop (), push () and show () is done. The user is asked to entered option and the entered option number is passed to switch () case structure to execute the anticipated option. The user has to press ‘y’ to continue the program, else if other alphabet is entered, the program will terminate.

In the push () function, it is a custom data type created with typedef statement. The variable *node is variable of type structure stack. The malloc () function is used to allocate memory to *node pointer equal to the size of structure variable. The element entered immediately by the user is stored in allocated memory. The number is stored in the num variable and the T is assigned to node->next.

In pop () function, another variable tmp is declared. If the T is NULL, i.e. the stack is still underflow and we can continue the push operation. Otherwise, the free function de-allocates the memory of last element pointed by next. When the memory is de-allocated the element also is destroyed. The show () function is used to print the elements. This is achieved using while loop.

4.6 REPRESENTATION OF ARITHMETIC EXPRESSIONS

An arithmetic expression contains operators and operands. Variables and constants are operands. The operators are of various kinds such as arithmetic binary, unary for example, + (addition), − (subtraction), *(multiplication), / (division) and % (modular division). The following Table 4.1 describes types of operators and the Fig. 4.7 shows the numbers of operators.

Figure 4.7 Types of operators

Table 4.1 Operators and its symbolic representation

Types of operators Symbolic representation
Arithmetic operators +,−, *, / and %
Relational operators >, <, =, ==, >=, <= and !=
Logical operators &&, ||, !
Increment/decrement operators ++, −−
Assignment operators =
Bitwise operators &, |, ^, ≫, ≪, ~
Special operators , ( comma)
Conditional operators ?:

The precedence of operator also plays an important role in expression solving. The precedence of operators is given in Table 4.2.

We have already studied the different stack operations. Now, we will study how stack can be useful in problem solving. Consider a mathematical expression.

5 − ((A * ((B + K)/ (U−4))+K) / 8 (8−4.3))

The common mistake, which can be made frequently by the programmer, is unbalance of parenthesis. For correct representation of mathematical expression, the following precautions must be taken:

 

Table 4.2 Precedence of operators

Operators Precedence Associativity
+ (unary), − (unary), NOT
6
^ (Exponentiation)
6
Right to left
* ( multiplication ), / ( division)
5
Left to right
+ (addition ), − ( subtraction )
4
Left to right
<,<=,+,<,>,>=
3
Left to right
  1. There must be equal number of left and right parenthesis.
  2. Each left parenthesis must be balanced by right parenthesis.

The expressions ((x+y) and ) x+y (−u are wrong.

Thus, by using stack such a problem can be solved. Assume the left parenthesis as opening scope and right parenthesis as end of scope. Some time the expression contains nested parenthesis, hence various scopes are opened but not closed. Count the number of opening parenthesis from beginning of expression to end. If the number of opening parenthesis is equal to closing parenthesis it means no scope is left open. The number of opening and closing parenthesis is found same. If the parenthesis count in the expression is negative, it means a right parenthesis is found, but no left parenthesis of its pair is defined.

( ( x + y )

1 2 1

In the above example, when opening parenthesis is encountered, counter is incremented and when closing parenthesis is encountered, counter is decremented.

) x + y ( − z

−1 0

In the above example, when the first closing parenthesis is encountered, the counter is decremented.

5 − ( ( A * ( ( B + K ) / ( U − 4 ) ) + K ) / 8 ( 8−4.3 ) )

0 1 2 3 4 3 4 3 2 1 2 1 0

In the above example the opening and closing parenthesis are balanced.

Example 4.8

Write a program to count opening and closing parenthesis and test the expression having balanced parenthesis or not.

Solution

# include <stdio.h>

# include <conio.h>

int stack[10];

int top=9;

main ()

{

int c=0,p=0;

char exp[]="(p+(q−(m+n))*j−((x+y))) / (j−(k−(−k(l−n))))";

clrscr();

printf ("\n%s\n",exp);

while (exp[c]!='\0')

{

switch(exp[c])

{

    case '{':

    case '(':

    case '[':

    p++;

    printf ("%d",p);

    break;

    case '}':

    case ')':

    case ']':

    p−−;

    printf ("%d",p);

    break;

    default:

    printf ("%d",p);

}

c++;

}

}

OUTPUT

(p+(q−(m+n))*j−((x+y))) / (j−(k−(−k(l−n))))

1112223333211112333321000011122233344443210

Explanation In this program whatever we discussed in last paragraph are applied practically. When an opening parenthesis is found counter p is incremented and when closing parenthesis is found counter is decremented. The counter value is displayed in the output. In the above program if expressions “)p+(p+q)” are entered the output will be -1-1-10000-1. So far, we used only one type of parenthesis, i.e. (). In expression other type of parenthesis like {}, [] can be used. In such case, it is necessary to keep record of not only number of opening and closing braces but also their type. The stack can be used in such application.

When an opening parenthesis is found it is pushed into the stack. When a closing parenthesis is found the pop operation is carried and it is tested, the deleted parenthesis corresponds to the opening parenthesis. If the opening and closing parentheses match, the program will continue otherwise the entered string is invalid. When the end of string is found, the stack must be empty. If the stack contains elements, it means there is opening parenthesis that had not been closed.

Consider the following expression.

{p+(q−[m+n])*j−[(x+y)]} / (j−(k−(k−[l−n])))

Figure 4.8 Different views of stack

As soon as the opening parenthesis of types (, {or [is encountered it is pushed on to the stack. We can see this in the figure 4.8 (a), (b) and (c). When a closing parenthesis is found the top element of the stack is popped. Only when the encountered closing bracket and the top element of the stack matching, i.e. {}, () and []. We can observe this in figure 4.8 (d) and (e). In Fig. 4.8(g) the stack is empty because there expression up to {p+(q−[m+n])*j−[(x+y)]} is read. The number of opening and closing brackets are same. Hence, the expression is correct. When an element remains in the stack, it means the expression is wrong and parentheses are not properly closed. Again, the expression is read and same push and pop procedure is applied. The remaining expression (j−(k−(k−[l−n]))) is read.

Example 4.9

Write a program to compare opening and closing brackets.

Solution

# include <stdio.h>

# include <conio.h>

char stack[15];

int t=14;

main ()

{

void pop(void);

void show (void);

void push (char);

char exp[20];

int j=0,b=0;

clrscr();

printf ("\n Enter an Expression: ");

scanf ("%s",exp);

while (exp[j]!='\0')

{

    switch(exp[j])

    {

        case '{':

        case '(':

        case '[':

        push (exp[j]);

        show();

        b++;

        break;

    case '}':

    if (stack[t+1]=='{')

    {

        pop();

        b−−;

        }

else

printf ("\n Error in expression");

break;

case ')':

if (stack[t+1]=='(')

{

    pop();

    b−−;

}

else

printf ("\n No matching opening and closing brackets");

break;

case ']':

if (stack[t+1]=='[')

{

    pop();

    b−−;

}

else

    printf ("\n No matching opening and closing brackets");

break;

}

j++;

}

if (b==0)

printf ("\n Expression is correct");

else

printf ("\n %d closing brackets are not closed",b);

show();

}

void push ( char c)

{

stack[t]=c;

t−−;

}

void pop ()

{

t++;

stack[t]=NULL;

}

void show ()

{

int k;

printf ("\n");

for (k=0;k<=14;k++)

printf ("%c",stack[k]);

}

OUTPUT

1)

Enter an Expression: {(a+b)}

{

({

Expression is correct

2)

Enter an Expression: {(a+b}

{

({

Error in expression

2 closing brackets are not closed

({

Explanation An entered expression by the user is stored in the array exp []. Using while loop the entire string (expression) is scanned. The switch () case structure within while loop is used to check different conditions. If any opening bracket comes across, it is pushed on to the stack by invoking push () function, i.e. the meet opening bracket is stored in the array stack using push () function.

We know that in any valid expression, the first opened parenthesis is closed lastly and the lastly opened parenthesis is closed first, i.e. the parenthesis arrangement is like stack mechanism first-in-last-out. The encountered opening parenthesis are pushed onto the stack. When closing parenthesis of same type is found the item is popped from the stack. Thus, matching pairs of parenthesis are checked. If no match is found, the error will be displayed. In case an opening parenthesis does not have closing parenthesis, the message displayed will be “Error in expression”.

4.7 INFIX, PREFIX AND POSTFIX NOTATIONS

This topic illustrates an important application of different kinds of stacks, various operations defined upon them and compilation of infix expressions. Stack has various real life applications. Stack is very useful to keep sequence of processing. In solving arithmetic expressions, stacks are used. Stacks are used to convert bases of numbers. In a large program, various functions are invoked by the main () function; all these functions are stacked in the memory. Most of the calculators work on stack mechanism.

Arithmetic expressions can be defined in three kinds of notation: infix, prefix and postfix. The prefixes in, pre and post indicate the relative location of the operator with two operands.

Infix Notation Expressions are generally expressed in infix notation with binary operator between the operands. The binary operator means the operator requires two operands such as +, *, / and %. In this type, the operator precedes the operands. Following are examples of infix notation:

  1. x+y
  2. x+y*z
  3. (x+y)*z
  4. (x+y)*(p+q)

Every single letter (A-Z) and an unsigned integer is a legal infix expression. If X and Y are two valid expressions then (X+Y), then (X−Y) and (X/Y) are legal infix expressions.

Prefix Notation The prefix notation is also called polish notation. The polish mathematician Lukasiewicx invented it. In this type also the operator precedes the operands. Following are the examples of prefix notation:

  1. +xy
  2. +x*yz
  3. *+xyz
  4. *+xy+pq

Postfix Notation The postfix notation is also called as reverse polish notation. The operator trails the operand. Following are the examples of postfix notation:

  1. xy+
  2. xyz*+
  3. xy+z*
  4. xy+pq*+

Consider the following example:

X+Y*Z

In the above expression, we know that the multiplication has higher precedence than addition. The expression X+(Y*Z) is same as the expression X+Y*Z. By applying rules of priority, we can convert the above expression to postfix notation.

X+(Y*Z)

Here, parentheses are not necessary.

X+(YZ*)

Here, multiplication is converted to postfix.

X(YZ*)+

Here, addition is converted to postfix.

XYZ*+

The above equation is postfix form. While doing the conversion operations, following points are important.

  1. When we convert an expression from prefix to postfix form, it is essential that properties like, precedence, commutability and well-formed expressions of operators must be preserved.
  2. The operations with high priority are converted first and after the remaining part of the expression are converted to postfix form. Table 4.3 shows infix to postfix of an expression. The remaining part is considered as a single operand.

     

    Table 4.3 Infix to postfix

    Infix Postfix
    X+Y XY+

    Here, XY is considered as single operand.

     

  3. In suffix and prefix equivalent of an infix expressions, the variables must be in the relative place. The expressions in prefix or suffix are without parenthesis. The operators are set according to precedence rule of operators.
  4. A fully parenthesized infix expression converted directly to postfix form, starting the conversion from innermost parenthesis to outer most parenthesis. For example

( X + Y + ( P + Q + ( T+Y) ) )

The innermost parenthesis (T+Y) is solved first.

The precedence can be changed on purpose by insertion of parenthesis. Consider the following example:

(X+Y)*Z

In the above example, if parenthesis is not inserted the multiplication operation gets first priority. Due to parenthesis the addition operation gets first priority.

(XY+)*Z

Here, the addition is converted in the postfix form.

(XY+)Z*

Here, the multiplication is converted to postfix form.

There are five binary operations such as addition (+), subtraction (−), multiplication (*), division (/) and exponentiation. In C/C++, there is no exponentiation operator. Here, A is used to denote exponent operation.

The equation XAY means X raised to Y. 2^ 3 means 8. When any expression is without parenthesis the order of operation is left to right. Only in exponent the order is from right to left.

X+Y+Z means (X+Y)+Z, on the other hand X^Y^Z means X^(Y^Z). The operation inside the parenthesis gets first priority. Consider the following Table 4.4 which converts infix to postfix to make your understanding perfect.

 

Table 4.4 Infix to postfix.

Infix Postfix
X+Y XY+
X+Y−Z XY+Z−
(X+Y)*(P−Q) XY+PQ−*
LAM*N−O+P/Q/(R+S) LMAN*O−PQ/RS+/+
((L+M)*N−(O−P)^(Q+R) LM+N*OP—QR+^
L−M/(N*O^P) LMNOP^*/−

For converting an expression from infix to prefix the rules are same as like conversion from infix to postfix. In the prefix conversion the operator is placed before the operand. The Table 4.5 converts the infix expression to the prefix.

 

Table 4.5 Infix to prefix

Infix Prefix
X+Y +XY
X+Y−Z −+XYZ
(X+Y)*(P−Q) *+XY−PQ
LAM*N−O+P/Q/(R+S) +−*^LMNO//PQ+RS
((L+M)*N−(O−P)^(Q+R) ^−*+LMN−OP+QR
L−M/(N*OAP) −L/M*N^OP

The postfix form doesn’t require parenthesis. Consider the following expressions:

X+(Y* Z) and (X+Y)*Z

 

Table 4.6 Postfix

Infix Postfix
X+(Y*Z) XYZ*+
(X+Y)*Z XY+Z*

You can see the above Table 4.6 that the postfix expressions have no parenthesis. In the postfix expressions, sequence or precedence of operators decides sequence of operation. While converting infix expression to postfix, it is difficult to know the operation associated with operand.

To write a valid expression whole parenthesization should be applied. However, the parenthesis must not be large. The expression (X+Y)*Z is valid expression and need not be written like ((X+Y)*Z). Here, the outer parenthesis can be omitted and has no purpose. Consider the following expression. The above expression can be written as (P+(Q*R))+(S*T). To evaluate the expression it must be scanned from left to right. Fig. 4.9 illustrates the expression.

Figure 4.9 Expression and operation precedence rank

If parentheses are present in the expression, then the precedence will be changed. For example, in expression (P+Q)*R, first P+Q is solved and then multiplication takes place. Actually, it is possible to declare an expression that makes the sequence of evaluation of expression independent of the priority of the operators. This can be done by putting subexpressions in the parentheses. The operators and operands are enclosed in the parentheses. Thus, we have several parenthetical levels as shown in the Fig. 4.10. Such expressions are called fully parenthesized expressions. Consider the following example,

Figure 4.10 Fully parenthesized expressions

The numbers indicate parenthetical level of operators. When such an expression is solved, the sub-expression having the operator with top parenthetical level is solved first. When two parentheses have equal parenthetical levels, the left-sided parentheses are evaluated first. Followed by parenthesis 2 and 1.

In case the expression is partially parenthesized, a repetitive scanning from left to right is essential to evaluate the expressions. This is because the operators present in conjunction with the operands within the expression. The scanning is shunned in case the infix expression is converted to postfix or prefix expression.

4.8 EVALUATION OF POSTFIX EXPRESSION

The postfix expressions are very simple. On the other hand, programming of evaluation of expression is complicated. This is because the numbers and characters are mixed in one string. The programmer needs to separate digits and symbols and perform arithmetic operation.

Each operator in the postfix expression is associated with the previous two operands. When we read an operand from a given expression it is pushed onto the stack. When an operator symbol is read, the operands associated with it are the top elements of the stack. We can pop these two elements from the stack and perform the operation. The obtained result from the last operation is again pushed onto the stack. Table 4.7 describes the algorithm for conversion of the infix expression to postfix.

 

Table 4.7 Algorithm for conversion of infix to postfix

Algorithm
1. Insert a ‘)’ at the end of X, where X is an expression
2. Check X from left to right and go back over the next 3 and 4 steps for every element of X until ‘)’ is found.
3. In case operands are found, push it on the stack.
4. a. If any operator is found, pop the top-most two elements from stack.

b. Evaluate the expression formed by top two elements.

c. Push the result obtained onto the stack.

5. Allocate value equal to top stack element.
6. Quit.

Example 4.10

Write a program to evaluate postfix expressions.

Solution

# include <stdio.h>

# include <conio.h>

# include <ctype.h>

# include <math.h>

float stack[10];

int top=−1;

void push(char);

float pop();

float exp_eval(char[],float[]);

main ()

{

int j=0;

char s_fix[20];

float number[20],res;

clrscr();

printf ("\n Enter a postfix expression: ");

gets(s_fix);

    while (s_fix[j]!='\0')

    {

    if(isalpha(s_fix[j]))

    {

        fflush(stdin);

        printf ("\n Enter number for %c: ",s_fix[j]);

        scanf ("%f",&number[j]);

    }

    j++;

}

res=exp_eval(s_fix, number);

printf("The res of %s =%f", s_fix,res);

getch();

}

float exp_eval( char s_fix[], float data[])

{

int j=0;

float opA,opB,fs;

char ch;

while (s_fix[j]!='\0')

{

    ch=s_fix[j];

    if (isalpha(s_fix[j]))

    {

        push(data[j]);

    }

    else

    {

        opB=pop();

        opA=pop();

            switch(ch)

            {

            case '+': push(opA+opB); break;

            case '-': push(opA-opB); break;

            case '*': push(opA*opB); break;

            case '/': push(opA/opB); break;

            case 'A': push(pow(opA,opB)); break;

        }

        }

        j++;

    }

fs=pop();

return(fs);

}

void push (char c)

{

top=++top;

stack[top]=c;

}

float pop()

{

float n;

n=stack[top];

top=−−top;

return(n);

}

OUTPUT

Enter a postfix expression: jk*

Enter number for j: 4

Enter number for k: 5

The res of jk* =20.000000

Explanation In this program before main () function, the float type array stack [10] and integer variable top are defined. They are initialized with −1. The prototype of functions push (), pop () and exp_val () are declared. User has to enter expression and the gets () function activates the input stream and the entered expression is stored in the s_fix[] character array.

The expression is checked and for every alphabet user has to enter a number. Immediately after this, the function exp_eval () is invoked with two arguments, i.e. s_fix and number. Both the arguments are array name and holds base address. This function returns result and is stored in variable res.

In the exp_eval () function the variable ch holds the arithmetic operation. The switch () case structure determines the operation to be carried out. The pop () function is invoked and the two popped values are stored in variables popB and popA. These variables are passed to push () function in switch () case structure.

4.9 CONVERSION OF EXPRESSION FROM INFIX TO POSTFIX

In any expression, there are two types of components clubbed together. They are operand and operators. The operator indicates the operation to be carried out and the operand indicates the values. The operands are the variables on which the operator operates. Operators have their priority of execution. When one or more operations are clubbed together in a single expression the priority decides which operation is to be performed first. Suppose, an expression contain two operations with high and low priority. We can force the low priority operation to evaluate first by putting that particular operation in parenthesis. When nested parenthesis are present in the expression the inner-most parenthesis is solved first. In any expression the parenthesis are solved first. The operations are generally solved from left to right. Table 4.8 shows the operator precedence.

 

Table 4.8 For operator precedence

Operator Precedence
Exponent
High
Multiplication (*), Division (/)
Next
Addition (+), Subtraction (−)
Low

Consider the following example:

x−y/(p*q)+(u*v)

The operators are −,/,^,+,* and x,y,p,q,u and v are variables. The parenthesis are used to provide higher priority to the operation (p^q) and (u*v).

Consider the example

Expression: X+ Y* Z

 

Table 4.9 Conversion of X+Y*Z into postfix

Character Postfix string Stack
X
X  
+
X
+
Y
XY
+
*
XY
+*
Z
XYZ
+*
  XYZ*
+
  XYZ*+  

The expression is scanned and when operators are found, they are pushed on the stack. The operators are pushed according to priority of execution of the stack. When operator + is found it is pushed onto the stack. The precedence of * is higher than +. The symbol * is pushed onto the stack. At last, when string reaches to end the stack is popped and its content is appended to the postfix string. These operations are illustrated in Table 4.9.

Expression: (P+Q)*C

 

Table 4.10 Conversion of (P+Q)*C into postfix

Character Postfix string Stack
(
 
(
P
P
(
+
P
(+
Q
PQ
(+
)
PQ+  
*
PQ+
*
R
PQ+R
*
  PQ+R*  

In the above example, opening parenthesis is found. Until the left parenthesis is not found the entire stack is popped. Here, the parentheses provide first priority to addition. Table 4.10 explains the conversion. Table 4.11 describes the algorithm for infix to postfix.

 

Table 4.11 Algorithm for conversion infix expression into postfix

Algorithm for Conversion of Infix Expression to Postfix
1. Push to the end of X, where X is an arithmetic expression.
2. Check expression from left to right and follow the steps 3 to 6 for every element of X until the stack is vacant.
3. In case an operand is found, add it to R, where R is the equivalent postfix expression.
4. In case left ‘(’ parenthesis is found push it onto stack.
5. In case an operator is found, then follow the following steps:
  1. Continually pop from the stack and add each operator to R at the top of stack. The pushed item should have same or upper precedence than the former operator encountered.
  2. Append operator (recently encountered) onto stack.
6. In case ‘)’ right parenthesis is found, then follow the following steps:
  1. Continually pop from the stack and append to every operator to R until left parenthesis is found.
  2. Eliminate the left parenthesis.

Example 4.11

Write a program to convert infix expression to postfix form.

Solution

# include <stdio.h>

# include <conio.h>

# include <string.h>

# include <process.h>

char stack[20];

int T=−1;

void topost(char in_fix[]);

void push(char);

char pop();

main()

{

char in_fix[25];

clrscr();

puts (" Enter an infix expressions: ");

gets(in_fix);

puts ("\n Postfix Expression: ");

topost(in_fix);

}

void push (char s)

{

if (T>=19)

{

puts (" Stack overflow ");

exit(0);

}

else

{

T=T+1;

stack[T]=s;

}

}

char pop ()

{

char num;

if (T==−1)

{

puts (" Stack is Empty ");

getch();

return (0);

}

else

{

num=stack[T];

T−−;

}

return (num);

}

int prefix (char ch)

{

if (ch=='/') return (5);

else if (ch=='*') return (4);

else if (ch=='+') return (3);

else return (2);

}

void topost (char in_fix[])

{

int len;

static int index=0,pos=0;

char s,t;

char postfix[40];

len=strlen(in_fix);

push('#');

while(index<len)

{

s=in_fix[index];

switch(s)

{

case '(': push(s); break;

case ')': t=pop();

while (t!='(')

{

    postfix[pos]=t;

    pos++;

    t=pop();

}

break;

case '+':

case '-':

case '*':

case '/':

case '^':

while (prefix(stack[T])>prefix(s))

{

   t=pop();

    postfix[pos]=t;

    pos++;

}

push (s); break;

default: postfix[pos++]=s; break;

}

index++;

}

while (T>0)

{

t=pop();

postfix[pos++]=t;

}

postfix[pos++]='\0';

puts(postfix);

return;

}

OUTPUT

Enter an infix expressions: m+s+p

Postfix Expression: msp++

Explanation In this program an infix expression is converted to postfix form. The prototype of function topost (), push () and pop () are declared. The array stack [20] is declared. In addition, the integer variable T is declared and initialized with −1. In function main (), a character array in_fix[] is declared. The infix expression is entered by the user. The function topost () is invoked and in_fix is sent as an argument.

In the function topost (), length of in_fix array is counted. Using push () function '#' is pushed. The integer variable index is initialized to zero. The while loop executes until the value of index is less than len. The variable s contains the value of in_fix[index] character. If the value of s is ‘(’, it is pushed and if it contains ‘)’ and pop () function is executed. The variable s is passed to switch () case statement. Accordingly, case statements are executed.

4.10 APPLICATIONS OF STACKS

Few applications of stack are narrated together with examples.

4.10.1 Reverse String

We know the stack is based on last-in-first-out rule. It can be achieved simply by pushing each character of the string onto the stack. The same can be popped in reverse fashion. Thus, reverse string can be done. Consider the following program.

Example 4.12

Write a program to reverse the string using stack.

Solution

# include <stdio.h>

# include <conio.h>

char text[40];

void main ()

{

 char ch;

 void push (char,int);

 char pop(int);

 int j=39,k;

 clrscr();

 puts ("\n Enter a string (* to end): ");

while (ch!='*' && j>=0)

{

 ch=getche();

 push (chj);

 j−−;

}

k=j;

j=0;

printf ("\n Reverse string is: ");

while (k!=40)

{

 ch=pop(k);

 printf ("%c",ch);

 k++;

}

}

void push ( char c, int j)

{

 if (c!='*')

 text[j]=c;

}

char pop (int j)

{

 char c;

 c=text[j];

 text[j]=text[j+1];

 return c;

}

OUTPUT

Enter a string (* to end):

HELLO*

Reverse string is: OLLEH

Explanation In this program the array text [40] is declared as global. So, other two functions push () and pop () have access to it. The character entered is pushed on the stack. When user enters ‘*’ the character reading loop is interrupted and immediately pop operation is carried out. During pop operation the pop () function returns one character its per execution. The string is displayed as reverse because the pop operation is reverse of push. The Fig. 4.11 represents the process.

Figure 4.11 Reverse string

4.10.2 Stack Frames

All the programs compiled using high-level language compilers uses stack frame for function invocation. Operational memory uses stack frames to store the variables declared in the program. During the function, execution number of data is pushed onto the stack. When the function execution terminates, the stack content is popped. When a function is invoked, local variables, formal arguments and return address are pushed onto the stack. Thus, every function executes in a particular or a separate circumstance and hence recursion of function is also possible. Consider the following program code:

fun (int p, int q)

{

int h;

if (condition) return (value);

h=10;

return joy(int h);

}

joy ( int l)

{

int m,u;

m=1, u=2;

return fun(m,u);

}

The above is an example of indirect function in which two functions fun () and joy () invokes each other. For every invocation of function new stack frame is created and as mentioned earlier new copy local variables, return address and formal arguments are pushed. Conceptually, the stack is a piece of main memory, which is used by the program to temporarily store data. When a function is invoked, variables are pushed onto the stack and when function execution ends, the stack is popped. When a function invokes another function (other than itself) the parameters of caller function are pushed onto the stack with address subsequently called instruction. This is because after execution of called function, the compiler can keep track of previous path and it can determine where to return after execution.

4.10.3 Conversion of Number System

Suppose, one wants to calculate binary number of a given decimal number, the given number is repeatedly divided by 2 until 0 is obtained. The binary number can be displayed in reverse order using stack rule last-in-first-out (LIFO). Consider the following program:

Example 4.13

Write a program to convert a given decimal number to binary. Explain the role of stack mechanism.

Solution

# include <stdio.h>

# include <conio.h>

int num[7];

main ()

{

int n,k,T=7;

void show();

void push(int,int );

clrscr();

printf ("\n Enter a number: ");

scanf ("%d",&n);

printf ("\n The binary number is: ");

while (n)

{

k=n%2;

push(−−T,k);

n=n/2;

}

show();

}

void push (int j, int b)

{

 num[j]=b;

}

void show ()

{

 int j;

 for (j=0;j<7;j++)

 printf (" %d ",num[j]);

}

OUTPUT

Enter a number: 9

The binary number is: 0 0 0 1 0 0 1

Explanation In this program the binary equivalent is obtained by repeatedly dividing by two. Here, the first binary digit obtained is pushed on the stack. This process is continued. The show () function displays the binary digits stored in the stack, i.e. an array.

4.10.4 Recursion

The recursion is the fundamental concept of the mathematical logic. Recursion is one of the important facilities provided in many languages. C also supports recursion. There are many problems, which can be solved recursively. The loop which performs repeated actions on a set of instructions can be classified as either iterative or recursive. The recursive loop is different from the iterative loop. In the recursion, the procedure can call itself directly or indirectly. In the directly called recursion the procedure calls itself repeatedly. On the other hand, if the procedure calls another procedure then it is an indirect recursion. In recursion, some statements, which are specified in the function, are executed repeatedly. Every time a new value is passed to the recursive function till the condition is satisfied. A simple programming example is given below.

Example 4.14

Write a program and find the greatest common divisor of the given two numbers.

Solution

# include <stdio.h>

# include <conio.h>

int stack[40],top=−1;

main ()

{

 void gcd(int,int );

 int n1,n2;

 clrscr();

 printf("\nEnter number:- ");

 scanf("%d",&n1);

 printf("\nEnter number:- ");

 scanf("%d",&n2);

 gcd(n1,n2);

 printf("\nThe gcd of %d & %d is:- %d",n1,n2,stack[top]);

}

void gcd(int a,int b)

{

 if(a!=b)

{

if(a>b)

{

top++;

stack[top]=a-b;

printf("\nTop value is:- %d",stack[top]);

gcd(a-b,b);

}

else

{

top++;

stack[top]=b-a;

printf("\nTop value is:- %d",stack[top]);

gcd(a,b-a);

}

 }

}

OUTPUT:

Enter number:- 5

Enter number:- 25

Top value is:- 20

Top value is:- 15

Top value is:- 10

Top value is:- 5

The gcd of 5 & 25 is:- 5

Explanation In this program the stack[] and the top are the global variables. By using the n1 and n2 variables the two numbers are input by the user. The gcd() function is the recursive function which is recursively called till the greatest common divisor of the two given numbers is obtained. The program stores the difference of the two numbers, which are passed by the function into stack []. The value present at top is the greatest common divisor of the two numbers.

Example 4.15

Write a program to convert decimal to binary by using the concept of recursion.

Solution

# include <stdio.h>

# include <conio.h>

int stack[40],top=−1;

main ()

{

void binary(int);

int no;

clrscr();

printf("\nEnter number:- ");

scanf("%d",&no);

binary(no);

printf("\nThe binary of the given number is:-");

while(top>=0)

{

printf(" %d ",stack[top]);

top−−;

}

}

void binary(int b)

{

if(b>0)

{ top++;

stack[top]=b%2;

binary(b/2);

 }

}

OUTPUT:

Enter number:- 255

The binary of the given number is:- 1 1 1 1 1 1 1 1

Explanation This program includes the function binary () which is called recursively for calculating the binary of a given decimal number. The number is prompted by the user in variable no. On modulus operation, the reminders are stored in the stack. At first, the least significant bit is obtained and it is stored on the top of the stack. Subsequently, the other reminders are obtained and pushed into the stack and the pop operation is carried out for displaying them.

4.11 ACTIVATION RECORD ORGANIZATION

The group of fields such as: a) memory for local variables, b) declaration of function, c) return addresses, and d) pointer to location are pushed, when a function is invoked and popped, when a function execution is completed. This particular record of function is known as an activation record.

The details of the fields are described in the following topics. In the block structure programming languages, the programmer can define variable with same name but with different scopes. Two variables with the same name cannot be declared in a single block. The scope can be categorized in two types: a) Local b) Global. The local scope of a variable is limited to a specific block in which a variable is declared. The global scope covers entire program. The variables declared in a global scope can be accessed by any sub-program. If, in a program, a variable with same name is declared in local and global variable then the local variable gets first priority. Consider the following program:

Example 4.16

Write a program to declare same variable within different blocks and display their values and addresses.

Solution

# include <stdio.h>

# include <conio.h>

main ()

{

int j=10;

clrscr();

printf ("\n Value of j is %2d & it’s address is = %u"j,&j);

{

int j=5;

printf ("\n Value of j is %2d & it’s address is = %u"j,&j);

}

printf ("\n Value of j is %2d & it’s address is = %u"j,&j);

}

OUTPUT:

Value of j is 10 & it’s address is = 65496

Value of j is 5 & it’s address is = 65494

Value of j is 10 & it’s address is = 65496

Explanation In this program you can observe that a variable int j is declared twice, first, immediately in main () function and second, declaration is done in a separate block inside the main () function. The values and their addresses displayed of both variables are different. The first and last printf () statement displays the same value and address because they are in main () block. The second statement is in the sub block.

4.12 SCOPE RULES

The above program is based on scope rule of the variable. The scope rules are of two kinds:

  1. Static scope
  2. Dynamic scope.

Static Scope The static scope declares the variable in circumstances of syntactic program structure. In such a program structure, one can easily conclude the declaration of variable by only reading the program. This is why the rule is known as static. The static rule can be defined as follows:

  1. The scope of a variable is limited to the current block in which it is declared, other blocks have no access to the variable.
  2. If a variable is not declared in a particular block, in such a case, the variable declaration of previous block is considered. If declaration, not found, it searches the nested blocks until the declaration is found. This rule is called “most closely nested rule”.

For example, consider the following program code from the previous program:

{

int j;

printf ("\n Address of j =%u",&j);

}

If we remove the statement int j, the output of the program would be:

Address of j =65524

Address of j =65524

Address of j =65524

This is because, when declaration is not found in the above block, the nearest closely declaration is considered and this is why the address of variable j declared in main () is printed.

Dynamic Scope The dynamic scope is different from static scope. In the dynamic scope, address of variable is determined at the time of program execution. The same variable name can be defined several times in the same program. The variable is activated in the memory when a sub-block is under execution. However, the variables have same name but their addresses are different. Hence, no ambiguous situation occurs for compiler.

The declaration of variables is considered from the nearly occurring and currently active definition of the variable during execution of the program.

Consider the following program:

Example 4.17

Write a program to demonstrate dynamic scope of variable.

Solution

# include <stdio.h>

# include <conio.h>

main ()

{

int j;

void A(void);

void B(void);

clrscr();

A();

printf ("\n Address of j in main() %u",&j);

B();

}

void A ()

{

int j;

printf ("\n Address of j in A() is %u",&j);

}

void B ()

{

int j;

printf ("\n Address of j in B() is %u",&j);

}

OUTPUT

Address of j in A() is 65518

Address of j in main() 65524

Address of j in B() is 65518

Explanation In this program, the variable int j is declared in functions main (), A () and B (). Only declaration does not allocates memory, when a program execution starts, only at that time memory is allocated to the variable. If execution of main () is started, the memory is not allocated to the variables of other functions. Memory is allocated to variables only when a function is invoked. From the output, we can observe that though variable names are same, their memory locations are different.

4.13 SCOPE RULES THROUGH STACK

So far, we have studied the scope rules of variable. Now, we will learn its implementation through stack. While following scope rules with stack, the system programmer needs to take care of memory allocation of variables declared in different blocks. There are two types of storage allocation:

  1. Static storage allocation
  2. Dynamic storage allocation.

Static Storage Allocation The static storage allocation is simple to define. It is a compile time binding. The space required for variables including all sub-programs are reserved. All subprograms are compiled. The total memory required can be calculated by adding the total amount of memory required by each individual program. The amount of memory calculated cannot further increase or decrease during the program execution. Thus, it is very safe for program execution. Thus, the program is only executed when the system is able to provide required resources to the program. Otherwise, compile time error or warning message will be displayed.

Dynamic Storage Allocation In dynamic storage allocation, memory is allocated during program execution as per the requirement of the program. When a sub-function is invoked, memory is allocated and de-allocated when control returns. The space requirement is not constant. At different calls of a function, the amount of memory required may be different. For example, if a function is invoked recursively, one cannot determine how deep the recursion will proceed and it is not possible to calculate the accurate amount of memory required by the function. The program related to dynamic storage allocation is required to take necessary precautions to shun accidental failure of system due to insufficient memory. Thus, it is as well necessary to check whether the memory allocation is successfully carried or not. If memory allocation fails, the sub-routine should transfer the control to next statement. The explanation of such routines is out of the scope of the book.

Now, we are going to discuss scope rules implementation with dynamic memory allocation. The handy implementation tool is stack. Such implementation is known as run-time stack. When a sub-function is invoked, memory is allocated and as soon as execution ends the memory is de-allocated. That specific block of memory is called an activation record. Such record consists of following structure:

  • Storage space for all variables including sub functions
  • Definition of functions and pointers
  • Return address
  • A pointer to activation record.

The Fig. 4.12 shows activation record.

Activation records are stored in the stack. The stack is controlled during program execution. When a new function is invoked, control passes to it. Its activation record is pushed onto the stack. The return address is stored in return address field. When function execution completes, the control returns to the caller function. It obtains the return address from the return address field of the activation record. Immediately after that the activation record is popped. The Fig. 4.12 shows the activation records.

Figure 4.12 Activation record

Consider the following program code and Fig. 4.13.

Figure 4.13 Functions

The function main () invokes function P (). The function P () invokes function Q () and R (). When a new function is invoked, the activation record is pushed and when function execution completes the record is popped. Thus, the stack is updated when new function is invoked and a function completes its execution. Thus, by maintaining the stack the next function, which is to be executed, is decided. Table 4.12 shows the stack operation.

 

Table 4.12 Stack operation of a program

Stack Status Operation
MAIN() Activation record of main () is pushed onto the stack
MAIN() P Function main () calls P()
MAIN() P Q Function invokes Q()
MAIN() P Q () execution completes and control returns to P
MAIN() P R P() invokes R()
MAIN() P R () execution completes and control returns to P
MAIN() P() completes execution and return to main ().

Consider the following program code. There are five activation records. The total numbers of activation records are equal to number of functions defined. The filed pointer to the location is defined only in dynamic scope. At the time of program execution, activation records of functions are pushed and popped to and from the stack.

Example 4.18

Write a program to demonstrate the above theory with an example.

Solution

# include <stdio.h>

# include <conio.h>

void Q(void);

void R(void);

main ()

{

void P(void);

clrscr();

printf ("\n main ()");

P();

printf ("\n Again in main () ");

}

void P ()

{

printf ("\n In P() ");

Q();

printf ("Execution of Q complete");

R();

printf ("Execution of R complete");

}

void Q () { printf ("\n In Q() "); }

void R () { printf ("\n In R() "); }

OUTPUT

main ()

In P()

In Q() Execution of Q complete

In R() Execution of R complete

Again in main ()

Explanation In this program P (), Q () and R () are three functions defined. The main () function invokes P (). The function P () invokes Q () and R () one by one. Messages are displayed when a function is invoked which help the user to understand the flow of the program. From the following Fig. 4.14 we can observe that the program execution sequence is main ()−P ()− Q ()−P ()−R ()−main (). Here, function P () is not invoked twice. After complete execution of Q (), control returns in function P ().

Figure 4.14 Flow of program execution

Summary
  1. Stack is an important tool in programming languages. Most of the programming languages support stack operations. The main operations are push and pop. The insertion of element onto the stack is called “push” and deletion operation is called “pop”. Due to the push operation that adds elements in the stack, the stack is also known as pushdown list. The most and least reachable elements in the stack are known as the “top” and “bottom” of the stack. Stack is a set of elements in a last-in-first-out technique.
  2. The insertion and deletion operations are carried out at one end. Hence, the recent element inserted is deleted first. If we want to delete the particular element of the stack, it is necessary to delete all the elements appearing before that element.
  3. A top pointer maintains track of the top elements.
  4. When stack has no element, it is called empty stack.
  5. Whenever an element is inserted (push operation) in the stack the value of pointer top is increased by one. In the same manner, the value of pointer is decremented when an element is deleted from the stack (pop operation).
  6. If a pop operation is performed on an empty stack it is called as underflow stack. An operation to insert an element more than the capacity of stack is known as overflow stack.
  7. Static implementation can be implemented using arrays. However, it is a very simple method but it has few limitations.
  8. Pointers can also be used for implementation of stack. The linked list is an example of this type of implementation. The limitations noticed in static implementation can be removed by using dynamic implementation.
  9. Recall that array name itself is a pointer. Pointer implementation of a stack is carried out similar to array implementation.
  10. An arithmetic expression contains operators and operands. Variable and constant are operands. The operators are of various kinds such as arithmetic binary, unary, for example, + (Addition), − (subtraction), *(multiplication), / (division) and % (modular division).
  11. Arithmetic expressions can be defined in three kinds of notation: infix, prefix and postfix. The prefixes ‘pre’, ‘post’ and ‘in’ indicates the relative location of the operator with two operands.
  12. Each operator in the postfix expression is associated with the previous two operands. When we read an operand from a given expression it is pushed onto the stack. When an operator symbol is read, the operands associated with it are the top elements of the stack. We can pop these two elements from the stack and perform the operation.
  13. In any expression, two types of components can be clubbed together. They are operand and operators. The operator indicates the operation to be carried out and the operand indicates the values. The operands are the variables on which the operator operates. Operators have their priority of execution. When one or more operations are clubbed together in a single expression the priority decides which operation is performed first.
  14. The group of field such as a) memory for local variables, b) declaration of function, c) return addresses and d) pointer to location are pushed when a function is invoked and popped when a function execution completed. This particular record of function is known as an activation record.
  15. The static scope declares the variable in circumstances of syntactic program structure.
  16. The dynamic scope is different from static scope. In the dynamic scope, address of a variable is determined at the time of program execution.
  17. The static storage allocation is simple to define. It is a compile time binding.
  18. In dynamic storage allocation, memory is allocated during program execution as per the requirement of the program. When a sub-function is invoked, memory is allocated and de-allocated when control returns.
Exercises
  1. Answer the following question:
    1. What do you mean by stack?
    2. Define various terms related to stack.
    3. Explain implementation procedure of stack.
    4. What is the top of the stack?
    5. What do you mean by stack overflow and stack underflow?
    6. Explain the terms infix expression, postfix expression, and polish notation.
    7. Distinguish between prefix and postfix expressions.
    8. What are the applications of stacks?
    9. Explain the push and pop operations.
    10. Explain scope rules.
    11. Explain activation record.
    12. Explain stack mechanism.
    13. Distinguish between static and dynamic implementation of stack.
    14. Explain the stack technique last-in-first-out with two real life examples.
    15. Translate following infix expressions to its equivalent prefix expressions:
      1. (x+y-z)/(h+k)-z
      2. (j+k)*(c/d)
    16. Explain solution for following expressions:
      1. From infix to postfix j-k / (g^h)+(n+m)
      2. From infix to prefix j-k / (g^h)+(n+m)
      3. From infix to postfix x*(c+d)+(j/k)*n+m*p
      4. From infix to postfix AABAC
      5. From infix to postfix A&&B I I ! (A>B)
    17. Evaluate the expression 123+*78 3/-. Show the contents of stack after every step in tabular form
  2. Attempt following programs:
    1. Write a program to demonstrate push () and pop () operation using class and member function.
    2. Write a program to enter an integer. Reverse the digits of the integer. Use stack mechanism.
    3. Write a program to implement stack operation push and pop with pointer.
    4. Write a program to perform following operations:
      1. push
      2. pop
      3. stack underflow
      4. stack overflow
      5. display all elements.
    5. Write a program to implement stack with two-dimensional array. Perform push () and pop () operation.
    6. Write a program to perform following stack operations:
      1. Create a stack with item code and quantity

         

        Item code Quantity
        001 450
        002 0
        003 487
        004 101
        005 500
        006 0
        007 359
        008 0
        009 458

         

      2. Delete the items having quantity zero and update the stack.
  3. Select the appropriate option for each of the following questions:
    1. The stack is based on the rule
      1. first-in-last-out
      2. last-in-first-out
      3. both (a) and (b)
      4. first-in-first-out
    2. The push () operation is used
      1. to insert an element
      2. to remove an element
      3. to move an element
      4. all of the above.
    3. The pop operation removes
      1. the element lastly inserted
      2. first element of the stack
      3. any element randomly
      4. none of the above.
    4. The top pointer is increased
      1. when push () operation is done
      2. when pop () operation is done
      3. both (a) and (b)
      4. none of the above.
    5. A stack holding elements equal to its capacity and if push is performed then such situation is called
      1. stack overflow
      2. stack underflow
      3. illegal operation
      4. none of the above.
    6. The prefix notation is also called as
      1. polish notation
      2. postfix notation
      3. infix notation
      4. none of the above.
    7. From the given options one is not a stack application
      1. template
      2. recursion
      3. reverse string
      4. conversion of number.
    8. An expression containing more than one operation are solved according to
      1. priority of operators
      2. priority of operands
      3. from left to right
      4. right to left.
    9. The following brackets changes the priority
      1. ()
      2. []
      3. {}
      4. &
    10. The postfix notation is also called as
      1. reverse polish notation
      2. polish notation
      3. prefix notation
      4. postfix notation.
  4. Find the output.
    1. # include <stdio.h>

      # include <conio.h>

      main ()

      {

      static int stack[6]j;

      clrscr();

      printf ("Enter Elements, put zero to exit: \n");

      for(j=0;j<6;j++)

      {

      printf ("\n Elements of stack are: ");

      scanf ("%d",&stack[j]);

      if (stack[j]==0)

      {

      printf ("\nBy choice terminated:- ");

      break;

      }

      }

      if (j>5)

      printf ("Stack is full \n");

      printf("\nStack elements are:-");

      for (j=0;j<6;j++)

      printf (" %d ",stack[j]);

      }

       

    2. # include <stdio.h>

      # include <conio.h>

      main ()

      {

      char stack[5];

      int j,p=0;

      clrscr();

      printf ("Enter less than seven Characters: \n");

      scanf ("%s",&stack);

      printf("\nStack characters are:-");

      for(j=0;j<6;j++)

      {

      p=j;

      if(stack[j]=='\0')

      break;

      }

      if (j>5)

      {

      for (j=0;j<6;j++)

      printf (" %c ",stack[j]);

      printf ("\nStack is full \n");

      }

      else

      {

      for (j=0;j<p;j++)

      printf (" %c ",stack[j]);

      }

      }

       

    3. # include <stdio.h>

      # include <conio.h>

      int p,top=0,stack[3],c;

      main()

      {

      void push();

      void show();

      clrscr();

      push();

      show();

      push();

      show();

      }

      void push ()

      {

      printf("\n Enter number to be pushed:- ");

      scanf("%d",&stack[top]);

      top++;

      }

      void show ()

      {

      printf("\nContents of stack are:-");

      for (p=top−1;p>=0;--p) printf("\n%d ",stack[p]);

      }

       

    4. # include <stdio.h>

      # include <conio.h>

      # include <process.h>

      int p,z=6,top=0,stack[7],c;

      main()

      {

      void push();

      void pop();

      void show();

      clrscr();

      push();

      show();

      push();

      show();

      pop();

      printf("\n\t After pop operation:");

      show();

      }

      void push ()

      {

      printf("\nEnter number to be pushed:- ");

      scanf("%d",&stack[top]);

      top++;

      }

      void pop ()

      {

      top−−;

      }

      void show ()

      {

      printf("\nStack elements are:");

      for (p=top−1;p>=0;—p)

      printf(" \n%d ",stack[p]);

      }

       

    5. # include <stdio.h>

      # include <conio.h>

      main ()

      {

      char text[40];

      int k=0j;

      clrscr();

      puts ("\n Enter a string:- ");

      scanf("%s",&text);

      while (text[k]!='\0')

      k++;

      printf("\nValue of top is:- %d",k);

      printf ("\nReverse string is: ");

      for(j=k;j>=0;j−−)

      {

      printf ("%c",text[k]);

      k−−;

      }

      }

       

    6. # include <stdio.h>

      # include <conio.h>

      main ()

      {

      static int arra[40];

      int k=0,j;

      clrscr();

      puts ("\nEnter numbers (insert 0 to end):- ");

      while(1)

      {

      scanf("%d",&arra[k]);

      if(arra[k]==0)

      break;

      k++;

      }

      printf("\nValue of top is:- %d",k);

      printf ("\nReverse array of numbers is: ");

      while(k>0)

      {

      k−−;

      printf ("%d",arra[k]);

      }

      }

       

    7. # include <stdio.h>

      # include <conio.h>

      int sum=0,stack[40],top=−1;

      main ()

      {

      void sum_num(int);

      int n,i;

      clrscr();

      printf("\nEnter the number:- ");

      scanf("%d",&n);

      sum_num(n);

      printf("\nThe sum of 1 ");

      for(i=2;i<=n;i++)

      printf("+%d",i);

      printf(" is:- %d",stack[top]);

      }

      void sum_num(int d)

      {

      if(d>0)

      {

      top++;

      sum=sum+d;

      stack[top]=sum;

      sum_num(d−1);

      }

      }

       

    8. # include <stdio.h>

      # include <conio.h>

      int fact=1,stack[40],top=−1;

      main ()

      {

      void fact_num(int);

      int n,i;

      clrscr();

      printf("\nEnter the number:- ");

      scanf("%d",&n);

      fact_num(n);

      printf("\nThe multiplication of 1 ");

      for(i=2;i<=n;i++)

      printf("* %d ",i);

      printf(" is:- %d",stack[top]);

      }

      void fact_num(int d)

      {

      if(d>0)

      {

      top++;

      fact=fact*d;

      stack[top]=fact;

      fact_num(d−1);

      }

      if(d==0)

      {

      fact=fact*1;

      top++;

      stack[top]=fact;

      }

      }

       

    9. # include <stdio.h>

      # include <conio.h>

      main ()

      {

      int j;

      clrscr();

      printf ("\n Address of j =%u",&j);

      {

      int j;

      printf ("\n Address of j =%u",&j);

      }

      printf ("\n Address of j =%u",&j);

      }

       

    10. # include<stdio.h>

      # include <conio.h>

      main ()

      {

      int a=5;

      void fun1(void);

      void fun2(void);

      clrscr();

      fun1();

      printf ("\n Value of j is %2d & it’s address in

      main() is %u ",a,&a);

      fun2();

      }

      void fun1 ()

      {

      int a=10;

      printf ("\n Value of j is %2d & it’s address in

      fun1() is %u",a,&a);

      }

      void fun2()

      {

      int a=20;

      printf ("\n Value of j is %2d & it’s address in

      fun2() is %u",a,&a);

      }