9
\$\begingroup\$

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();
    System.out.println("Introduce your expression");

    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");
    }

}
  }
\$\endgroup\$
  • \$\begingroup\$ It seems to me that ((x) would pass, when it shouldn't \$\endgroup\$ – janos Sep 18 '17 at 6:22
  • \$\begingroup\$ @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' \$\endgroup\$ – user178403 Sep 18 '17 at 7:09
  • 4
    \$\begingroup\$ 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. \$\endgroup\$ – Eric Lippert Sep 18 '17 at 20:10
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – Eric Lippert Sep 18 '17 at 20:16
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – RobAu Sep 19 '17 at 15:16
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ why would be better to use ww as a boolean type variable? \$\endgroup\$ – user178403 Sep 18 '17 at 20:36
  • \$\begingroup\$ 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 \$\endgroup\$ – user178403 Sep 18 '17 at 20:43
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Barmar Sep 22 '17 at 3:28
  • 1
    \$\begingroup\$ But in general, flags are boolean, since they're either on or off. \$\endgroup\$ – Barmar Sep 22 '17 at 3:29
  • 1
    \$\begingroup\$ I see, well in my program the flag show when an error appear, so maybe it should be named found found a mistake. @Barmar \$\endgroup\$ – user178403 Sep 22 '17 at 4:08
31
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ what if you receive as input: ')(' ? it shouldn't be correct \$\endgroup\$ – user178403 Sep 18 '17 at 7:12
  • 8
    \$\begingroup\$ on the first ")" the counter gets below zero... \$\endgroup\$ – Sharon Ben Asher Sep 18 '17 at 7:43
  • 2
    \$\begingroup\$ 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 \$\endgroup\$ – Sharon Ben Asher Sep 18 '17 at 7:45
  • \$\begingroup\$ very nice/short/good answer but it's part of the exercise to use Stacks :( (that's why the tag) \$\endgroup\$ – user178403 Sep 18 '17 at 18:58
  • 2
    \$\begingroup\$ @Michelle You can think of the stack size as the counter. \$\endgroup\$ – JollyJoker Sep 19 '17 at 9:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.