parenthetic symbols

[swalton]

I am going over these examples because i want to understand algorithms better but there are no solutions for this question.Can anybody show me what this algorithm would look like?

Design an algorithm that checks whether a string is parenthetically correct in time proportional to the size of the string using a stack as an auxiliary data structure.

[S6k9GNh0]

Design an algorithm that checks whether a string is parenthetically correct in time proportional to the size of the string using a stack as an auxiliary data structure.

That has to be the most abstract statement ever.

[Zhuge]

What exactly does "parenthetically correct" mean? That all opening parentheses are closed?

[swalton]

Here is some background information for the question.

In most programming languages, parenthetic symbols (), [], 
and {} must be balanced and properly nested. 
We define a parenthetically correct string of characters as a string 
that matches one of the following patterns,
where S denotes a (possibly empty) string without any parenthetic 
symbols, and P, P’, and P’’ recursively denote parenthetically correct strings:

S
P’(P)P’’
P’[P]P’’
P’{P}.

Hopefully this helps you understand the question better so that you can show me what the algorithm looks like. ^_^

[swalton]

Can anybody help with this question?

[S6k9GNh0]

EDIT and DELETE: I still don't know what this has to do with programming in concept. >.>

[moorecm]

The problem is explained exceptionally well, IMO. Traverse a string and push "opening" symbols to the stack. When "closing" symbols are encountered, verify that the top of the stack is the matching "opening" symbol and pop it off. If the symbols do not match, return an error. Finally, if all is well, verify that the stack is empty.

For example, given "([{]})":

push (
push [
push {
found {, not [
error

Given "([][])":

push (
push [
pop [
push [
pop [
pop (
stack empty
good to go

Given "(":

push (
stack not empty
error

[swalton]

Ok i see what your doing moorecm but is there you can probably explain it a little further so that i may better understand it? Oh and thank you all for the help :D

[Duthomhas]

It is a standard homework question, and was well-stated.



/me oh, just read moorecm's response. +1