Data structure - arithmetic expressions

Question

Data structure - arithmetic expressions

Navigation

#1 by (2 votes)

1

Recently I received the following challenge in college, but I'm having a hard time doing

The challenge is:

Identify how a subset of numbers from 1 to 1000 can be   written using arithmetic expressions that have only the following   elements:

5, 7, (,), +, - and *.

For example, the expressions for the numbers 30 to 35 are shown below.   It is important to note that expressions should be as short as possible because it would be too simple to find only the equivalent expression of 1 and then sum it up as many times as necessary to get a number. The number of parentheses should also be as few as possible.   The degree of complication of a number is the number of times that 5 and 7 are to be used in the expression that corresponds to the number.   Thus, 30 has the degree of complication 3, and 31 has the degree of complication 5. Expressions must be assembled with as little complication as possible.

Examples:

30 = 5 * 7 - 5
  31 = 7 - (5 * 5) + 7 * 7
  32 = 7 + 5 * 5
  33 = 5 * 7 + 5 - 7
  34 = 7 + 5 * 5 - (5 - 7)
  35 = 5 * 7

So far, I'm trying this way, but I can not get to the result, I hope, it's not generating an error, but the output result is far from being what the exercise asks for.

package ex5e7;

//import static java.lang.Math.pow;
import javax.swing.JOptionPane;

public class Expressoes {

    String[] expressoes = new String[1000];
    boolean[] preenchidos = new boolean[1000];

    public void preenchidos(boolean preencher) {
        if (preencher) {
            for (int i = 0; i < 1000; i++) {
                preenchidos[i] = false;
            }
        } else {
            String pre = "";
            for (int i = 0; i < 1000; i++) {
                if (preenchidos[i]) {
                    pre += i + "\n";
                }
            }
            JOptionPane.showMessageDialog(null, pre);
        }
    }

    public void multiplos() {
        int resultado = 5;
        boolean mil = false;
        expressoes[resultado] = "5 = 5";
        preenchidos[resultado] = true;
        while (!mil) {
            resultado *= 5;
            if (resultado <= 1000) {
                expressoes[resultado] = resultado + " = " + expressoes[resultado / 5].substring(expressoes[resultado / 5].indexOf("=") + 2) + "*5";
                preenchidos[resultado] = true;
            } else {
                mil = true;
            }
        }
        resultado = 7;
        mil = false;
        expressoes[resultado] = "7 = 7";
        preenchidos[resultado] = true;
        while (!mil) {
            resultado *= 7;
            if (resultado <= 1000) {
                expressoes[resultado] = resultado + " = " + expressoes[resultado / 7].substring(expressoes[resultado / 7].indexOf("=") + 2) + "*7";
                preenchidos[resultado] = true;
            } else {
                mil = true;
            }
        }
    }

    public void somas() {
        int resultado = 10;
        boolean mil = false;
        expressoes[resultado] = "10 = 5+5";
        preenchidos[resultado] = true;
        /*while (!mil) {
            resultado += 5;
            if (resultado <= 1000) {
                expressoes[resultado] = resultado + " = " + expressoes[resultado - 5].substring(expressoes[resultado - 5].indexOf("=") + 2) + "+5";
                preenchidos[resultado] = true;
            } else {
                mil = true;
            }
        }*/
    }

    public void mulCincoSete() {
        boolean mil = false;
        int n1 = 125, n2 = 7;
        expressoes[n1 * n2] = "875 = 7*5*5*5";
        preenchidos[n1 * n2] = true;
        while (!mil) {            
            for (int i = n1 - 1; i > 0; i--) {
                if (preenchidos[i]) {
                    n1 = Integer.parseInt(expressoes[i].substring(0, expressoes[i].indexOf("=") - 1));
                }
            }
            if (n1 * n2 <= 1000) {

            } else {
                mil = true;
            }
        }
    }

    /*public int[] multiplos(int num, int tamanho) {
        int[] multiplos = new int[tamanho];
        for (int i = 0; i < tamanho; i++) {
            multiplos[i] = num * tamanho;
        }
        return multiplos;
    }

    public int[] soma(int tamanho) {
        int[] resultados = new int[(int) pow(2, tamanho)];
        int[] num = {5, 7};
        int k = 0;
        for (int i = 0; i < pow(2, tamanho); i++) {
            resultados[i] = 0;
        }
        for (int i = 0; i < pow(2, tamanho); i++) {
            for (int j = 0; j <= 1; j++) {
                resultados[i] += num[j];
            }
        }
        return resultados;
    }*/
}

java

asked by anonymous 04.07.2018 / 21:30

