編寫使用堆棧到具有價值這樣的組合Java程序

Question

問題

考慮數字123456789的字符串。考慮可以通過將+或-散佈在字符串內形成的所有算術表達式。例子：

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

編寫使用堆棧來找到具有價值2012這樣的組合的Java程序。

我的問題

我堅持的邏輯，因爲我們必須使用兩個算術運算符。

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

Answer 1

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

認爲有數字，可以由+,- or nothing來無論是充滿之間8 empty boxes。所以你可以得到3^8 = 6561不同的排列。創建一個8字符的數組。現在排列這個數組並找到所有的可能性。抱歉，我現在不知道該怎麼做，也許別人可以給你解釋，我很確定它可以完成。使用這些排列將這些值插入原始字符串中。

您可以使用堆棧來評估表達式。可以在不考慮運算符優先級的情況下完成，大致如下：

從左到右迭代，如果遇到操作數，則將其推入堆棧。如果遇到操作員，請再次將其推入堆棧。現在，當您輸入第二個操作數時，彈出並檢索操作符，再次彈出以檢索操作數，使用這兩個操作數和操作符執行操作，並將結果推回堆棧。最後，你在堆棧上有結果。

編輯：或者只是使用Python's eval ...

Answer 2

找到組合，你需要

1234 - 5 - 6 +789 = 2012 

，但你必須在邏輯來呢。

嘗試你的組合，同時推（價值和+或 - ）它堆棧和檢查答案是否是2012年 如果不是全部彈出。所以推動和彈出，直到你發現你的組合是2012.所以堆棧項目包含從下到上的組合。

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

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

可以使用運算符陣推到堆棧

Answer 3

所以，你只需要添加這個類裏面的代碼，它會檢查，該款項將於2012年==

附：感謝您的良好運動，我會將其用於我的學生。

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

} 

}