Results 1 to 11 of 11
  1. #1
    superhaNds is offline Senior Member
    Join Date
    Apr 2013
    Location
    Sweden
    Posts
    232
    Rep Power
    1

    Default Balanced Symbols

    Hi,

    I have an exercise that should check if an arithmetic expression or some input stream
    has properly balanced enclosure symbols. I.E (6+5*(2+2)) is good, {5+5*[3-5*(4+5) ] } also good, but [5+5*(2-1]+3) is bad

    I must use a Stack array built in implementation I did, which works fine.

    I'm not sure if this is the best approach, but I put all the symbols in the stack then have some standard checks, but finally I am not
    sure how to proceed for the final case to check if the symbols are placed correctly

    Java Code:
    import java.util.Scanner;
    
    public class Test {
    
    	public static void main(String[] args) {
    		String input;
    		int numOfCloseSymbols = 0;
    		StackInterface stack = new StackArrayBased();
    		Scanner in = new Scanner(System.in);
    		
    		System.out.println("Give an arithmetic expression to check if enclosure brackets are placed "
    						+ "Correctly");
    		
    		input = in.nextLine();
    		in.close();
    
    		for (int i = 0; i < input.length(); i++) {
    			if (input.charAt(i) == '(' || input.charAt(i) == '['
    					|| input.charAt(i) == '{' || input.charAt(i) == ')'
    					|| input.charAt(i) == ']' || input.charAt(i) == '}') {
    				numOfCloseSymbols += 1;
    				stack.push(input.charAt(i));
    			}
    		}
    
    		if (numOfCloseSymbols == 0) {
    			System.out.println("No enclosure symbols");
    		} else if (numOfCloseSymbols % 2 != 0) {
    			System.out.println("Not valid");
    		} else {
    			while (!stack.isEmpty()) {
    				// How to check if valid -- for example, this is not -> [ 3 - 5 * ( 3 + 5 ] - 3 )
    			}
    		}
    	
    	}
    }

  2. #2
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    United States
    Posts
    2,924
    Rep Power
    4

    Default Re: Balanced Symbols

    Well, you need to keep track of the various times you encounter a starting or ending bracket. Here is a hint. Map<String,Integer> or perhaps Map<Character,Integer>. Or possibly multiple stacks, one for each bracket type.

    Regards,
    Jim
    Last edited by jim829; 11-12-2013 at 09:37 PM.
    The Java™ Tutorial | SSCCE | Java Naming Conventions
    Poor planning our your part does not constitute an emergency on my part.

  3. #3
    superhaNds is offline Senior Member
    Join Date
    Apr 2013
    Location
    Sweden
    Posts
    232
    Rep Power
    1

    Default Re: Balanced Symbols

    In the map the integer would represent what exactly? if for example '{' is the 1st symbol in the expression?
    Are saying that I should pop all the elements and map them to figure out the validity of the expression by the order of the symbols?

  4. #4
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    United States
    Posts
    2,924
    Rep Power
    4

    Default Re: Balanced Symbols

    Every time you get an opening symbol, push it on the stack. Then when you get a closing symbol. Check the stack. If it is its counter part, you are okay. Pop the stack and continue.

    Regards,
    Jim
    The Java™ Tutorial | SSCCE | Java Naming Conventions
    Poor planning our your part does not constitute an emergency on my part.

  5. #5
    superhaNds is offline Senior Member
    Join Date
    Apr 2013
    Location
    Sweden
    Posts
    232
    Rep Power
    1

    Default Re: Balanced Symbols

    Thank you!

  6. #6
    ras_oscar is offline Member
    Join Date
    Jun 2013
    Posts
    53
    Rep Power
    0

    Default Re: Balanced Symbols

    You could also define 3 int variables initialized to 0; Curly, square, and curved. Every time you encounter an open symbol, add 1. Every time you encounter a close symbol, subtract 1. At the end verify that you ended up back at zero

  7. #7
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,755
    Rep Power
    7

    Default Re: Balanced Symbols

    Why???

    The proposed use of a Stack is a better approach.

  8. #8
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    12,999
    Blog Entries
    7
    Rep Power
    19

    Default Re: Balanced Symbols

    True, if all you want is match balanced parentheses, a stack of characters is sufficient, i.e. push a left parenthesis and pop a right parenthesis is it matches the current input character; any other character is ignored; at the end or the input the stack is supposed to be empty; the advice by ras_oscar was just crappy.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  9. #9
    superhaNds is offline Senior Member
    Join Date
    Apr 2013
    Location
    Sweden
    Posts
    232
    Rep Power
    1

    Default Re: Balanced Symbols

    @ras_oscar I clearly state in the OP that I must use my own array built in implementation of a stack. Similarly like many compilers use stacks to validate.

  10. #10
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,755
    Rep Power
    7

    Default Re: Balanced Symbols

    Just to illustrate why a Stack is a better solution.

    Example 1.
    [({])}

    By using three variables they would all end up at 0 and give a result of being balanced when it isn't.

    Example 2.
    }(((((((((()))))))))){{{{{{{{{{}}}}}}}}}}[[[[[[[[[[]]]]]]]]]]}

    Both algorithms would give this as unbalanced but the Stack would be able to detect it was false at the very first bracket. Using the 3 variable option requires iterating over the entire String before getting a result.

  11. #11
    superhaNds is offline Senior Member
    Join Date
    Apr 2013
    Location
    Sweden
    Posts
    232
    Rep Power
    1

    Default Re: Balanced Symbols

    Just for the record, this is my solution.

    Java Code:
    	public static boolean areSymbolsBalanced(String input) {
    		char c;
    		for (int i = 0; i < input.length(); i++) {
    			if (input.charAt(i) == '(' || input.charAt(i) == '['
    					|| input.charAt(i) == '{') {
    				stack.push(input.charAt(i));
    			} else if ((input.charAt(i) == ')' || input.charAt(i) == ']'
    					|| input.charAt(i) == '}')) {
    				if (!stack.isEmpty()) {
    					c = (Character)stack.pop();
    					if ((c == '(' && input.charAt(i) == ')') 
    							|| (c == '[' && input.charAt(i) == ']') 
    							|| (c == '{' && input.charAt(i) == '}')) {
    						continue;
    					} 
    					return false;
    				}
    				return false;		
    			}
    		}
    		return stack.isEmpty();
    	}

Similar Threads

  1. regex for symbols
    By wildheart25c in forum New To Java
    Replies: 2
    Last Post: 08-01-2012, 06:38 AM
  2. Check for Balanced Parenthesis in a Stack
    By cjw92 in forum New To Java
    Replies: 0
    Last Post: 10-04-2011, 10:16 PM
  3. Checking If A String Contains Symbols
    By SwissR in forum New To Java
    Replies: 7
    Last Post: 07-27-2010, 09:07 AM
  4. Representing ERD with symbols
    By vivvy in forum JDBC
    Replies: 1
    Last Post: 02-17-2010, 05:17 PM
  5. How to cut symbols from a string?
    By gutters in forum New To Java
    Replies: 3
    Last Post: 06-16-2008, 03:47 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •