Author |
Topic: Parentheses Matching (Read 7050 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Parentheses Matching
« on: May 25th, 2005, 11:00am » |
 Quote  Modify
|
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?
|
|
 IP Logged |
|
|
|
VincentLascaux
Guest
|
|
Re: Parentheses Matching
« Reply #1 on: May 25th, 2005, 11:41am » |
Quote Modify
 Remove
|
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 
| hidden: |
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();
|
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Parentheses Matching
« Reply #2 on: May 25th, 2005, 11:51am » |
Quote Modify
|
Can you describe what the PM procedure is specifically?
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Parentheses Matching
« Reply #3 on: May 26th, 2005, 2:17am » |
Quote Modify
|
on May 25th, 2005, 11:51am, 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 
|
|
IP Logged |
|
|
|
VincentLascaux
Guest
|
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?
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Parentheses Matching
« Reply #5 on: May 26th, 2005, 7:25am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Parentheses Matching
« Reply #6 on: May 26th, 2005, 8:22am » |
Quote Modify
|
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 
|
| « Last Edit: May 26th, 2005, 8:24am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Parentheses Matching
« Reply #7 on: May 26th, 2005, 8:33am » |
Quote Modify
|
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.
|
| « Last Edit: May 26th, 2005, 8:39am by Deedlit » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Parentheses Matching
« Reply #8 on: May 26th, 2005, 9:41am » |
Quote Modify
|
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>
|
| « Last Edit: May 26th, 2005, 9:43am by Grimbal » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Parentheses Matching
« Reply #9 on: May 26th, 2005, 9:41am » |
Quote Modify
|
on May 26th, 2005, 6:30am, 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.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Parentheses Matching
« Reply #10 on: May 26th, 2005, 9:58am » |
Quote Modify
|
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
|
| « Last Edit: May 26th, 2005, 10:01am by Grimbal » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Parentheses Matching
« Reply #11 on: May 26th, 2005, 12:29pm » |
Quote Modify
|
on May 26th, 2005, 8:33am, 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..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Parentheses Matching
« Reply #12 on: May 27th, 2005, 8:04am » |
Quote Modify
|
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. 
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Parentheses Matching
« Reply #13 on: May 27th, 2005, 9:52am » |
Quote Modify
|
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
|
| « Last Edit: May 27th, 2005, 9:56am by TenaliRaman » |
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print