i wanted C Program

[thyagi1]

Write a program to check the proper pairing of braces. The program will have two
variables, one to keep track of the left braces and the other to keep track of the right
braces. They both start at value 0 and the appropriate one is incremented each time a
brace is encountered.If the right brace variable ever exceeds the value of the left brace
variable, the program inserts the character pair ?? at that point in the output. If, at
the end of the input file, the left brace variable is greater than the right brace variable,
the program should print a message that include the number of missing right braces as
a series of that many }s.What output is produced for the input }{}{? Do you think that the output is correct?
Try to rectify the algorithm so that the output is }??{}{ 1 missing }.

[gpraghuram]

Write a program to check the proper pairing of braces. The program will have two
variables, one to keep track of the left braces and the other to keep track of the right
braces. They both start at value 0 and the appropriate one is incremented each time a
brace is encountered.If the right brace variable ever exceeds the value of the left brace
variable, the program inserts the character pair ?? at that point in the output. If, at
the end of the input file, the left brace variable is greater than the right brace variable,
the program should print a message that include the number of missing right braces as
a series of that many }s.What output is produced for the input }{}{? Do you think that the output is correct?
Try to rectify the algorithm so that the output is }??{}{ 1 missing }.

Please refer to posting guidelines.
Raghu

[keerthiramanarayan]

Such Programs can be easily specified using Grammars and can be converted to C Programs using Lex and Yacc. However for the specific purpose of matching braces, i doubt if your algorithm will work for all cases. The best way to tackle the matching program is by recursion. Enter when you get the left brace and leave when you get the right brace.

[xoinki]

hi,
I suggest you to use.. PCRE..
http://www.pcre.org/pcre.txt

thnx and Regards,
Xoinki

[Eyeinstyin]

you can also use stack.When left brace comes "{" push it into stack i.e "{".Keep doing this for every left brace.When right brace comes "}" pop the last element out of stack and check if it is left brace .

PUSH means insert into stack
POP means remove out of stack

For correct brace matching stack should be empty at the end of expression

Initially stack is empty or contains some initial values say "X"
1>Now if right brace comes,it will try to pop left brace out .so if expression starts with left brace then it will pop "X" out which is not equal to brace.
2>Now if no of left braces > no of right braces,then stack will not be empty ,it will contain leftbraces and hence not empty.
3>no of right braces > no of left .Here it will try to pop out X again so pop'd element is not left brace and hence expression invalid

Check if this works for others conditions too

[JosAH]

you can also use stack.When left brace comes "{" push it into stack i.e "{".Keep doing this for every left brace.When right brace comes "}" pop the last element out of stack and check if it is left brace .

Since you only push "{"s on the stack you can be sure it is one when you pop
it again. You don't need a stack, just a counter that shows the depth of the
stack if you had one.

A "{" increments the counter and a "}" decrements it again. When the counter
becomes negative you've got an unbalanced right curly bracket.

When the input is exhausted the number of times the counter was negative
equals the number of missing left curly brackets, not the final value of the
counter.

btw, recursion is overkill for this as well.

kind regards,

Jos

[keerthiramanarayan]

Thanks Jos. I will be more carefull while using recursion next time :)

btw, recursion is overkill for this as well.
Jos