wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Parentheses Matching
        
(Message started by: Barukh on May 25^th, 2005, 11:00am)

Title: Parentheses Matching
Post by Barukh on May 25^th, 2005, 11:00am

You are given a string of open/closed parenetheses of a single type. It's fairly easy to implement the parentheses matching (PM) procedure using a single counter with the set of operations (reset, ++, --).

Is it possible to implement PM given 2 different types of parentheses and using 2 counters?

What about general case of n different types of parentheses?

Title: Re: Parentheses Matching
Post by VincentLascaux on May 25^th, 2005, 11:41am

Quote:

Is it possible to implement PM given 2 different types of parentheses and using 2 counters?

No, if you have [ ( ] ), the basic counter algorithm will return that it's ok when it's not. You need a stack of counters.

Quote:

What about general case of n different types of parentheses?

Same thing... you need to store the type of parenthesis in the stack.

As usual, following code was not tested :)

[hideb]
std::vector< std::pair<int, int> > stack;

/* I assume there is a "read parenthesis" function called read that sets these variable */
bool opened;
int type;

while(read())
{
if(stack.empty())
{
if(!opened) return false;
stack.push_back(std::make_pair(type, 1));
} else {
if(stack.back().first == type)
{
if(opened)
++stack.back().second;
else if(--stack.back().first == 0)
stack.pop_back();
} else {
if(!opened) return false;
stack.push_back(std::make_pair(type, 1));
}
}
}
return stack.empty();
[/hideb]

Title: Re: Parentheses Matching
Post by Deedlit on May 25^th, 2005, 11:51am

Can you describe what the PM procedure is specifically?

Title: Re: Parentheses Matching
Post by Barukh on May 26^th, 2005, 2:17am

on 05/25/05 at 11:51:45, Deedlit wrote:

Can you describe what the PM procedure is specifically?

Parentheses Matching is a standard procedure in parsing the formal languages. Given a sequence of open/closed parentheses of n types (for instance, (), [], {}) PM checks whether the parentheses are properly nested, that is:

1. No subsequence has more closed parentheses that open parentheses of a specific type.

2. Any pair of open/closed parentheses of a specific type encloses the same number of open/closed parentheses of any type.

3. The whole sequence has the same number of open/closed parentheses of any type.

Hope I defined it correctly ;)

Title: Re: Parentheses Matching
Post by VincentLascaux on May 26^th, 2005, 6:30am

I'd rather define it like that:
empty is correct
If E and F are correct, EF (concatenation) is correct
If E is correct (E), {E}, [E]... are correct

In you definition "No subsequence has more closed parentheses than open parentheses of a specific type" looks wrong: ) is a subsequence of () isn't it? Where you speaking of prefixes instead of subsequence?

Title: Re: Parentheses Matching
Post by Deedlit on May 26^th, 2005, 7:25am

I agree that Vincent's makes more sense as an operational definition; Barukh's characterization should be a theorem to be proven. (Not hard, with the fix that Vincent mentioned.)

There certainly is an algorithm that only uses two counters for writing; it turns out that a finite automaton equipped with two counters is a Turing-complete computing model. That means we can implement the parentheses matching procedure by simply reading the string from left to right, and at each step, we transition between a finite number of states, and possibly increment or decrement the two counters.

Of course, I'm sure you're talking about a natural algorithm for implementing the procedure. This does put the kibosh on actually proving that it is impossible, though, unless you come up with other restrictions.

Title: Re: Parentheses Matching
Post by towr on May 26^th, 2005, 8:22am

If you use a turing machine, you don't need any counters, I think..
Just keep eliminating inner pairs of parenthesis
[()({}{})]
->
[({}{})]
->
[({})]
->
[()]
->
[]
->
all matched up

If however you can only move the tape one way, I'm not sure if it works anymore..
It's not very efficient anyway.
And oh yeah, you're destroying the input, probably not something you want :P

Title: Re: Parentheses Matching
Post by Deedlit on May 26^th, 2005, 8:33am

Good point! Yes, it does work just going one way. Why do you say it isn't very efficient? It's O(n), without a large constant I think.

If you don't want to destroy the input, just write the each left parenthesis as you encounter it; for each right parenthesis, erase the last parenthesis if it matches, otherwise return false. This is what I assumed vincent wrote, although I haven't checked his code.

As far as using a counter goes, you can of course implement a stack as a counter in base-b notation. This requires multiplication by a constant; if you wish to disallow that explicitly, a second counter will let you implement it with just incrementing. But the "idea behind it" is a stack.

Title: Re: Parentheses Matching
Post by Grimbal on May 26^th, 2005, 9:41am

It could be simpler if you could save some temporary variables. Here, the original string and 2 variables i and j are all I am using.


<script language="javaScript">

function get(name)
{
      if( document.all )
            return document.all[name];
      else
            return document.getElementById(name);
}

function leftpar(ch){
      return ch=='(' || ch=='[' || ch=='{';
}

function rightpar(ch){
      return ch==')' || ch==']' || ch=='}';
}

