A counterexample in balanced parentheses

In this program I had to analyse if the parenthesis given are well balanced. For instance, input (()) is correct and input ())(() is incorrect. I've tested with other similar inputs, so my question is: can my code fail with some weird expression (using parentheses) or will it always work correctly?

public class Main {

public static void main(String[] args) {
Scanner x = new Scanner(System.in);
Stack<String> parenthesis = new Stack<>();

System.out.println("Introduce the length of your expression");
int l = x.nextInt();

x.nextLine();
for (int i = 0; i < l; i++) {
System.out.println("Introduce an element");
String e = x.next();
parenthesis.push(e);
}

analysis(parenthesis);
}

public static void analysis(Stack<String> st) {

Stack<String> closed = new Stack<>();//only for parentesis like this: )

int ww = 0;
while (!st.isEmpty() && ww != 1) {
String s =st.pop();
if (0 == s.compareTo("(") && !closed.isEmpty()) {
closed.pop();
} else if ((0 == s.compareTo("(")) && closed.isEmpty()) {
System.out.println("incorrect expression.");
ww = 1;
} else {
closed.push(s);
}
}
if (ww == 1) {
System.out.println();
} else if (!closed.isEmpty()) {
System.out.println("incorrect espression");
} else {
System.out.println("correct");
}

}
}

• It seems to me that ((x) would pass, when it shouldn't Sep 18, 2017 at 6:22
• @janos no, it works correctly. I didn't consider arguments inside the parenthesis but if you just put as input: (() the output will be 'incorrect expression' Sep 18, 2017 at 7:09
• A better exercise, which you might consider trying right now is: modify your code so that it detects correct vs incorrect strings in the language of balanced parentheses with {}[]() parens. So ({()[]}[]) would be legal but ({())} would not be. Now it is not so simple as just counting how many opens and closed you see; you have to actually use the contents of the stack to solve this problem, and not, as others have noted, simply use the stack as a complicated integer. Sep 18, 2017 at 20:10
• Hint: the way you've written the code is not wrong, but it is more complicated than it needs to be. Try this: Make an empty stack. Go through the inputs. When you see a (, push it on the stack. When you see a ), check to see if the stack is empty; if it is, you have a bad input. If not, pop the stack. If you end up with a non-empty stack, you have a bad input. Otherwise you have a good input. This program should be much shorter and simpler than yours. Sep 18, 2017 at 20:16
• @Michelle do you know why? Because it doesn't improve readability and is more prone to causing NullPointerExceptions (when s == null) than the equals in my comment. Sep 19, 2017 at 15:16

Inside the analysis method, you only use the variable ww as 0 or 1. This would be better as a boolean type instead of int type.

Currently analysis has two actions:

1. Validate the input
2. Write the response to the console.

The analysis would be more reusable if you removed the printing and put it in a different function. And then analysis would return String instead of void.

This:

public static void analysis(Stack<String> st) {
...<snip>...
if (ww == 1) {
System.out.println();
} else if (!closed.isEmpty()) {
System.out.println("incorrect espression");
} else {
System.out.println("correct");
}
}


becomes

public static String analysis(Stack<String> st) {
...<snip>...
if (ww == 1) {
return "\n";
} else if (!closed.isEmpty()) {
return "incorrect espression\n";
} else {
return "correct\n";
}
}


Some of your variable names are really good (such as parentheses), but some are only a single letter or two, which can be hard to understand by someone else reading your code. l would be better as length, x could be scanner or input, etc. I still haven't figured out what ww is, other than a flag of some kind.

Is there a reason the user needs to type each character in the parentheses one at a time instead of all at once?

You have a typo in one of your incorrect espression blocks. And one ends with a period while the other does not.

• why would be better to use ww as a boolean type variable? Sep 18, 2017 at 20:36
• I feel more comfortable typing character in the parentheses one at a time, it's just an option, also I don't see disadvantages on doing it Sep 18, 2017 at 20:43
• @Michelle That's too generic. The name of a flag variable should say what condition it's flagging. E.g. in a search function you might call it found, in a validation function it might be called valid. Sep 22, 2017 at 3:28
• But in general, flags are boolean, since they're either on or off. Sep 22, 2017 at 3:29
• I see, well in my program the flag show when an error appear, so maybe it should be named found found a mistake. @Barmar Sep 22, 2017 at 4:08

May I suggest a simpler solution: You need only a counter. it is incremented by 1 whenever you encounter an openning parenthesis "(" and is decreased by 1 whenever you encounter a closing parenthesis ")" The input is invalid if the counter drops below zero or is not zero by the end of scanning.

EDIT
since OP specified they must use a stack, we can follow @JollyJoker's advice: counter increament is implemented by a push operation, counter decrement by a pop one. counter falling below zero is implemented by attemt to pop when the stack is empty. by the end of scanning the stack has to be empty.

• what if you receive as input: ')(' ? it shouldn't be correct Sep 18, 2017 at 7:12
• on the first ")" the counter gets below zero... Sep 18, 2017 at 7:43
• in my answer I meant if (the counter drops below zero) or (is not zero by the end of scanning) so the input is invalid the instant the counter gets below zero which really mean an extra closing parenthesis Sep 18, 2017 at 7:45
• very nice/short/good answer but it's part of the exercise to use Stacks :( (that's why the tag) Sep 18, 2017 at 18:58
• @Michelle You can think of the stack size as the counter. Sep 19, 2017 at 9:00