program if the parenthesis match?

Question

program in determining if the program match.. if we input (()) then the answer would be "the parenthesis match"

Answer 1

As long as you're not trying to actually parse anything, you can just keep a count. Start at 0 when you start going through the input character by character. Every time you see an open parenthesis, add 1. Every time you see a closed parenthesis, subtract 1.



If the number ever goes negative, it's an error (a closing parenthesis without a matching opening). If you hit the end of the string and the number isn't zero, then there's a mismatch between open and closed.



=================

public class MyClass {

static String parenMatch(String s) {

int count = 0;

for (int i=0; i
char c = s.charAt(i);

if (c == '(') count++;

else if (c == ')') {

count--;

if (count < 0) return "Unmatched closed paren";

} }

if (count > 0) return "" + count + " unmatched open paren(s)";

return null;

}

public static void main(String[] args) {

String s = "(foo bar) (( bletch)";

System.out.println(s + " -> " + parenMatch(s));

s = "(foo bar) ) oops";

System.out.println(s + " -> " + parenMatch(s));

s = "(foo bar) (bletch)";

System.out.println(s + " -> " + parenMatch(s));

} }



=================

Sample output:



(foo bar) (( bletch) -> 1 unmatched open paren(s)



(foo bar) ) oops -> Unmatched closed paren



(foo bar) (bletch) -> null

Answer 2

You did not specify the programming language that you are using; so, I cannot tell you the exact programming syntax. However, here is the algorithm.



You must perform 3 separate checks. You will count the total number of characters in the program (use a variable, i.e., intTotalCharacters). Use a loop to process the code segment that you are checking for correct parentheses pairing. The upper limit of the loop should equal the total number of characters. Increment a character counter, i.e. "i," as you check each character.



Use a boolean variable blMatchOK. Initialize it to True.



The loop should exit once either:



Do Until blMatchOK = False Or (i = intTotalCharacters)



Loop



1) You will process each character—one by one. As you do this you will check to see if the character is an opening parenthesis or a closing parenthesis. You need two variables to keep track of the number of opening and closing parentheses. Each time that the program locates either an opening or closing parenetheses, it will increment the corresponding variable.



2) If the character is a closing parenthesis then, use an If statement to check whether the number of closing parentheses is greater than the number of opening parentheses. If it is then, there exists a mismatch in the total number of pairs. Set blMatchOK to False (the loop will exit at this point).



3) The final code check should be to make sure that the total number of opening parentheses equals the total number of closing parentheses.

Answer 3

McFate covered it pretty well, but if you intend to actually use this, there is MUCH more to be done. You will also want to exclude parens that are in quoted strings ( and possibly other exclusions, depending on your language.) And you do NOT want to exclude a quote in a string if it is escaped. You will also need to couple paren matching with block containment. For example:

BEGIN

(statement

END

)

should probably NOT be considered well matched parens. It really becomes a major parsing effort to do completely, but you can write a single pass with something like McFate showed, adding a facility for string exclusion, and make it recursive. Recurse down at the start of each block start and at each block end fail if mismatched in that block, else return back up. The whole program is of course treated as a block. When *that* block returns your parens are successfully matched.



When you get that much done, you will be fairly complete and probably have sufficient framework to add on whatever you discover is still needed.



Hope this helps.