Skip to content
TheChatArchiveThe Chat Archive
o1-mini-2024-09-12· OpenAIAi2 WildChat-4.8M (AI2)

Write a single-file java program that solves the following ACSL problem: American…

  1. User

    Write a single-file java program that solves the following ACSL problem:

    American Computer Science League

    2017-2018 SENIOR DIVISION Contest #2 ACSL Enclosure

    PROBLEM: Given string data input representing a mathematical expression, determine the possible location(s) of the missing symbol of enclosure. Although we show spaces between characters for readability, the input strings will have no spaces. All operands will be integers less than 1000. The order of evaluation for the symbols is parentheses, brackets, and then braces.

    Given { [ ( 2 + 3 ) * 6 / 10 }, a bracket is missing. It could be correctly placed in several locations: { [ ( 2 + 3 ) ] * 6 / 10 } Location 8 { [ ( 2 + 3 ) * 6 ] / 10 } Location 10 { [ ( 2 + 3 ) * 6 / 10 ] } Location 13

    INPUT: There will be five lines of input. Each line will contain a string of characters with no spaces representing a mathematical expression. Each type of symbol of enclosure will be used at most once. Each expression will have one missing symbol of enclosure. The operators used will be: +, -, *, and /.

    OUTPUT: For each line of input list all the locations in that expression where the missing symbol of enclosure can be correctly placed. Note: Single integers are never enclosed.

    SAMPLE INPUT

    1. { [ ( 2 + 3 ) * 6 / 10 }
    2. { [ 7 * 25 / 5 + 14 ) * 51 ] + 6 }
    3. { 60 + [ 15 * ( 520 - 505 ) ] / 5 - 23 }
    4. { 32 * 510 + ( 8 / 4 ) * 2 + 43 ] / 24 }
    5. { [ ( 24 + 900 / 300 * 64 ] }

    SAMPLE OUTPUT

    1. 8, 10, 13
    2. 3, 5, 8
    3. 19, 21, 24
    4. 2, 5, 9, 15
    5. 10, 14, 17
  2. Assistant
    import java.util.*;
    import java.io.*;
    
    public class Main {
        public static void main(String[] args) throws IOException {
            // Initialize BufferedReader to read input
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            // Read five lines of input
            List<String> inputs = new ArrayList<>();
            for(int i=0;i<5;i++) {
                String line = br.readLine();
                if(line == null) break;
                // Remove any spaces just in case
                line = line.replaceAll("\\s+", "");
                inputs.add(line);
            }
            // Process each input line
            int lineNumber = 1;
            for(String expr : inputs) {
                // Determine the missing closing symbol
                char missingClosing = findMissingClosingSymbol(expr);
                // If no missing symbol, output empty
                List<Integer> positions = new ArrayList<>();
                if(missingClosing != 0) {
                    // Find all positions to insert the missing closing symbol
                    positions = findValidInsertionPositions(expr, missingClosing);
                }
                // Prepare output
                System.out.print(lineNumber + ". ");
                for(int i=0;i<positions.size();i++) {
                    if(i >0) System.out.print(", ");
                    System.out.print(positions.get(i));
                }
                System.out.println();
                lineNumber++;
            }
        }
    
        // Function to find the missing closing symbol
        private static char findMissingClosingSymbol(String expr) {
            int countOpenParen = 0, countCloseParen = 0;
            int countOpenBracket = 0, countCloseBracket =0;
            int countOpenBrace = 0, countCloseBrace=0;
            
            for(char c : expr.toCharArray()) {
                switch(c) {
                    case '(': countOpenParen++; break;
                    case ')': countCloseParen++; break;
                    case '[': countOpenBracket++; break;
                    case ']': countCloseBracket++; break;
                    case '{': countOpenBrace++; break;
                    case '}': countCloseBrace++; break;
                    default: break;
                }
            }
            
            if(countOpenParen > countCloseParen) return ')';
            if(countOpenBracket > countCloseBracket) return ']';
            if(countOpenBrace > countCloseBrace) return '}';
            return 0; // No missing symbol
        }
        
        // Function to find all valid insertion positions for a given closing symbol
        private static List<Integer> findValidInsertionPositions(String expr, char missingClosing) {
            List<Integer> validPositions = new ArrayList<>();
            int len = expr.length();
            for(int pos=1; pos<=len+1; pos++) {
                StringBuilder sb = new StringBuilder(expr);
                sb.insert(pos-1, missingClosing);
                String modified = sb.toString();
                if(isBalanced(modified)) {
                    validPositions.add(pos);
                }
            }
            return validPositions;
        }
        
        // Function to check if the expression is balanced
        private static boolean isBalanced(String expr) {
            Stack<Character> stack = new Stack<>();
            for(char c : expr.toCharArray()) {
                if(c == '(' || c == '[' || c == '{') {
                    stack.push(c);
                }
                else if(c == ')' || c == ']' || c == '}') {
                    if(stack.isEmpty()) return false;
                    char top = stack.pop();
                    if(!isMatching(top, c)) return false;
                }
                // Ignore other characters (digits and operators)
            }
            return stack.isEmpty();
        }
        
        // Helper function to check matching pairs
        private static boolean isMatching(char open, char close) {
            if(open == '(' && close == ')') return true;
            if(open == '[' && close == ']') return true;
            if(open == '{' && close == '}') return true;
            return false;
        }
    }