Bracket Sequence

Introduction

You are given a string consisting of the following bracket types: <>, {}, [], (). There are open and close brackets. For example, an open bracket is < and { while a close bracket is > and }. You want to know if the string given is a regular bracket sequence (RBS). A regular bracket sequence is a sequence of brackets such that brackets of the same type open then close, and within that opening and closing, there can be other sequences of brackets that also open and close. It is similar to how in math and in coding, brackets are opened and can have nested brackets within them before being closed. An empty string is also RBS.

Examples of RBS: < { ( [ ] ) } > <>{ } [ <> ( ) ]

Examples of NOT RBS: < { > } <>{ } > <

Solution

Idea

It makes sense to use a stack to solve this problem because the last bracket opened needs to be closed before any of the brackets before that one. So, the general idea is to:
1. iterate through the string and add if we detect an open bracket, we push the same type's close bracket
2. If we detect a character to be a close bracket, we first check if the stack is empty. If this is the case, we have no open brackets that need to be closed which means there is a close bracket without an open bracket, which is not RBS.
3. If the stack is not empty, we move on to peek at the top of the stack to check if the close bracket's type matches the last pushed open bracket's type.
4. If it is the same type, we do not need to replace the bracket so we simply pop the stack.
5. If the close bracket is a different type, we would have to replace it to match the open bracket type, so we increment the number of replaces then pop the stack.

Runtime

Worst case runtime is O(length of input string).

Code

Solution - Java

import java.util.*;
/**
 * Created by alanguo on 2/29/16.
 */
public class bracketSequence {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String input = in.next();
        int num = 0;
        Stack<Character> s = new Stack<Character>();
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            if (c == '}') {
                if(s.empty()) {
                    System.out.println("Impossible");
                    return;
                }
                if (s.peek() == c) {
                    s.pop();
                } else {
                    s.pop();
                    num++;
                }
            } else if (c == '>') {
                if(s.empty()) {
                    System.out.println("Impossible");
                    return;
                }
                if (s.peek() == c) {
                    s.pop();
                } else {
                    s.pop();
                    num++;
                }
            } else if (c == ']') {
                if(s.empty()) {
                    System.out.println("Impossible");
                    return;
                }
                if (s.peek() == c) {
                    s.pop();
                } else {
                    s.pop();
                    num++;
                }
            } else if (c == ')') {
                if(s.empty()) {
                    System.out.println("Impossible");
                    return;
                }
                if (s.peek() == c) {
                    s.pop();
                } else {
                    s.pop();
                    num++;
                }
            } else if (c=='{') {
                s.push('}');
            } else if (c=='[') {
                s.push(']');
            } else if (c=='<') {
                s.push('>');
            } else if (c=='(') {
                s.push(')');
            }

        }
        if(!s.empty()) {
            System.out.println("Impossible");
            return;
        }
        System.out.println(num);
        return;
    }
}