1 answer

create menu instead of select to change form Composer returning memory allocation error

score 2 · Answer 1

I did it. The result is a monstrous thing.

The code below is divided into several parts:

Lexical analysis - Divide a numeric expression into a sequence of tokens. A token can be either a number consisting of a sequence of 5s and 7s or one of the symbols + , - , * , / , ( or ) .
li>
Syntactic trees - Represented by the Operacao functional interface and methods that return lambdas of this type. Responsible for interpreting syntactically well-formed expressions. It can generate an error in case of division by zero or not integer division.
Syntactic analysis - Discover the structure of a given expression. Syntax analysis is based on a context-free language and the parser is recursive recursive LL-1 with the following grammar:
- additive (initial symbol) → multiplicative (cont_additive) *
- cont_address → ( + | - ) multiplicative
- multiplicative → unary (cont_multiplicative) *
- cont_multiplication → ( * | / ) unary
- unary → ( + | - ) parentheses
- parentheses → ( additive ) | number
Random expression string generation - Converts a number to a symbol sequence consisting of 5 , 7 , + , - , * , / , ( and ) .
Evaluate the number of parentheses and the degree of complication of the strings.
Expression Optimizer - Search for the best expression that generates the desired number:
- Search for an increasing number of characters, starting at 1 and going up to 12, and brute force generating all strings of strings with the symbols mentioned in the corresponding size. It only looks for a larger string if you have not found any smaller ones that will serve.
- The strings that are served are those that can be compiled and interpreted without generating lexical, syntactic or interpretation errors and that the result of the evaluation is equal to the number searched.
- When you find a string of a certain size, keep looking for a better string of the same size. If the new string is the same size and less parentheses than the previous one or has the same size and number of parentheses but less complication, test it when compiling and interpreting.

The program tries to optimize all numbers from 0 to 100. The statement says that it is up to 1000, but as this business runs on brute force basis, then it takes time to finish and I had no bag to wait until it solved the 1000 The syntax analyzer code could also be better and a bit more organized, but that should be good enough.

Here is the code:

import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.LinkedHashMap;

/**
 * @author Victor Williams Stafusa da Silva
 */
public class Expressoes {

    private static class ExpressaoMalformadaException extends Exception {}

    private static class AvaliacaoExpressaoException extends Exception {}

    // Árvore sintática e interpretação:

    @FunctionalInterface
    private interface Operacao {
        public int calcular() throws AvaliacaoExpressaoException;
    }

    private static Operacao soma(Operacao a, Operacao b) {
        return () -> a.calcular() + b.calcular();
    }

    private static Operacao sub(Operacao a, Operacao b) {
        return () -> a.calcular() - b.calcular();
    }

    private static Operacao mult(Operacao a, Operacao b) {
        return () -> a.calcular() * b.calcular();
    }

    private static Operacao div(Operacao a, Operacao b) {
        return () -> {
            int ac = a.calcular();
            int bc = b.calcular();
            if (bc == 0 || ac % bc != 0) throw new AvaliacaoExpressaoException();
            return ac / bc;
        };
    }

    private static Operacao op(String simbolo, Operacao a, Operacao b) {
        switch (simbolo) {
            case "+": return soma(a, b);
            case "-": return sub(a, b);
            case "*": return mult(a, b);
            case "/": return div(a, b);
            default: throw new AssertionError();
        }
    }

    private static Operacao simples(int i) {
        return () -> i;
    }

    // Análise léxica:

    private static List<String> tokenize(String expressao)
            throws ExpressaoMalformadaException
    {
        List<String> tokens = new ArrayList<>(expressao.length());
        StringBuilder proximoToken = new StringBuilder(expressao.length());
        for (int i = 0; i < expressao.length(); i++) {
            char c = expressao.charAt(i);
            if ("()+-*/".indexOf(c) != -1) {
                if (proximoToken.length() != 0) {
                    tokens.add(proximoToken.toString());
                    proximoToken = new StringBuilder(expressao.length() - i);
                }
                tokens.add(String.valueOf(c));
            } else if ("57".indexOf(c) != -1) {
                proximoToken.append(c);
            } else {
                throw new ExpressaoMalformadaException();
            }
        }
        if (proximoToken.length() != 0) tokens.add(proximoToken.toString());
        return tokens;
    }

    // Análise sintática:

    private static class Subexpressao {
        private final Operacao op;
        private final List<String> resto;

        public Subexpressao(Operacao op, List<String> resto) {
            this.op = op;
            this.resto = resto;
        }
    }

    private static class Continuacao {
        private final String simbolo;
        private final Operacao op;
        private final List<String> resto;

