Требуется написать программу, находящую требуемую расстановку знаков или сообщающую, что таковой не существует
Во время недавних раскопок на Марсе были обнаружены листы бумаги с таинственными символами на них. После долгих исследований учёные пришли к выводу, что надписи на них на самом деле могли быть обычными числовыми равенствами. Кроме того, из других источников было получено веское доказательство того, что марсиане знали только три операции - сложение, умножение и вычитание (марсиане никогда не использовали «унарный минус»: вместо «-5» они писали «0-5»). Также ученые доказали, что марсиане не наделяли операции разным приоритетом, а просто вычисляли выражения (если в них не было скобок) слева направо: например, 3+3*5 у них равнялось 30, а не 18. К сожалению, символы арифметических действий стерлись. Например, если была запись «18=7 (5 3) 2», то возможно восстановить эту запись как «18=7+(5-3)*2». Требуется написать программу, находящую требуемую расстановку знаков или сообщающую, что таковой не существует.
Входные данные
Первая строка входного файла INPUT.TXT состоит из натурального числа, не превосходящего 230, знака равенства, и последовательности натуральных чисел (не более десяти), произведение которых также не превосходит 230. Некоторые группы чисел (одно или более) могут быть окружены скобками. Длина входной строки не будет превосходить 80 символов, и других ограничений на количество и вложенность скобок нет. Между двумя соседними числами, не разделенными скобками, всегда будет хотя бы один пробел, во всех остальных местах может быть любое (в том числе и 0) число пробелов (естественно, внутри числа пробелов нет).
Выходные данные
В выходной файл OUTPUT.TXT необходимо вывести одну строку, содержащую полученное равенство (т.е., исходное равенство со вставленными знаками арифметических действий без лишних пробелов). В случае если требуемая расстановка знаков невозможна, вывести строку, состоящую из единственного числа «-1». Выходная строка не должна содержать пробелов.
Примеры
№ INPUT.TXT OUTPUT.TXT 1 18=7 (5 3) 2 18=7+(5-3)*2 2 5= 3 3 -1
import java.io.File; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.FileWriter; import java.io.IOException; import java.io.LineNumberReader; import java.util.ArrayList; import java.util.LinkedList; public class Marthians { public static void main(String[] args) { File file = new File("INPUT.txt"); File fout = new File("OUTPUT.txt"); if (fout.exists()) { fout.delete(); try { fout.createNewFile(); } catch (IOException e) { e.printStackTrace(); } } FileWriter wout = null; try { wout = new FileWriter(fout); } catch (IOException e1) { e1.printStackTrace(); } LineNumberReader lnr = null; try { lnr = new LineNumberReader(new FileReader(file)); } catch (FileNotFoundException e) { e.printStackTrace(); } String line; MarsExec marsExec; try { while ((line = lnr.readLine()) != null) { marsExec = new MarsExec(line); wout.write(line + " " + marsExec.findResult()); wout.write(" "); } wout.write("\n"); wout.flush(); wout.close(); } catch (IOException e) { e.printStackTrace(); } } private static class MarsExec { private String unparsedLine; private Integer expectResult; private ArrayList<String> operations = new ArrayList<String>(); private static char signList[] = { '+', '-', '*' }; public MarsExec(String line) { this.unparsedLine = line.split("=")[1]; this.expectResult = Integer.parseInt(line.split("=")[0]); } public String findResult() { String result = "-1"; String[] digitsWithSquares = unparsedLine.split(" "); int len = digitsWithSquares.length - 1; operations.clear(); StringBuffer sb = new StringBuffer(len); char currentChar = signList[0]; for (int i = 1; i <= len; i++) { sb.append(currentChar); } changeCharacters(0, sb, len); String[] workOperators; String executeLine; for (String currentOperators : operations) { workOperators = currentOperators.split(""); executeLine = createExecuteLine(workOperators, digitsWithSquares); // System.out.println("execline " + executeLine); if (expectResult == eval(executeLine)) { result = expectResult + "=" + executeLine; break; } } return result; } private String createExecuteLine(String[] workOperators, String[] digitsWithSquares) { StringBuffer sb = new StringBuffer(); for (int i = 0; i < workOperators.length; i++) { sb.append(workOperators[i]); sb.append(digitsWithSquares[i]); } return sb.toString(); } boolean isOperator(char c) { return c == '+' || c == '-' || c == '*'; } int priority(char op) { switch (op) { case '+': case '-': case '*': return 1; default: return -1; } } boolean isDelim(char c) { return c == ' '; } void processOperator(LinkedList<Integer> st, char op) { int r = st.removeLast(); int l = st.removeLast(); switch (op) { case '+': st.add(l + r); break; case '-': st.add(l - r); break; case '*': st.add(l * r); break; } } private int eval(String s) { LinkedList<Integer> st = new LinkedList<Integer>(); LinkedList<Character> op = new LinkedList<Character>(); for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (isDelim(c)) continue; if (c == '(') op.add('('); else if (c == ')') { while (op.getLast() != '(') processOperator(st, op.removeLast()); op.removeLast(); } else if (isOperator(c)) { while (!op.isEmpty() && priority(op.getLast()) >= priority(c)) processOperator(st, op.removeLast()); op.add(c); } else { String operand = ""; while (i < s.length() && Character.isDigit(s.charAt(i))) operand += s.charAt(i++); --i; st.add(Integer.parseInt(operand)); } } while (!op.isEmpty()) processOperator(st, op.removeLast()); return st.get(0); } private StringBuffer changeCharacters(int pos, StringBuffer sb, int length) { for (int i = 0; i <= signList.length - 1; i++) { sb.setCharAt(pos, signList[i]); if (pos == length - 1) { operations.add(sb.toString()); } else { changeCharacters(pos + 1, sb, length); } } return sb; } } }
автор: mutagen