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

The naive solution would be to move a single task from the most busy server to least busy server each second until the load is balanced. This solution does not finish in time (complexity is O(servers*tasks))

A better solution would be to calculate the average number of tasks (desired number of output tasks), and either add or remove tasks to/from a server. If the average rounds up, a number of servers (the "rounded" servers) have to add 1 to their tasks. If the average rounds down, a number of servers have to subtract 1 from their tasks. This ensures the correct answer in cases where the average number of tasks is not an integer. The number of seconds can then be calculated by adding together the difference between each servers' number of tasks and the rounded average. The answer is this number divided by 2 (because we need half the difference).

Runtime

Worst case runtime is O(servers).

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