        public Continuacao(String simbolo, Operacao op, List<String> resto) {
            this.simbolo = simbolo;
            this.op = op;
            this.resto = resto;
        }
    }

    private static class Simbolo {
        private final String op;
        private final List<String> resto;

        public Simbolo(String op, List<String> resto) {
            this.op = op;
            this.resto = resto;
        }
    }

    private static Subexpressao parseAditivo(List<String> tokens) {
        Subexpressao a = parseMultiplicativo(tokens);
        if (a == null) return null;

        List<String> resto = a.resto;
        List<Continuacao> outros = new ArrayList<>();
        while (true) {
            Continuacao proximo = parseContinuacaoAditivo(resto);
            if (proximo == null) break;
            outros.add(proximo);
            resto = proximo.resto;
        }

        for (Continuacao c : outros) {
            a = new Subexpressao(op(c.simbolo, a.op, c.op), c.resto);
        }
        return a;
    }

    private static Continuacao parseContinuacaoAditivo(List<String> tokens) {
        Simbolo sinal = parseTerminal("+", tokens);
        if (sinal == null) sinal = parseTerminal("-", tokens);
        if (sinal == null) return null;

        Subexpressao b = parseMultiplicativo(sinal.resto);
        if (b == null) return null;

        return new Continuacao(sinal.op, b.op, b.resto);
    }

    private static Subexpressao parseMultiplicativo(List<String> tokens) {
        Subexpressao a = parseUnario(tokens);
        if (a == null) return null;

        List<String> resto = a.resto;
        List<Continuacao> outros = new ArrayList<>();
        while (true) {
            Continuacao proximo = parseContinuacaoMultiplicativo(resto);
            if (proximo == null) break;
            outros.add(proximo);
            resto = proximo.resto;
        }

        for (Continuacao c : outros) {
            a = new Subexpressao(op(c.simbolo, a.op, c.op), c.resto);
        }
        return a;
    }

    private static Continuacao parseContinuacaoMultiplicativo(List<String> tokens) {
        Simbolo sinal = parseTerminal("*", tokens);
        if (sinal == null) sinal = parseTerminal("/", tokens);
        if (sinal == null) return null;

        Subexpressao b = parseUnario(sinal.resto);
        if (b == null) return null;

        return new Continuacao(sinal.op, b.op, b.resto);
    }

    private static Subexpressao parseUnario(List<String> tokens) {
        Simbolo sinal = parseTerminal("+", tokens);
        if (sinal == null) sinal = parseTerminal("-", tokens);
        if (sinal == null) return parseParenteses(tokens);

        Subexpressao v = parseParenteses(sinal.resto);
        if (v == null) return null;

        return new Subexpressao(op(sinal.op, simples(0), v.op), v.resto);
    }

    private static Subexpressao parseParenteses(List<String> tokens) {
        Simbolo abre = parseTerminal("(", tokens);
        if (abre == null) return parseNum(tokens);

        Subexpressao dentro = parseAditivo(abre.resto);
        if (dentro == null) return null;

        Simbolo fecha = parseTerminal(")", dentro.resto);
        if (fecha == null) return null;

        return new Subexpressao(dentro.op, fecha.resto);
    }

    private static Subexpressao parseNum(List<String> tokens) {
        if (tokens.isEmpty()) return null;
        String first = tokens.get(0);
        int t;
        try {
            t = Integer.parseInt(first);
        } catch (NumberFormatException e) {
            return null;
        }
        return new Subexpressao(simples(t), tokens.subList(1, tokens.size()));
    }

    private static Simbolo parseTerminal(String s, List<String> tokens) {
        if (tokens.isEmpty()) return null;
        String first = tokens.get(0);
        if (!s.equals(first)) return null;
        return new Simbolo(s, tokens.subList(1, tokens.size()));
    }

    private static Subexpressao analiseSintatica(List<String> tokens)
            throws ExpressaoMalformadaException
    {
        Subexpressao raiz = parseAditivo(tokens);
        if (raiz == null) throw new ExpressaoMalformadaException();
        if (!raiz.resto.isEmpty()) throw new ExpressaoMalformadaException();
        return raiz;
    }

    // Interpretador:

    private static int interpretar(String expressao)
            throws ExpressaoMalformadaException, AvaliacaoExpressaoException
    {
        return analiseSintatica(tokenize(expressao)).op.calcular();
    }

    // Gerador de expressões:

    private static final String SIMBOLOS = "57()+-*/";
    private static final int TAMANHO_SIMBOLOS = SIMBOLOS.length();

