Stacks, Data Structure & Algorithms

Assignment Help:

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");

 


Related Discussions:- Stacks

Comparisions and assignments in worst case, Q. Calculate that how many key ...

Q. Calculate that how many key comparisons and assignments an insertion sort makes in its worst case?        Ans: The worst case performance occurs in insertion

Complexity of an algorithm, Q. Explain the complexity of an algorithm?  Wha...

Q. Explain the complexity of an algorithm?  What are the worst case analysis and best case analysis explain with an example.

Representation of a polynomial with a singly linked list, List areutilized ...

List areutilized to maintainPOLYNOMIALS in the memory. For example, we have a functionf(x)= 7x 5 + 9x 4   - 6x³ + 3x². Figure depicts the representation of a Polynomial by means o

Algorithm, give me algorithm of simple interest

give me algorithm of simple interest

Define minimum spanning tree, Define Minimum Spanning Tree A minimum sp...

Define Minimum Spanning Tree A minimum spanning tree of a weighted linked graph is its spanning tree of the smallest weight, where the weight of a tree is explained as the sum

Tower of hanoi, how do we use 4-discs stack to solve tower of hanoi problem...

how do we use 4-discs stack to solve tower of hanoi problem and write an algorithm to solve it?

Delete a given specific node from a doubly linked list. , D elete a specif...

D elete a specific Node from Double Linked List as follows DELETEDBL(INFO, FORW, BACK, START, AVAIL,LOC) 1. [Delete Node] Set FORW [ BACK [LOC]]:= FORW[LOC]& BACK [FORW[

Determine about the unreachable code assertion, Determine about the unreach...

Determine about the unreachable code assertion An unreachable code assertion is an assertion that is placed at a point in a program that shouldn't be executed under any circum

FOLDING METHOD, 12345 SOLVE BY USING FOLDING METHOD

12345 SOLVE BY USING FOLDING METHOD

Determine the effect of ruby in implementation of string, Determine the eff...

Determine the effect of Ruby in implementation of string Ruby has a String class whose instances are mutable sequences of Unicode characters. Symbol class instances are charact

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd