Give an algorithm that returns the position

Assignment Help Data Structure & Algorithms

Reference no: EM13691700

Question: A common problem for compilers and text editors is to determine if the parentheses (or other brackets) in a string are balanced and properly nested.

For example, the string "((())())()" contains properly nested pairs of parentheses, but the string ")()(" does not; and the string "())" does not contain properly matching parentheses.

Part (a) Give an algorithm that returns true if a string contains properly nested and balanced parentheses, and false if otherwise. Hint: At no time while scanning a legal string from left to right will you have encountered more right parentheses than left parentheses.

Part (b) Give an algorithm that returns the position in the string of the first offending parenthesis if the string is not properly nested and balanced That is, if an excess right parenthesis is found, return its position; if there are too many left parentheses, return the position of the first excess left parenthesis. Return -1 if the string is properly balanced and nested.

Can you solve this problem and show all the workings.

Reference no: EM13691700

Questions Cloud

Program that will read in 8 numbers into an array : Write a program that will read in 8 numbers into an array. Print out the numbers from the array, then print the 2nd number, the 5th number and the last number.

Write a method compact that removes all zeroes : Write a program that reads a text file (compact.txt) and stores the integers in an array. Your instructor will provide this text file.

Write a program which initialize an integer array : Write a program which performs the tasks - return the control to main( )and print the new array elements in main.

Steps in preparing a high level language program : Describe the purpose of each step in preparing a high level language program for execution (editing, compiling, linking, and loading). Include in your description the types of files created with each of the first three steps.?

Give an algorithm that returns the position : Give an algorithm that returns true if a string contains properly nested and balanced parentheses, and false if otherwise. Hint: At no time while scanning a legal string from left to right will you have encountered more right parentheses than left..

Define an adt for character strings : Define an ADT for character strings. Your ADT should consist of typical functions that can be performed on strings, with each function defined in terms of its input and output. Then define two different physical representations for strings.

Describe ways to generalize a simple sorting algorithm : Describe ways to generalize a simple sorting algorithm (such as insertion sort, or any other sort you are familiar with) to support this generalization

The keto form of uracil predominates at room temperature : Problem- Suggest a spectroscopic method that could be used to show that the keto form of uracil predominates at room temperature. Why does the keto form predominate over the enol form

Is it likely that both ring connections are mad : Problem- Is it likely that both ring connections are mad simultaneously in this experiment (Miniscale synthesis of a substituted pyrimidine) as was observed for the diels-alder synthesis

User Account

All Pages