    private static String gerarExpressao(int chute, int tamanho) {
        char[] c = new char[tamanho];
        for (int i = 0; i < tamanho; i++) {
            int r = chute % TAMANHO_SIMBOLOS;
            c[i] = SIMBOLOS.charAt(r);
            chute /= TAMANHO_SIMBOLOS;
        }
        return new String(c);
    }

    private static int complicacao(String x) {
        int comp = 0;
        for (char c : x.toCharArray()) {
            if (c == '5' || c == '7') comp++;
        }
        return comp;
    }

    private static int contaPar(String x) {
        int comp = 0;
        for (char c : x.toCharArray()) {
            if (c == '(' || c == ')') comp++;
        }
        return comp;
    }

    private static int pow(int base, int expoente) {
        return expoente == 0 ? 1 : base * pow(base, expoente - 1);
    }

    // Otimizador de expressões:

    private static String acharMelhorString(int valor) {
        String melhor = "";
        int menosComplicado = 999999;
        int menosParenteses = 999999;
        int menor = melhor.length();
        for (int tamanho = 1; tamanho < 12; tamanho++) {
            boolean achou = false;
            int max = pow(TAMANHO_SIMBOLOS, tamanho);
            for (int i = 0; i < max; i++) {
                String g = gerarExpressao(i, tamanho);

                int par = contaPar(g);
                if (par > menosParenteses) continue;

                int complicado = complicacao(g);
                if (par == menosParenteses && complicado >= menosComplicado) continue;

                try {
                    if (valor == interpretar(g)) {
                        melhor = g;
                        menosComplicado = complicado;
                        menosParenteses = par;
                        System.out.println("Achei: " + valor + " = " + g);
                    }
                } catch (ExpressaoMalformadaException | AvaliacaoExpressaoException e) {
                    // Ignora e continua.
                }
            }
            if (!melhor.isEmpty()) return melhor;
        }
        return "";
    }

    private static Map<Integer, String> tabelar(int min, int max) {
        Map<Integer, String> tabela = new LinkedHashMap<>(max - min + 1);
        for (int i = min; i <= max; i++) {
            tabela.put(i, acharMelhorString(i));
        }
        return tabela;
    }

