CODEWITHSUNDEEP
javanestedstack
Scarl
Scarl

Reputation: 950

Checking if an expression is balanced in terms of parantheses

I'm trying to check if an expression is balanced in terms of its parentheses , my program should output the appropriate messages as follows: (I'm reading the expression from a file)

If for every ")" there is an "(" then it's balanced. If there is a ")" with no "(" then the left parentheses is missing , and so on.

i worked out the code for the case of " (A+B) " and it prints balanced, but for the case of " (A+B))" it prints Balanced and Left missing and I can't seem to figure out what the problem is

here's the code: (EDIT: I worked it out as a method, it works fine when the expression is balanced and when the right parenthesis is missing, but if the left one is missing it prints out "balanced") The problem is when it has a missing left parenthesis, the stack returned is empty, so that's why it prints "balanced" . I dont really know how to fix that case!

 public static Stack isBalanced(String str) {

    Stack s = new Stack();
    char temp;

    for (int i = 0; i < str.length(); i++) {
        if (str.charAt(i) == '(') {
            s.push(str.charAt(i));
        } else if (str.charAt(i) == ')') {
                if (!s.isEmpty()) {
                temp = (char) s.pop();
            }
        }
    }
    return s;
}

Upvotes: 0

Views: 989

Answers (3)

Scarl
Scarl

Reputation: 950

I've solved the problem, in the end I had only 1 condition which was checking if the stack was not empty, and I didn't put a condition when the stack was not empty, so if the stack happened to be empty I will push the closing parentheses into it and in the main the appropriate message will be printed ( I forgot to add my mm in the code above)

        if (!s.isEmpty()) {
           temp = (char) s.pop();
        }else{
         s.push(str.charAt(i));
    }

Then in the mm I'm checking whether my returned stack is empty or not and print the right messaged (balanced- left missing- right missing)

Upvotes: 0

Tim B
Tim B

Reputation: 41178

This seems like an overly complex approach to the problem. You can simplify this a lot just by realizing that in this case you are only matching one possible pair so a simple count is enough.

Simply scan through the string checking each character. Increment a counter at each (, decrement it at each ).

If the counter ever falls below zero then you have an extra closing bracket. If you finish the scan and the counter is not zero then you have an extra opening bracket.

Upvotes: 6

chrylis -cautiouslyoptimistic-
chrylis -cautiouslyoptimistic-

Reputation: 77177

You're checking whether the stack isEmpty every single time you encounter a ) and printing "Balanced" the first time your count gets down to zero. You should only make that check at the very end (and you'll also need to make sure you never saw a stack underrun throughout).

Upvotes: 3

Related Questions