Stacks, Data Structure & Algorithms

Q. Explain what are the stacks? How can we use the stacks  to check whether an expression is correctly parentheses or not. For example (()) is well formed but (() or )()( is not well formed.

 

Ans:

The stack is a data structure that organizes data in a similar way one organizes a pile of coins. The new coin is all the time placed on the top and the oldest is on the bottom of the stack. When we are accessing coins, the last coin on the pile is the first coin which was removed from the stack. If we want to reach the third coin, we should remove the first two coins from the top of the stack first so that the third coin comes on the top of the stack and we can easily remove it. There is no way at all to remove a coin from anywhere other than the top of the stack.

A stack is useful whenever we need to store data and retrieve data in last in, first out order. Let us take an example the computer processes instructions using a stack in which the next instruction to execute is at the top of the stack.

To determine whether an expression is well parentheses or not:- the two conditions should be fulfilled while pushing an expression into a stack. At first, whenever an opening bracket is pushed inside a stack, there should be an occurrence a closing bracket before we reach the last symbol. Whenever a closing bracket is encountered, the top of the stack is popped until the opening bracket is popped out and discarded. If no such type of opening bracket is found and stack is made empty, then this means that the expression is not well parentheses designed.

An algorithm to check that whether an expression is correctly parenthized or not is written below:

flag=TRUE;

clear the stack;

Read a symbol from input string;

while not end of input string and flag do

{

if(symbol= '( ' or symbol= '[' or symbol = '{' )

push(symbol,stack);

else  if(symbol= ') ' or symbol= '[' or symbol =

'{' )

if stack is empty flag=false;

printf("More right parenthesis than left

parenthises");

else c=pop(stack);

match c and the input symbol; If not matched

{     flag=false;

printf("Mismatched

parenthesis");

}

Read the next input symbol;

}

if stack is empty then

printf("parentheses are balanced properly");

else

printf(" More number of left parentheses than right parentheses");

 

Posted Date: 7/10/2012 7:02:20 AM | Location : United States







Related Discussions:- Stacks, Assignment Help, Ask Question on Stacks, Get Answer, Expert's Help, Stacks Discussions

Write discussion on Stacks
Your posts are moderated
Related Questions
Sequential files are most frequently utilized in commercial batch oriented data processing where there is the concept of a master file on which details are inserted periodically. F

Given is the structure of an AVL tree: struct avl { struct node *left; int info; int bf; struct node *right; }; 2) A multiway tree of n order is an ord

adjacency multilist

What is an unreachable code assertion An unreachable code assertion can be placed at the default case; if it's every executed, then program is in an erroneous state. A loop in

What are stored and derived attributes?  Stored attributes: The attributes kept in a data base are called stored attributes.  Derived attributes: The attributes that are

Q. Write down the algorithm for binary search. Which are the conditions under which sequential search of a list is preferred over the binary search?

Like general tree, binary trees are implemented through linked lists. A typical node in a Binary tree has a structure as follows struct NODE { struct NODE *leftchild; i

Define order of growth The  efficiency  analysis  framework  concentrates   on  the  order  of  growth  of  an  algorithm's   basic operation count as the principal indicator o

how to write a function of area of a circle using python

Insertion: Records has to be inserted at the place dictated by the sequence of keys. As is obvious, direct insertions into the main data file would lead to frequent rebuilding of