Write a Java program that uses a stack to such a combination that has value

Question

The question

Consider the string of digits 123456789. Consider all arithmetic expression that can be formed by placing + or - interspersed within the string. Examples:

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

Write a Java program that uses a stack to find such a combination that has value 2012.

My Problem

I am stuck with the logic since we have to use two arithmetic operators.

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) {
        }                                     
    }
}

Should have not skipped the CS class. Come back, if you have a specific question. — ppeterka, Oct 25 '12 at 06:57
You have to search more... SO isn't made to resolve the exercises your professor gives you. — Aubin, Oct 25 '12 at 06:57
Why the upvotes? This question does not even classify itself as a question... — ppeterka, Oct 25 '12 at 06:58
I have been stuck on it. I don't need you to do all the work, just a suggestion would be nice :-) — xx xx, Oct 25 '12 at 06:59

Andremoniy · Answer 1 · 2019-08-28T05:23:37.063

So, you just need to add a code inside this class, which will check, that sum == 2012.

P.S. Thanks for a good exercise, I will use it for my students.

P.P.S. Ups, sorry, just fixed one mistake here. This code can work for any number of operations. You just need to enumerate them in "ops" variable and add a specific code for calculation sum.

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();
    }

}

}

score 1 · Answer 2 · answered Oct 25 '12 at 07:43

1

Found the combination you required

1234 - 5 - 6 +789  = 2012

but you have to logically come to it.

try your combinations while push (Value and + or -) it in to stack and check whether the answer is 2012 if not pop all. so push and pop until you find your combination is 2012. So that stack items contains your combination from bottom to top.

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

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

You can use operators array to push to the stack

answered Oct 25 '12 at 07:43

someone

6,577
7
37
60

I was totally over thinking it. thanks for this. – xx xx Oct 25 '12 at 07:57
It would be more elegant to use arrays of char in this case. char[] numbers = "123456789".toCharArray(); – Andremoniy Oct 25 '12 at 08:21

score 0 · Accepted Answer · edited May 23 '17 at 12:22

Rough idea, this is what I can think:

Think that there are 8 empty boxes between the numbers, which can be either filled by a +,- or nothing. So you can get 3^8 = 6561 different permutations. Create an array of 8 chars. Now permute this array and find all its possibilities.. sorry I don't know how to do this right now, maybe someone else can explain it to you, I'm pretty sure it can be done. Use these permutations to insert these values in the original string.

You can use a stack to evaluate an expression. Can be done without considering operator precedence in your case roughly like this:

Iterate from left to right, if you encounter an operand, push it to the stack. If you encounter an operator, push it to the stack again. Now when you enter a second operand, pop and retrieve the operator, pop again to retrieve an operand, do the operation with these two operands and the operator, and push the result back to the stack. In the end, you have the result on the stack.

Edit: Or just use Python's eval...

Write a Java program that uses a stack to such a combination that has value

3 Answers3