Parenthesis/Brackets Matching using Stack algorith

Question

For example if the parenthesis/brackets is matching in the following:

({})
(()){}()
()

and so on but if the parenthesis/brackets is not matching it should return false, eg:

{}
({}(
){})
(()

and so on. Can you please check this code? Thanks in advance.

public static boolean isParenthesisMatch(String str) {
    Stack<Character> stack = new Stack<Character>();

    char c;
    for(int i=0; i < str.length(); i++) {
        c = str.charAt(i);

        if(c == '{')
            return false;

        if(c == '(')
            stack.push(c);

        if(c == '{') {
            stack.push(c);
            if(c == '}')
                if(stack.empty())
                    return false;
                else if(stack.peek() == '{')
                    stack.pop();
        }
        else if(c == ')')
            if(stack.empty())
                return false;
            else if(stack.peek() == '(')
                    stack.pop();
                else
                    return false;
        }
        return stack.empty();
}

public static void main(String[] args) {        
    String str = "({})";
    System.out.println(Weekly12.parenthesisOtherMatching(str)); 
}

Answer 1

import java.util.*;

public class Parenthesis

 {

    public static void main(String...okok)

    {
        Scanner sc= new Scanner(System.in);
        String str=sc.next();
        System.out.println(isValid(str));

    }
    public static int isValid(String a) {
        if(a.length()%2!=0)
        {

            return 0;
        }
        else if(a.length()==0)
        {

            return 1;
        }
        else
        {

            char c[]=a.toCharArray();
            Stack<Character> stk =  new Stack<Character>();
            for(int i=0;i<c.length;i++)
            {
                if(c[i]=='(' || c[i]=='[' || c[i]=='{')
                {
                    stk.push(c[i]);
                }
                else
                {
                    if(stk.isEmpty())
                    {
                        return 0;
                        //break;
                    }
                    else
                    {

                        char cc=c[i];
                        if(cc==')' && stk.peek()=='(' )
                        {
                            stk.pop();
                        }
                        else if(cc==']' && stk.peek()=='[' )
                        {

                            stk.pop();
                        }
                        else if(cc=='}' && stk.peek()=='{' )
                        {

                            stk.pop();
                        }
                    }
                }

            }
            if(stk.isEmpty())
            {
                return 1;
            }else
            {
                return 0;
            }
        }



    }

}

Answer 2

Algorithm is:

1)Create a stack

2)while(end of input is not reached)

   i)if the character read is not a sysmbol to be balanced ,ignore it.

   ii)if the character is {,[,( then push it to stack

   iii)If it is a },),] then if 

        a)the stack is empty report an error(catch it) i.e not balanced

        b)else pop the stack 

   iv)if element popped is not corresponding to opening sysmbol,then report error.

3) In the end,if stack is not empty report error else expression is balanced.  

In Java code:

public class StackDemo {
    public static void main(String[] args) throws Exception {
        System.out.println("--Bracket checker--");
        CharStackArray stack = new CharStackArray(10);
        stack.balanceSymbol("[a+b{c+(e-f[p-q])}]") ;
        stack.display();

    }

}    

class CharStackArray {
        private char[] array;
        private int top;
        private int capacity;

        public CharStackArray(int cap) {
            capacity = cap;
            array = new char[capacity];
            top = -1;
        }

        public void push(char data) {
            array[++top] = data;
        }

        public char pop() {
            return array[top--];
        }

        public void display() {
            for (int i = 0; i <= top; i++) {
                System.out.print(array[i] + "->");
            }
        }

        public char peek() throws Exception {
            return array[top];
        }

        /*Call this method by passing a string expression*/
        public void balanceSymbol(String str) {
            try {
                char[] arr = str.toCharArray();
                for (int i = 0; i < arr.length; i++) {
                    if (arr[i] == '[' || arr[i] == '{' || arr[i] == '(')
                        push(arr[i]);
                    else if (arr[i] == '}' && peek() == '{')
                        pop();
                    else if (arr[i] == ']' && peek() == '[')
                        pop();
                    else if (arr[i] == ')' && peek() == '(')
                        pop();
                }
                if (isEmpty()) {
                    System.out.println("String is balanced");
                } else {
                    System.out.println("String is not balanced");
                }
            } catch (Exception e) {
                System.out.println("String not balanced");
            }

        }

        public boolean isEmpty() {
            return (top == -1);
        }
    }

Output:

--Bracket checker--

String is balanced

Answer 3

The algorithm:

1. scan the string,pushing to a stack for every '(' found in the string
2. if char ')' scanned, pop one '(' from the stack

Now, parentheses are balanced for two conditions:

• '(' can be popped from the stack for every ')' found in the string, and
• stack is empty at the end (when the entire string is processed)

Answer 4

Actually, there is no need to check any cases "manually". You can just run the following algorithm:

1. Iterate over the given sequence. Start with an empty stack.

2. If the current char is an opening bracket, just push it to the stack.

3. If it's a closing bracket, check that the stack is not empty and the top element of the step is an appropriate opening bracket(that it is, matches this one). If it is not, report an error. Otherwise, pop the top element from the stack.

4. In the end, the sequence is correct iff the stack is empty.

Why is it correct? Here is a sketch of a proof: if this algorithm reported that the sequence is corrected, it had found a matching pair of all brackets. Thus, the sequence is indeed correct by definition. If it has reported an error:

1. If the stack was not empty in the end, the balance of opening and closing brackets is not zero. Thus, it is not a correct sequence.

2. If the stack was empty when we had to pop an element, the balance is off again.

3. If there was a wrong element on top of the stack, a pair of "wrong" brackets should match each other. It means that the sequence is not correct.

I have shown that:

• If the algorithm has reported that the sequence is correct, it is correct.

• If the algorithm has reported that the sequence is not correct, it is incorrect(note that I do not use the fact that there are no other cases except those that are mentioned in your question).

This two points imply that this algorithm works for all possible inputs.

Answer 5

import java.util.*;

class StackDemo {

    public static void main(String[] argh) {
        boolean flag = true;
        String str = "(()){}()";
        int l = str.length();
        flag = true;
        Stack<String> st = new Stack<String>();
        for (int i = 0; i < l; i++) {
            String test = str.substring(i, i + 1);
            if (test.equals("(")) {
                st.push(test);
            } else if (test.equals("{")) {
                st.push(test);
            } else if (test.equals("[")) {
                st.push(test);
            } else if (test.equals(")")) {
                if (st.empty()) {
                    flag = false;
                    break;
                }
                if (st.peek().equals("(")) {
                    st.pop();
                } else {
                    flag = false;
                    break;
                }
            } else if (test.equals("}")) {
                if (st.empty()) {
                    flag = false;
                    break;
                }
                if (st.peek().equals("{")) {
                    st.pop();
                } else {
                    flag = false;
                    break;
                }
            } else if (test.equals("]")) {
                if (st.empty()) {
                    flag = false;
                    break;
                }
                if (st.peek().equals("[")) {
                    st.pop();
                } else {
                    flag = false;
                    break;
                }
            }
        }
        if (flag && st.empty())
            System.out.println("true");
        else
            System.out.println("false");
    }
}

Answer 6

Was asked to implement this algorithm at live coding interview, here's my refactored solution in C#:

Git Tests