Java- Recursion

blueberykiwi · **Posted:** Sat Mar 26, 2005 6:28 pm

i need help on my java assignment, it's due on Monday...i'm stuck... and i'm kinda failing...sooo need a lotta help on this...thanks

Java:

class Recursion
{
public static void main(String[] args) //testing my own methods..doesn't work ><
{
int n = In.getInt();
System.out.println("n=?");
digitSum(5);
}

// method to add digits..using recursion... i.e digitSum(3281) will return 14, and digitSum(1) will return 1

public static int digitSum (int n)

{
if (n < 0)
n = Math.abs(n);
{
if ( n < 10)
return n;
else
n = n%10;
return digitSum(n/=10);
}
}

//method to count the number of occurances of char c

public static int count (String s, char c)
{
int result = 0;
for(int i =0; i < s.length(); i++)
if(s.charAt(i) =='c')
count(s, c);
return result;
}

}

that's the first 2 parts...i kno where to *start*

the 3rd part...i have no idea how to start it...

Suppose that we are working in an environment in which expressions can be bracketed by any
of three types of bracketing operators:
( ) parentheses
[ ] brackets
{ } braces
In a properly formed expression, these characters will be properly nested and matched. To
determine whether this condition holds, you can ignore all other characters and simply look
at the pattern formed by the parentheses, brackets, and braces. In a valid configuration, all
the operators match up correctly, as shown in the following example:
{([])([()])}
The following patterns, however, are illegal for the reasons indicated:
(([]) A closing right parenthesis is missing.
)( The closing parenthesis precedes the opening parenthesis.
{(}) The braces and parentheses are improperly nested.
Write a recursive method with the header
public static boolean isBalanced (String s)
that returns true if the bracketing operators in s are balanced and returns false otherwise.
Your method may assume that s contains only the bracketing characters shown above.

thanks.... i reallie need the help...

blueberykiwi · **Posted:** Sat Mar 26, 2005 6:37 pm

actually can i just get help on the 3rd question?

i just got the first 2 questions thanks

rizzix · **Posted:** Sat Mar 26, 2005 6:41 pm

use a Stack and push the opening braces into the stack, when u come across a closing brace pop the last entry in the stack and check if its the matching opening brace, if not its an error.

edit: wait i didn't realise you had to use recursive functions.

wtd · **Posted:** Sat Mar 26, 2005 7:31 pm

Here's an example. Not in Java, since I can't do your homework for you, but hopefully it'll give you a push in the right direction.

code:

-- Empty string and no matches. Obviously true.
isBalanced "" [] = True
-- Empty string and not an empty set of matches.
-- If it were balanced, the matches would be empty.
isBalanced "" _ = False
-- if non-empty string, but an empty matchset,
-- then if there's an open bracket, add it as a match,
-- but if it's a close bracket, there's nothing for it to
-- match. Otherwise it's a character to ignore.
-- Continue with the remaining string.
isBalanced (firstChar:remainingString) [] =
if elem firstChar "([{"
then isBalanced remainingString [firstChar]
else if elem firstChar "}])"
then False
else isBalanced remainingString []
-- The string is not empty, and neither is the match set.
-- If the string starts with an open bracket, add it to
-- the matchset. If the string starts with a closing bracket,
-- check the matches. If the last match corresponds to the
-- closing bracket, eliminate the last match and continue
-- with the remaining string and matches. If the closing
-- bracket does match up with the las match, then the string
-- is not balanced.
isBalanced (firstChar:remainingString) allMatches@(lastMatch:previousMatches) =
if elem firstChar "([{"
then isBalanced remainingString (firstChar:allMatches)
else if elem firstChar "}])"
then if match firstChar == lastMatch
then isBalanced remainingString previousMatches
else False
else isBalanced remainingString allMatches
where
-- function to match a closing bracket with
-- the corresponding open bracket.
match closingBracket =
case closingBracket of
')' -> '('
']' -> '['
'}' -> '{'
_ -> error "Not a closing bracket."

rizzix · **Posted:** Sat Mar 26, 2005 11:22 pm

hmm.. i'm not sure but ehm i dont think that covers cases like: "({[]}[])"

wtd · **Posted:** Sat Mar 26, 2005 11:34 pm

code:

insaneones@ubuntu:~ $ cd Programming/
insaneones@ubuntu:~/Programming $ ghci Main
___ ___ _
/ _ \ /\ /\/ __(_)
/ /_\// /_/ / / | | GHC Interactive, version 6.2.2, for Haskell 98.
/ /_\\/ __ / /___| | http://www.haskell.org/ghc/
\____/\/ /_/\____/|_| Type :? for help.

Loading package base ... linking ... done.
Compiling Main ( Main.hs, interpreted )
Ok, modules loaded: Main.
*Main> isBalanced "({[]}[])" []
Loading package haskell98 ... linking ... done.
True
*Main>

rizzix · **Posted:** Sat Mar 26, 2005 11:35 pm

nice.

wtd · **Posted:** Sun Mar 27, 2005 1:26 am

Gracias.

1of42 · **Posted:** Fri Apr 01, 2005 1:16 pm

Well, this isn't recursive, but...

Keep 3 variables: 1 keeps track of parentheses, one keeps track of braces, the other keeps track of brackets. Initialize each to 0. Move through the String, adding 1 to a variables any time you encounter one of the characters it represents. Remove 1 on any closing parentheses etyc.

Ensure that no variables are ever negative, if any do become negative return false. At the end, if every variables is at value 0, the string is balanced.

wtd · **Posted:** Fri Apr 01, 2005 1:25 pm

1of42 wrote:

Well, this isn't recursive, but...

Keep 3 variables: 1 keeps track of parentheses, one keeps track of braces, the other keeps track of brackets. Initialize each to 0. Move through the String, adding 1 to a variables any time you encounter one of the characters it represents. Remove 1 on any closing parentheses etyc.

Ensure that no variables are ever negative, if any do become negative return false. At the end, if every variables is at value 0, the string is balanced.

This doesn't work.

code:

({[)}]

Would pass your test, but is not balanced. For what it's worth, though, an implementation of the flawed algorithm. Smile

code:

class String
def each_char
split(//).each { |ch| yield ch }
end

def balanced?
count = {"(" => 0, "{" => 0, "[" => 0}
each_char do |ch|
case ch
when "(" then count["("] += 1
when ")" then count["("] -= 1
when "{" then count["{"] += 1
when "}" then count["{"] -= 1
when "[" then count["["] += 1
when "]" then count["["] -= 1
end
end
count.values.reject { |x| x == 0 }.empty?
end
end

1of42 · **Posted:** Fri Apr 01, 2005 4:50 pm

Hehe... Oh well, I guess that's what I get for not thinking about a problem enough Razz

rizzix · **Posted:** Tue Apr 12, 2005 7:02 pm

Think it's safe to post the solution.. i hope so..

Java:

import java.util.regex.*;

class Parser {
final Pattern BRACKET_PATTERN = Pattern.compile(
"^.*?(\\[|\\]|\$|\$|\\{|\\})+?.*$" //matches all brackets reluctantly
);

boolean isDebug = false;

private boolean isPair(String op, String cl) {
return op.equals("[") && cl.equals("]") ||
op.equals("(") && cl.equals(")") ||
op.equals("{") && cl.equals("}");
}

private boolean isClosed(String bracket) {
return bracket.equals("]") ||
bracket.equals(")") ||
bracket.equals("}");
}

private boolean isOpened(String bracket) {
return bracket.equals("[") ||
bracket.equals("(") ||
bracket.equals("{");
}

private String match(String bracket) {
return bracket.equals("[") ? "]" :
bracket.equals("(") ? ")" :
bracket.equals("{") ? "}" :
bracket.equals("]") ? "[" :
bracket.equals(")") ? "(" :
bracket.equals("}") ? "{" :
"";
}

public void setDebugOutput(boolean b) {
isDebug = b;
}

public boolean isValid(String str) {
if (str.equals("")) return true;
if (isDebug) {
System.out.println("------------------");
System.out.println("str: "+str);
}

Matcher m = BRACKET_PATTERN.matcher(str);
final int strLastIndex = str.length()-1;
int n_oindex, n_cindex;

if (m.matches()) {
int oindex = m.start(1);
String obracket = m.group(1);
if (isOpened(obracket) && oindex < strLastIndex) {
m.region(oindex+1, strLastIndex+1);
if (m.matches()) {
int cindex = m.start(1);
String cbracket = m.group(1);
if (isDebug) System.out.println("looking at: "+cbracket);
if (isPair(obracket, cbracket))
return isValid(str.substring(cindex+1));
else if (isOpened(cbracket)) {
n_oindex = str.indexOf(obracket, oindex+1);
n_cindex = str.indexOf(match(obracket), cindex+1);
while (true) {
if (n_cindex == -1) break;
if (n_oindex == -1 || n_oindex > n_cindex)
return isValid(str.substring(cindex+1, n_cindex))
&& isValid(str.substring(n_cindex+1));
else { // if n_oindex < n_cindex
n_oindex = str.indexOf(obracket, n_oindex+1);
n_cindex = str.indexOf(match(obracket), n_cindex+1);
}
}
}
}
} return false;
} return true;
}

}

here's how you use it:

code:

class Test {
public static void main(String[] args) {
Parser p = new Parser();
p.setDebugOutput(true);
boolean isValid;
isValid = p.isValid("[{()([][])}(){}]");
System.out.println("string is "+(isValid?"":"not")+" valid");
}
}

edit: oops.. long string sorry.. i used that to test the speed of the algorithm

rizzix · **Posted:** Wed Apr 13, 2005 3:30 pm

shoot. sorry i thought i had fixed the thread.

edit: there we go.. definitely fixed

	Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB Username: Password: Register
Wiki Blog Search Turing Chat Room Members