728x90 AdSpace

Latest Article



Data structures & Stacks in C++ with example and exercises





How to use stacks & POSTFIX EXPRESSIONS in c++? Introduction of data structures & Stacks in C++ with example and exercises 

INTRODUCTION TO DATA STRUCTURES AND STACKS

               This lecture discusses data structures in general and stacks in particular. You will learn about stack, the data associated with a stack and the operations performed on a stack. You will also learn about the postfix notation and evaluation of postfix expressions. The topics are listed below:
  • STACKS
  • POSTFIX EXPRESSIONS

               After this lecture, you should be able to implement stack and its variants in C++. You should also be able to design a program in C++ that is capable of evaluating postfix expressions. If you think that you know enough about the topic, you may skip the lecture and jump to EXERCISES.

DATA STRUCTURES:

               A data structure is an entity that is represented by some data (values) and the operations that can be performed on this data. An important thing to remember at this point is that a study of data structures is more related to mathematics than it is to computer programming. The implementation of a data structure should be kept separate from its study, as implementation is a much later concern. That is where the intangible ADT (Abstract Data Type) comes into the picture. Don't worry, we are not going to study ADT. J All you need to know is that ADT is a way to define data structures in a way that is independent of the implementation issues.

STACKS

               An appropriate definition of a stack would go like " It is an ordered collection (list) of items into which items can be added and from which items can be removed from a single end of the list. This end is called as the top of the stack. Stacks may also be termed as push down lists or LIFO (Last In First Out).Stack is one of the most basic Data Structures. A stack can be visualized as a pile of books or a pile of dishes. The book or dish which is put last of all on the pile is the first one to be removed. As mentioned earlier, a data structure is represented by the data associated with it and the operations that can be done on the data. Now you will try to figure out both the data and the functions that may be associated with a stack.

What Data may be Associated with a Stack?

               A stack was defined as an ordered collection of items. This item is the only data associated with the stack. The items may be integers, characters, or any other predefined data type. The items may even be instances of user defined data types (structures or classes). The phrase ordered dictates that some kind of order must be there. However, the way this order may be achieved is an implementation issue and the definition of stack says nothing about it.
               Another variable associated with a stack is top, which determines the end to which insertions are done or from which deletion takes place.

Which Operations may be Performed on a Stack?

               The two fundamental operations that may be performed on a stack are:
  • Insertion of a new element in the stack: Since we push an item on the top of the stack, this operation is known as push (S, i). The push has two arguments: S and i. The notation means "Push an item i onto the stack S. When we are referring to a single stack, we may use push (i) to mean "Push an item i onto the stack under consideration
  • Deletion of a new element from the stack: As we pop the top item from the stack, this operation is known as pop (S). The pop takes a single arguments: S. The notation means "Pop the item on the top from the stack S. When we are referring to a single stack, we may use pop ( ) to mean "Pop the top item from the stack under consideration
               Two other operations, though less important, may also be defined for a stack. These are stated below:
  • Test if the stack is empty: The operation returns TRUE if the stack is empty and FALSE otherwise. This is written as empty(S) meaning "Test if the stack S is empty". In case of a single stack, empty( ) may be used.
  • Get the Top element of the Stack: The operation returns the value of the top element of the stack without removing it. The operation cane be represented as getTop(S) for a particular stack S, and getTop( ) when a single stack is being considered.
A demonstration of push(i) and pop() functions
 
 


9







6
6
6




4
3
3
3
3
3


2
2
push(3) push(6)  push(9)  pop() pop()  pop()  pop()   push(2)  push(4) 
getTop()=3     getTop()=9     getTop()=3      getTop()=!     getTop( )=4 
       getTop( )=6      getTop( )=6       getTop( )=!    getTop( )=2   

POSTFIX EXPRESSIONS

               When we write mathematical expressions in our daily life, we are using infix notation. Infix notation means that a binary operator will lie between its two operands. Other possible notations are prefix and postfix. As the names indicate, the binary operator lies before the two operands in prefix notation and after the two operands in case of postfix notation. In most of the today's computational systems postfix notation is used to evaluate mathematical expressions. These systems get input in infix notation (because this is the way humans prefer to use) and then convert it into postfix in order to evaluate it. One of the important uses of stacks is in evaluating postfix expressions.
               Now you will first know how to represent expressions in prefix and postfix notations. Then you will use stacks to devise an algorithm that evaluates postfix expressions.
PREFIX
INFIX
POSTFIX
-AB
A-B
AB-
+*ABC
A*B+C
AB*C+
*A+BC
A*(B+C)
ABC+*
+/AB/CD
A/B+C/D
AB/CD/+
               The infix expression to be converted into postfix, should be first parenthesized according to the order of preference. Now the expression inside the inner most parentheses should be first converted to postfix and be written in place of the previous expression. The postfix expression yielded is treated as a single term now and the process is repeated for parentheses having the next precedence. This is repeated until we obtain a complete postfix expression. Following example illustrates the process.
(A+B)*C+D/(E-F)
original infix expression
(((A+B)*C)+(D/(E-F)))
parenthesizing the infix expression
(((AB+)*C)+(D/(EF-)))
converting the innermost addition and subtraction to postfix
(AB+C*)+(DEF-/)
converting the innermost multiplication and division to postfix
AB+C*DEF-/+
converting the final addition to postfix

How to Evaluate a Postfic expression using a stack?

               A postfix expression can be evaluated using a stack. We assume that the postfix expression has operands that can be represented by a single character(0-9). Following algorithm uses a stack to evaluate postfix expressions:
  1. While the postfix expression does not end, do steps 2 and 3
  2. Start reading the expression character by character from the right
  3. If the character is an operand, push it to the stack
    • Else if the character is an operator
      1. pop the top element twice to obtain the last two operands
      2. apply the operator on the two operands
      3. push the result back to stack
  4. pop the stack to obtain the final result


EXERCISES

  • Implement Stack as a C++ class, having two private data members: an integer array data and an integer top. Write functions for push, pop, and empty operations. Then test the stack in a main program using random push and pop sequence. Attempts to pop from an empty stack or push onto a full stack should generate an error message. (Can a stack be full?)
  • Consider a special variant of a stack that has two different push operations. pushOne pushes a single item onto it and the pushTwo pushes two items in order. Another operation strangePop is also defined, which pops one item if it was pushed alone and pops two items from the stack if they were pushed in a pair. Implement this stack in C++.
  • Write a C++ program that inputs a postfix expression and outputs the result. Assume that the input can have operands in the rang 0-9 and only the +,-,*, / operators.


no image
  • Title : Data structures & Stacks in C++ with example and exercises
  • Posted by :
  • Date : 06:44
  • Labels :






  • Blogger Comments
  • Facebook Comments

0 comments:

Post a Comment