1. Senior Member
Join Date
Apr 2013
Location
Sweden
Posts
263
Rep Power
2

## 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. Senior Member
Join Date
Jan 2013
Location
Northern Virginia, United States
Posts
3,418
Rep Power
5

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

3. Senior Member
Join Date
Apr 2013
Location
Sweden
Posts
263
Rep Power
2

## 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. Senior Member
Join Date
Jan 2013
Location
Northern Virginia, United States
Posts
3,418
Rep Power
5

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

5. Senior Member
Join Date
Apr 2013
Location
Sweden
Posts
263
Rep Power
2

Thank you!

6. Member
Join Date
Jun 2013
Posts
55
Rep Power
0

## 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. ## Re: Balanced Symbols

Why???

The proposed use of a Stack is a better approach.

8. ## 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

9. Senior Member
Join Date
Apr 2013
Location
Sweden
Posts
263
Rep Power
2

## 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. ## 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. Senior Member
Join Date
Apr 2013
Location
Sweden
Posts
263
Rep Power
2

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

#### Posting Permissions

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