Write a single-file java program that solves the following ACSL problem: American…
- 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
- { [ ( 2 + 3 ) * 6 / 10 }
- { [ 7 * 25 / 5 + 14 ) * 51 ] + 6 }
- { 60 + [ 15 * ( 520 - 505 ) ] / 5 - 23 }
- { 32 * 510 + ( 8 / 4 ) * 2 + 43 ] / 24 }
- { [ ( 24 + 900 / 300 * 64 ] }
SAMPLE OUTPUT
- 8, 10, 13
- 3, 5, 8
- 19, 21, 24
- 2, 5, 9, 15
- 10, 14, 17
- 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; } }