Matching Parantheses using stack

Question

Below code is to check whether the given string has balanced parantheses or not using stack. Getting wrong output for input "[]". It should print true but the result that i am getting is false.

import java.util.*;
class Solution{
    public static void main(String[] argh) {
        Scanner sc = new Scanner(System.in);
        Stack st = new Stack();
        boolean flag = true;
        while (sc.hasNext()) {
            String input = sc.next();
            //Complete the code
            for (int i = 0; i < input.length(); i++) {
                flag = false;
                if ((input.charAt(i) == '{') || (input.charAt(i) == '(') || (input.charAt(i) == '[')) {
                    st.push(input.charAt(i));
                    continue;
                }
                if ((input.charAt(i) == '}') || (input.charAt(i) == ')') || (input.charAt(i) == ']')) {
                    if (st.isEmpty()) {
                        flag = false;
                    } else {
                        char item = (char) st.pop();
                        if ((item == '(') && (input.charAt(i) == ')'))
                            flag = true;
                        if ((item == '{') && (input.charAt(i) == '}'))
                            flag = true;
                        if ((item == '[') && (input.charAt(i) == ']'))
                            flag = true;
                    }
                }
            }
            if (!st.isEmpty())
                flag = false;
            System.out.println(flag);
        }
    }
}

[What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173) — Andy Turner, Apr 03 '20 at 19:18
If I enter `[]` as input, it displays `true`. Can not reproduce. — Johannes Kuhn, Apr 03 '20 at 19:21
However, note that if you enter `][]`, it would also return true, so it doesn't work correctly. — Andy Turner, Apr 03 '20 at 19:22
@xerx593 Why in the world would you use 3 stacks when you can do it more easily with just 1? — Jim Mischel, Apr 03 '20 at 21:31

score 0 · Answer 1 · answered Apr 03 '20 at 21:44

I have reproduced your code below with a few changes (identified by comments) that should get it to work.

import java.util.*;
class Solution{
    public static void main(String[] argh) {
        Scanner sc = new Scanner(System.in);
        Stack st = new Stack();
        while (sc.hasNext()) {
            // jim - Moved this to inside the loop.
            // Assume the input is good unless proven otherwise.
            boolean flag = true;
            String input = sc.next();
            //Complete the code
            // jim - Added the "&& flag == true" to exit if the input is bad
            for (int i = 0; i < input.length() && flag == true; i++) {
                // jim - Commented this out. We'll assume it's good. If the input
                // is found to be bad, we set the flag, and the
                // "&& flag == true" condition above will exit the loop.
                // flag = false; 
                if ((input.charAt(i) == '{') || (input.charAt(i) == '(') || (input.charAt(i) == '[')) {
                    st.push(input.charAt(i));
                    continue;
                }
                if ((input.charAt(i) == '}') || (input.charAt(i) == ')') || (input.charAt(i) == ']')) {
                    if (st.isEmpty()) {
                        flag = false;
                    } else {
                        char item = (char) st.pop();
                        // jim - here, check for not equal, and set to false.
                        if ((item == '(') && (input.charAt(i) != ')'))
                            flag = false;
                        if ((item == '{') && (input.charAt(i) != '}'))
                            flag = false;
                        if ((item == '[') && (input.charAt(i) != ']'))
                            flag = false;
                    }
                }
                else {
                    // jim - added this 'else' clause.
                    // If there's any character other than [{()}], then it's
                    // bad input.
                    flag = false;
                }
            }
            if (!st.isEmpty())
                flag = false;
            System.out.println(flag);
        }
    }
}

There are some improvements you could make to your code, but those few changes I documented should get it to work.

Matching Parantheses using stack

1 Answers1