-2

问题

考虑一串数字123456789。考虑可以通过放置+或-散布在字符串中形成的所有算术表达式。例子：

1 + 2 - 345 + 67 - 8 - 9 = 292
123456 - 789 = 122667

编写一个 Java 程序，该程序使用堆栈来查找具有值的这种组合2012。

我的问题

我被逻辑困住了，因为我们必须使用两个算术运算符。

import java.util.*;

public class arithmeticStack {
    public static void main (String args[]) {
        ArrayList<String> dg = new ArrayList<String>();
        Stack<String> digits = new Stack<String>();
        int number = 0;
        dg.add("1");
        dg.add("2");
        dg.add("3");
        dg.add("4");
        dg.add("5");
        dg.add("6");
        dg.add("7");
        dg.add("8");
        dg.add("9");

        for (int i = 0; i <= dg.size() - 1; i++) {
            digits.push(dg.get(i));
        }

        for (String f : digits){
            number += Integer.parseInt(f);
        }

        while (number == 2012) {
        }                                     
    }
}
4

3 回答 3

2

所以，你只需要在这个类中添加一个代码，它将检查总和 == 2012。

PS谢谢你的好练习，我会用它给我的学生。

PPS Ups，抱歉，这里只修正了一个错误。此代码可用于任意数量的操作。您只需要在“ops”变量中枚举它们并为计算总和添加特定代码。

import java.util.Stack;

public class Arithmetics {

public static void main(String[] args) {
    String digits = "1234567890";
    //String ops = "+-*";
    String ops = "+-";

    String number = "";
    Stack<String> numbers = new Stack<>();
    for (int i = 0; i < 2 << digits.length(); i += 2) {
        number = "" + digits.charAt(0);
        for (int bit = 0; bit < digits.length() - 1; bit++) {
            int j = (2 << bit) & i;
            if (j > 0) {
                numbers.push(number);
                number = "";
            }
            number += digits.charAt(bit + 1);
        }
        numbers.push(number);

        for (String n : numbers) {
            System.out.print(n + " ");
        }
        System.out.println();

        String expression = "";
        Integer sum = 0;
        final int base = ops.length();
        for (int k = 0; k < Math.pow(base, numbers.size() - 1); k++) {
            expression = numbers.get(0);
            sum = Integer.parseInt(expression);
            for (int pos = 0; pos < numbers.size() - 1; pos++) {
                int opNum = k;
                for (int j = numbers.size() - 1; j >= pos + 1; j--) {
                    if (opNum >= Math.pow(base, j)) {
                        opNum = (int) (opNum - (opNum / (int)Math.pow(base, j)) * (int)Math.pow(base, j));
                    }
                }
                if (pos > 0) {
                    opNum = (int) (opNum - Math.pow(base, (pos - 1)));
                    opNum = (int) (opNum / Math.pow(base, pos));
                }
                expression += ops.charAt(opNum);
                // -------------------------------
                if (ops.charAt(opNum) == '+') {
                    sum += Integer.parseInt(numbers.get(pos + 1));
                } else
                if (ops.charAt(opNum) == '-') {
                    sum -= Integer.parseInt(numbers.get(pos + 1));
                } /*else
                if (ops.charAt(opNum) == '*') {
                    sum *= Integer.parseInt(numbers.get(pos + 1));
                }*/
                // -------------------------------
                expression += numbers.get(pos + 1);
            }
            System.out.println(expression + " = " + sum);
        }

        numbers.clear();
    }

}

}
于 2012-10-25T08:00:43.463 回答
1

找到您需要的组合

1234 - 5 - 6 +789  = 2012

但你必须从逻辑上来。

尝试您的组合，同时将（值和 + 或 -）推入堆栈并检查答案是否为 2012（如果不是全部弹出）。所以推并弹出，直到你发现你的组合是 2012。所以堆栈项目包含你的组合从下到上。

   String [] numbers = {"1","2","3","4","5","6","7","8","9"};

   String [] operators ={"+","-"};

您可以使用运算符数组推送到堆栈

于 2012-10-25T07:43:45.297 回答
0

粗略的想法，这是我能想到的：

认为8 empty boxes数字之间有，可以用+,- or nothing. 所以你可以得到3^8 = 6561不同的排列。创建一个包含 8 个字符的数组。现在排列这个数组并找到它所有的可能性..对不起，我现在不知道该怎么做，也许其他人可以向你解释，我很确定可以做到。使用这些排列将这些值插入到原始字符串中。

您可以使用堆栈来评估表达式。可以在不考虑您的情况下的运算符优先级的情况下完成，大致如下：

从左到右迭代，如果遇到操作数，将其压入堆栈。如果遇到运算符，请再次将其压入堆栈。现在，当您输入第二个操作数时，弹出并检索运算符，再次弹出以检索一个操作数，对这两个操作数和运算符进行操作，并将结果推回堆栈。最后，您将结果放在堆栈上。

编辑：或者只是使用Python 的eval...

于 2012-10-25T07:22:35.827 回答