# Balanced Symbols

• 11-12-2013, 10:14 PM
superhaNds
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

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 )                         }                 }                 } }```
• 11-12-2013, 10:23 PM
jim829
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
• 11-12-2013, 10:46 PM
superhaNds
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?
• 11-12-2013, 11:54 PM
jim829
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
• 11-13-2013, 12:14 AM
superhaNds
Re: Balanced Symbols
Thank you!
• 11-15-2013, 08:05 PM
ras_oscar
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
• 11-16-2013, 02:09 AM
Junky
Re: Balanced Symbols
Why???

The proposed use of a Stack is a better approach.
• 11-16-2013, 11:12 AM
JosAH
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
• 11-16-2013, 05:06 PM
superhaNds
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.
• 11-19-2013, 12:59 AM
Junky
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-20-2013, 12:57 AM
superhaNds
Re: Balanced Symbols
Just for the record, this is my solution.

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();         }```