Computer Science Canada

Java- Recursion
Author:  blueberykiwi [ Sat Mar 26, 2005 6:28 pm ]
Post subject:  Java- Recursion
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...
Author:  blueberykiwi [ Sat Mar 26, 2005 6:37 pm ]
Post subject:  nvm
actually can i just get help on the 3rd question?

i just got the first 2 questions thanks
Author:  rizzix [ Sat Mar 26, 2005 6:41 pm ]
Post subject: 
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.
Author:  wtd [ Sat Mar 26, 2005 7:31 pm ]
Post subject: 
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."
Author:  rizzix [ Sat Mar 26, 2005 11:22 pm ]
Post subject: 
hmm.. i'm not sure but ehm i dont think that covers cases like: "({[]}[])"
Author:  wtd [ Sat Mar 26, 2005 11:34 pm ]
Post subject: 
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>


Smile
Author:  rizzix [ Sat Mar 26, 2005 11:35 pm ]
Post subject: 
nice. Wink
Author:  wtd [ Sun Mar 27, 2005 1:26 am ]
Post subject: 
Gracias. Smile
Author:  1of42 [ Fri Apr 01, 2005 1:16 pm ]
Post subject: 
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.
Author:  wtd [ Fri Apr 01, 2005 1:25 pm ]
Post subject: 
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
Author:  1of42 [ Fri Apr 01, 2005 4:50 pm ]
Post subject: 
Hehe... Oh well, I guess that's what I get for not thinking about a problem enough Razz
Author:  rizzix [ Tue Apr 12, 2005 7:02 pm ]
Post subject: 
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
Author:  rizzix [ Wed Apr 13, 2005 3:30 pm ]
Post subject: 
shoot. sorry i thought i had fixed the thread.

edit: there we go.. definitely fixed

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy