Требуется написать программу, находящую требуемую расстановку знаков или сообщающую, что таковой не существует

Во время недавних раскопок на Марсе были обнаружены листы бумаги с таинственными символами на них. После долгих исследований учёные пришли к выводу, что надписи на них на самом деле могли быть обычными числовыми равенствами. Кроме того, из других источников было получено веское доказательство того, что марсиане знали только три операции - сложение, умножение и вычитание (марсиане никогда не использовали «унарный минус»: вместо «-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
code: #java
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

Поделиться:

Похожие статьи:

теги: java se