function findMatch(str, i){
      var j;
      if( leftpar(str.charAt(i)) ){
            j = 0;
            while( i<str.length ){
                  if( leftpar(str.charAt(i)) ) j++;
                  if( rightpar(str.charAt(i)) ) j--;
                  if( j==0 ) break;
                  i++;
            }
      } else
      if( rightpar(str.charAt(i)) ){
            j = 0;
            while( i>=0 ){
                  if( leftpar(str.charAt(i)) ) j++;
                  if( rightpar(str.charAt(i)) ) j--;
                  if( j==0 ) break;
                  i--;
            }
      }
      return i;
}

function testValid(str){
      var i;
      i = 0;
      while( i<str.length ){
            if( str.charAt(i)=='(' ){
                  i = findMatch(str,i);
                  if( i<0 || i>str.length || str.charAt(i)!=')' )
                        return false;
                  i = findMatch(str,i);
            }
            if( str.charAt(i)=='[' ){
                  i = findMatch(str,i);
                  if( i<0 || i>str.length || str.charAt(i)!=']' )
                        return false;
                  i = findMatch(str,i);
            }
            if( str.charAt(i)=='{' ){
                  i = findMatch(str,i);
                  if( i<0 || i>str.length || str.charAt(i)!='}' )
                        return false;
                  i = findMatch(str,i);
            }
            if( str.charAt(i)==')' ){
                  i = findMatch(str,i);
                  if( i<0 || i>str.length || str.charAt(i)!='(' )
                        return false;
                  i = findMatch(str,i);
            }
            if( str.charAt(i)==']' ){
                  i = findMatch(str,i);
                  if( i<0 || i>str.length || str.charAt(i)!='[' )
                        return false;
                  i = findMatch(str,i);
            }
            if( str.charAt(i)=='}' ){
                  i = findMatch(str,i);
                  if( i<0 || i>str.length || str.charAt(i)!='{' )
                        return false;
                  i = findMatch(str,i);
            }
            i++;
      }
      return true;
}

function check()
{
      var exp = get("exp").value;
      if( testValid(exp) ){
            get("reply").value = "Expression is valid";
      } else {
            get("reply").value = "Expression is NOT valid";
      }
}
</script>

Title: Re: Parentheses Matching
Post by Barukh on May 26^th, 2005, 9:41am

on 05/26/05 at 06:30:10, VincentLascaux wrote:

I'd rather define it like that:
empty is correct
If E and F are correct, EF (concatenation) is correct
If E is correct (E), {E}, [E]... are correct

Yes, this is much better!

Quote:

In you definition "No subsequence has more closed parentheses than open parentheses of a specific type" looks wrong: ) is a subsequence of () isn't it? Where you speaking of prefixes instead of subsequence?

Yes. I am kind of fuzzy these days.

Title: Re: Parentheses Matching
Post by Grimbal on May 26^th, 2005, 9:58am

PS: the idea is to find for each parenthesis the matching one (counting just lefts and rights) and to see if the type matches. Test the code at
http://www.florian.net/puzzle/parens.html

Title: Re: Parentheses Matching
Post by towr on May 26^th, 2005, 12:29pm

on 05/26/05 at 08:33:38, Deedlit wrote:

Good point! Yes, it does work just going one way. Why do you say it isn't very efficient? It's O(n), without a large constant I think.

Well, the way I described it, for a turing machine, as I understand it, it's o(n^2), because you keep moving the tape back and forwards.
Of course if you have random access memory, then it could be O(n); as long as you don't have to search to and fro each time. Which requires at least two pointers. (Which are just as 'bad' as counters)

It really just depends on how you look at it..

Title: Re: Parentheses Matching
Post by Grimbal on May 27^th, 2005, 8:04am

Tonight I realized that the single parentheses problem can be solved with a single counter plus an index to scan the string.
My solution also uses a single index and a single counter. So I am over target. 8)

Title: Re: Parentheses Matching
Post by TenaliRaman on May 27^th, 2005, 9:52am

I am not sure if this is of any relevance to the current discussion. Just thought it would add something to the discussion.

I had written the following code for a module i was working on. This one is a bit incomplete, in the sense, it wont take mixture of expression and brackets as inputs. However, completing it wont take much time.

Code:

#include<stdio.h>
#include<string.h>
int parantheses[256];
void set_parantheses(char *par)
{
for(int i=0;i<256;i++)
parantheses[i]=0;
int len = strlen(par);
int count = 1;
for(i=0;i<len;i++)
{
if(i%2 == 0)
parantheses[par[i]]=count;
else
{
parantheses[par[i]]=-count;
count++;
}
}
}
int parantheses_check(char c,char *a)
{
static int next=0;
static int flag=1;
static char startsymbol=c;
while(a[next]!='\0')
{
if(parantheses[a[next]]>0)
flag = parantheses_check(a[next++],a);
if(parantheses[a[next]]<0)
{
if(parantheses[c] == -parantheses[a[next]])
next++;
else
flag=0;
return flag;
}
}
if(c != startsymbol)
flag = 0;
return flag;
}
int main()
{
char par[] = "(){}[]";
set_parantheses(par);
char test[]="[({({})})]";
if(parantheses_check('0',test))
printf("Correct");
else
printf("Error");
return 0;
}

-- AI