-----------------------------------

blueberykiwi

Sat Mar 26, 2005 6:28 pm


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 

class Recursion 
{
    public static void main(String

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

Sat Mar 26, 2005 6:37 pm


nvm

-----------------------------------

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

i just got the first 2 questions thanks


-----------------------------------

rizzix

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

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.

-- 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

Sat Mar 26, 2005 11:22 pm



-----------------------------------

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


-----------------------------------

wtd

Sat Mar 26, 2005 11:34 pm



-----------------------------------

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

Sat Mar 26, 2005 11:35 pm



-----------------------------------

nice.  :wink:


-----------------------------------

wtd

Sun Mar 27, 2005 1:26 am



-----------------------------------

Gracias.  :)


-----------------------------------

1of42

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

Fri Apr 01, 2005 1:25 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.

This doesn't work.

({[)}]

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

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

Fri Apr 01, 2005 4:50 pm



-----------------------------------

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


-----------------------------------

rizzix

Tue Apr 12, 2005 7:02 pm



-----------------------------------

Think it's safe to post the solution.. i hope so..
import java.util.regex.*;

class Parser {
    final Pattern BRACKET_PATTERN = Pattern.compile(
        "^.*?(\\

here's how you use it: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

Wed Apr 13, 2005 3:30 pm



-----------------------------------

shoot. sorry i thought i had fixed the thread.

edit: there we go.. definitely fixed