    public static void main(String[] args) {
        Map<Integer, String> tabela = tabelar(0, 100);
        for (Map.Entry<Integer,String> entry : tabela.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}

The output looks like this:

Achei: 0 = 5-5
Achei: 1 = 5/5
Achei: 2 = 7-5
Achei: 3 = 5-7+5
Achei: 4 = 5-5/5
Achei: 5 = 5
Achei: 6 = 5/5+5
Achei: 7 = 7
Achei: 8 = 7+5/5
Achei: 9 = 7+7-5
Achei: 10 = 5+5
Achei: 11 = 55/5
Achei: 12 = 7+5
Achei: 13 = 75-7-55
Achei: 13 = 7+5/5+5
Achei: 14 = 7+7
Achei: 15 = 75/5
Achei: 16 = 55/5+5
Achei: 17 = 7+5+5
Achei: 18 = 75-57
Achei: 18 = 5*5-7
Achei: 19 = 7+7+5
Achei: 20 = 75-55
Achei: 20 = 5*5-5
Achei: 21 = 7+7+7
Achei: 22 = 77-55
Achei: 23 = 5-57+75
Achei: 23 = 5*5-7+5
Achei: 24 = 7+7+5+5
Achei: 25 = 5*5
Achei: 26 = 75-7*7
Achei: 27 = 7+75-55
Achei: 27 = 7+5*5-5
Achei: 28 = 7*5-7
Achei: 29 = 7+77-55
Achei: 30 = 5*5+5
Achei: 31 = 775/5/5
Achei: 32 = 7+5*5
Achei: 33 = 7*5-7+5
Achei: 34 = 7*5-5/5
Achei: 35 = 7*5
Achei: 36 = 5/5+7*5
Achei: 37 = 7+5*5+5
Achei: 38 = 55-7-5-5
Achei: 39 = 7*7-5-5
Achei: 40 = 7*5+5
Achei: 41 = 55-7-7
Achei: 42 = 7+7*5
Achei: 43 = 55-7-5
Achei: 44 = 7*7-5
Achei: 45 = 55-5-5
Achei: 46 = 57-55/5
Achei: 47 = 57-5-5
Achei: 48 = 55-7
Achei: 49 = 7*7
Achei: 50 = 55-5
Achei: 51 = 7*7+7-5
Achei: 52 = 57-5
Achei: 53 = 5-7+55
Achei: 54 = 7*7+5
Achei: 55 = 55
Achei: 56 = 7*7+7
Achei: 57 = 57
Achei: 58 = 57+5/5
Achei: 59 = 7+57-5
Achei: 60 = 5+55
Achei: 61 = 75-7-7
Achei: 62 = 7+55
Achei: 63 = 75-7-5
Achei: 64 = 7+57
Achei: 65 = 5+5+55
Achei: 66 = 55/5+55
Achei: 67 = 7+5+55
Achei: 68 = 75-7
Achei: 69 = 7+7+55
Achei: 70 = 75-5
Achei: 71 = 7+7+57
Achei: 72 = 77-5
Achei: 73 = 5-7+75
Achei: 74 = 75-5/5
Achei: 75 = 75
Achei: 76 = 5/5+75
Achei: 77 = 77
Achei: 78 = 77+5/5
Achei: 79 = 7+77-5
Achei: 80 = 5+75
Achei: 81 = 5/5+5+75
Achei: 82 = 7+75
Achei: 83 = 7*5-7+55
Achei: 84 = 7+77
Achei: 85 = 5+5+75
Achei: 86 = 55/5+75
Achei: 87 = 7+5+75
Achei: 88 = 77+55/5
Achei: 89 = 7+7+75
Achei: 90 = 7*5+55
Achei: 91 = 7+7+77
Achei: 92 = 57+7*5
Achei: 93 = 75-57+75
Achei: 93 = 5*5-7+75
Achei: 94 = 7+7+5+75
Achei: 95 = 7*5+5+55
Achei: 96 = 755/5-55
Achei: 96 = 7+7+7+75
Achei: 97 = 7+7*5+55
Achei: 98 = 7*7+7*7
Achei: 99 = 7*7-5+55
Achei: 100 = 5*5+75
0: 5-5
1: 5/5
2: 7-5
3: 5-7+5
4: 5-5/5
5: 5
6: 5/5+5
7: 7
8: 7+5/5
9: 7+7-5
10: 5+5
11: 55/5
12: 7+5
13: 7+5/5+5
14: 7+7
15: 75/5
16: 55/5+5
17: 7+5+5
18: 5*5-7
19: 7+7+5
20: 5*5-5
21: 7+7+7
22: 77-55
23: 5*5-7+5
24: 7+7+5+5
25: 5*5
26: 75-7*7
27: 7+5*5-5
28: 7*5-7
29: 7+77-55
30: 5*5+5
31: 775/5/5
32: 7+5*5
33: 7*5-7+5
34: 7*5-5/5
35: 7*5
36: 5/5+7*5
37: 7+5*5+5
38: 55-7-5-5
39: 7*7-5-5
40: 7*5+5
41: 55-7-7
42: 7+7*5
43: 55-7-5
44: 7*7-5
45: 55-5-5
46: 57-55/5
47: 57-5-5
48: 55-7
49: 7*7
50: 55-5
51: 7*7+7-5
52: 57-5
53: 5-7+55
54: 7*7+5
55: 55
56: 7*7+7
57: 57
58: 57+5/5
59: 7+57-5
60: 5+55
61: 75-7-7
62: 7+55
63: 75-7-5
64: 7+57
65: 5+5+55
66: 55/5+55
67: 7+5+55
68: 75-7
69: 7+7+55
70: 75-5
71: 7+7+57
72: 77-5
73: 5-7+75
74: 75-5/5
75: 75
76: 5/5+75
77: 77
78: 77+5/5
79: 7+77-5
80: 5+75
81: 5/5+5+75
82: 7+75
83: 7*5-7+55
84: 7+77
85: 5+5+75
86: 55/5+75
87: 7+5+75
88: 77+55/5
89: 7+7+75
90: 7*5+55
91: 7+7+77
92: 57+7*5
93: 5*5-7+75
94: 7+7+5+75
95: 7*5+5+55
96: 7+7+7+75
97: 7+7*5+55
98: 7*7+7*7
99: 7*7-5+55
100: 5*5+75

These lines that begin with "I found" are to see what he is doing. It is interesting to see the optimizer working, as in the example below where an expression was found for the 18 with 5 characters and degree of complication 4, but when looking for a better expression, one with a degree of complication 3 was found after: / p>

Achei: 18 = 75-57
Achei: 18 = 5*5-7

Interestingly, none of the expressions generated until the 100 use parentheses (they are expensive because each pair of parentheses leave the longest expressions in 2 characters). Including, your example gives this:

31 = 7 - (5 * 5) + 7 * 7

But the program found this:

31 = 775/5/5

And in this case, the degree of complication is the same, but the size of the expression and the number of parentheses is less.