Returns true if a string contains properly nested

Assignment Help Data Structure & Algorithms

Reference no: EM13168045

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.

(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.

(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.

Reference no: EM13168045

Questions Cloud

Payroll and uses the selection construct : This problem involves payroll and uses the selection construct. A possible restatement: An hourly employee's regular payRate is $16.78/hour for hoursWorked

Compute the percent of the rdi : The student ended up calculating that he/she has 2.19 ppm of Vitamin B2 in the diluted sample. Calculate the percent of the RDI of Riboflavin satisfied by consuming this tablet

Design an ethernet network to connect a single client pc : Design an Ethernet network to connect a single client PC to a single server. The two devices are 410 feet apart. They need to communicate at 800 Mbps. Your design will specify the locations of switches and the transmission line between the switche..

Explain what is the calorimeter constant : If the final temperature of the system is 59.4 oC, what is the calorimeter constant (Ccalorimeter) ? Use 4.184 J/goC for the heat capacity of water.

Returns true if a string contains properly nested : 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..

Explain how much energy is required to heat : How much energy (in Joules) is required to heat 10.99 g of water from 12.9 Celsius to 42.4 Celsius?

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.

Imagine that you have been assigned : Imagine that you have been assigned to implement a sorting program. The goal is to make this program general purpose, in that you don't want to define in advance what record or key types are used

How large a value can be stored in an integer variable : Most programming languages have a built-in integer data type. Normally this representation has a fixed size, thus placing a limit on how large a value can be stored in an integer variable

User Account

All Pages